The complexity of the \(T\)-coloring problem for graphs with small degree (Q1406032)

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.