×

Bandwidth consecutive multicolorings of graphs. (English) Zbl 1419.05079

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.

MSC:

05C15 Coloring of graphs and hypergraphs
05C85 Graph algorithms (graph-theoretic aspects)
PDFBibTeX XMLCite
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.