Nishikawa, Kazuhide; Nishizeki, Takao; Zhou, Xiao Bandwidth consecutive multicolorings of graphs. (English) Zbl 1419.05079 Theor. Comput. Sci. 532, 64-72 (2014). Summary: Let \(G\) be a simple graph in which each vertex \(v\) has a positive integer weight \(b(v)\) and each edge \((v,w)\) has a nonnegative integer weight \(b(v,w)\). A bandwidth consecutive multicoloring of \(G\) assigns each vertex \(v\) a specified number \(b(v)\) of consecutive positive integers so that, for each edge \((v,w)\), all integers assigned to vertex \(v\) differ from all integers assigned to vertex \(w\) by more than \(b(v,w)\). The maximum integer assigned to a vertex is called the span of the coloring. In the paper, we first investigate fundamental properties of such a coloring. We then obtain a pseudo polynomial-time exact algorithm and a fully polynomial-time approximation scheme for the problem of finding such a coloring of a given series-parallel graph with the minimum span. We finally extend the results to the case where a given graph \(G\) is a partial \(k\)-tree, that is, \(G\) has a bounded tree-width. Cited in 2 Documents MSC: 05C15 Coloring of graphs and hypergraphs 05C85 Graph algorithms (graph-theoretic aspects) Keywords:bandwidth coloring; channel assignment; multicoloring; series-parallel graph; partial \(k\)-tree; algorithm; acyclic orientation; approximation; FPTAS PDFBibTeX XMLCite \textit{K. Nishikawa} et al., Theor. Comput. Sci. 532, 64--72 (2014; Zbl 1419.05079) Full Text: DOI References: [1] Arnborg, S.; Proskurowski, A., Linear time algorithms for NP-hard problems restricted to partial \(k\)-trees, Discrete Appl. Math., 23, 11-24 (1989) · Zbl 0666.68067 [2] Bodlaender, H. L., Treewidth: algorithmic techniques and results, (Proc. MFCS 1997. Proc. MFCS 1997, Springer Lect. Notes in Computer Science, vol. 1295 (1997)), 19-36 · Zbl 0941.05057 [3] Halldórsson, M. M.; Kortsarz, G., Tools for multicoloring with applications to planar graphs and partial \(k\)-trees, J. Algorithms, 42, 2, 334-366 (2002) · Zbl 0993.05070 [4] Halldórsson, M. M.; Kortsarz, G.; Proskurowski, A., Multicoloring trees, Inform. and Comput., 180, 2, 113-129 (2003) · Zbl 1054.68016 [5] Ito, T.; Nishizeki, T.; Zhou, X., Algorithms for multicolorings of partial \(k\)-trees, IEICE Trans. Inf. Syst., E86-D, 2, 191-200 (2003) [6] Jansen, K.; Scheffler, P., Generalized coloring for tree-like graphs, Discrete Appl. Math., 75, 2, 135-155 (1997) · Zbl 0879.68076 [7] Jensen, T. R.; Toft, B., Graph Coloring Problems (1994), Wiley: Wiley New York [8] Malaguti, E.; Toth, P., An evolutionary approach for bandwidth multicoloring problems, European J. Oper. Res., 189, 638-651 (2008) · Zbl 1146.90503 [9] McDiamid, C.; Reed, B., Channel assignment on graphs of bounded treewidth, Discrete Math., 273, 183-192 (2003) · Zbl 1029.05150 [10] Pinedo, M. L., Scheduling: Theory, Algorithms and Systems (2008), Springer Science: Springer Science New York · Zbl 1155.90008 [11] Nishikawa, K.; Nishizeki, T.; Zhou, X., Algorithms for bandwidth consecutive multicolorings of graphs (Extended Abstract), (Proc. FAW-AIIM 2012. Proc. FAW-AIIM 2012, Lecture Notes in Computer Science, vol. 7285 (2012)), 117-128 · Zbl 1304.05139 [12] Takamizawa, K.; Nishizeki, T.; Saito, N., Linear-time computability of combinatorial problems on series-parallel graphs, J. Assoc. Comput. Mach., 29, 623-641 (1982) · Zbl 0485.68055 [13] West, D. B., Introduction to Graph Theory (1996), Prentice-Hall: Prentice-Hall Englewood Cliffs, NJ · Zbl 0845.05001 [14] Zhou, X.; Kanari, Y.; Nishizeki, T., Generalized vertex-colorings of partial \(k\)-trees, IEICE Trans. Fundam., E83-A, 4, 671-678 (2000) [15] Zhou, X.; Nishizeki, T., Multicolorings of series-parallel graphs, Algorithmica, 38, 271-297 (2004) · Zbl 1072.68083 [16] Zuckerman, D., Linear degree extractors and the inapproximability of max clique and chromatic number, Theory Comput., 3, 103-128 (2007) · Zbl 1213.68322 This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.