The complexity of the \(T\)-coloring problem for graphs with small degree
type: Item
instance of: scholarly article
title: The complexity of the \(T\)-coloring problem for graphs with small degree
zbMATH Open document ID: 1023.05126
DOI: 10.1016/S0166-218X(02)00576-0
author: Krzysztof Giaro
author: R. Janczewski
author: Michal Malafiejski
published in: Discrete Applied Mathematics
publication date: 2003-09-09T00:00:00Z
review text: The paper studies in some detail the \({T}\)-coloring problem being a generalization of the vertex coloring problem. The problem possesses strong engineering motivation as a representation of the channel assignment in broadcast networks. Minimizing the span of the frequency band is the objective. It was investigated by \textit{W. K. Hale} (1980), and it was proved to be NP-complete in the strong sense. Nevertheless, numerous instances of the general problem happen to posses polynomial-time algorithms. The authors study extensively the optimization problem, called \({T}\)-span, that guarantees the span of the constrained \({T}\)-coloring is minimum. A certain regular structure of the considered graphs is motivated by technical models of the represented circuits (channels). The authors claim that the \({T}\)-span problem with smallest possible span on graphs with small degree \(\Delta \) is NP-complete in the strong sense producing also several detailed results concerning NP-completeness or existence of polynomial-time algorithms for related subproblems. The paper is hard to read up to the details probably by misprints of the text. It is difficult to believe that it would be the intention of the authors to investigate a graph \(H\) that is isomorphic to all subgraphs of a given graph \(G\). Certain results concern such a definition. It is worthwhile to mention that related problems were previously studied by R. Janczewski who is one of the authors of the reviewed paper. A number of definitions and results of \textit{R. Janczewski} [Discrete Math. 234, 171-179 (2001; Zbl 0997.05035)] are used in the present paper.
reviewed by: Adam Kapralski
Mathematics Subject Classification ID: 05C85
Mathematics Subject Classification ID: 05C15
Mathematics Subject Classification ID: 68R10
zbMATH DE Number: 1977903
zbMATH Keywords: T-span
MaRDI profile type: Publication
cites work: Q4731201
cites work: Q4252727
cites work: Q3322121
cites work: Q5286940
cites work: Homomorphisms of graphs into odd cycles
cites work: Distance graphs and the \(T\)-coloring problem
cites work: The channel assignment problem for mutually adjacent sites
cites work: On the complexity of H-coloring
cites work: The NP-Completeness of Edge-Coloring
cites work: Divisibility and \(T\)-span of graphs
cites work: A rainbow about \(T\)-colorings for complete graphs
cites work: \(T\)-colorings of graphs
cites work: \(T\)-graphs and the channel assignment problem
cites work: Further Results on T-Coloring and Frequency Assignment Problems
cites work: \(T\)-colorings of graphs: recent results and open problems
cites work: List \(T\)-colorings of graphs
cites work: Q3487366
Recommended article: The complexity of some graph colouring problems
Recommended article: Small H-Coloring Problems for Bounded Degree Digraphs
Recommended article: On Approximately Counting Colorings of Small Degree Graphs
Recommended article: \(T\)-colorings of graphs
Recommended article: The complexity of \(H\)-colouring of bounded degree graphs
Recommended article: Q3690214
Recommended article: The complexity of generalized graph colorings
Recommended article: On the complexity of coloring ‐graphs
Recommended article: Complexity of total dominator coloring in graphs
Recommended article: The complexity of colouring problems on dense graphs
description: scientific article; zbMATH DE number 1977903