×

Complexity of list coloring problems with a fixed total number of colors. (English) Zbl 0990.05042

In the list coloring problem, a graph \(G=(V,E)\) is given and with each vertex \(v\), a list of colors \(L(v)\). The problem is to select for each vertex a color from its list such that adjacent vertices get different colors. This paper looks at versions of the problem where additionally there is a function \(p\), such that each color \(j\) is given to exactly (or respectively at most) \(p(j)\) vertices. The paper establishes NP-completeness for the problem when there are three colors for bipartite planar graphs, and shows it is polynomially time solvable when there are two colors. The paper also shows that for a fixed number of colors, the problems (and the standard list coloring problem) are polynomially solvable for treeds and for graphs of bounded treewidth. Treeds can be defined as follows. A forest is a treed. If we have a treed and replace one vertex \(v\) by a treed such that each vertex in the latter treed is exactly adjacent to all neighbors of \(v\), then we again have a treed.

MSC:

05C15 Coloring of graphs and hypergraphs
05C85 Graph algorithms (graph-theoretic aspects)
05C05 Trees
68Q25 Analysis of algorithms and problem complexity
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Biro, M.; Hujter, M.; Tuza, Zs., Precoloring extension I. Interval graphs, Discrete Math., 100, 267-279 (1992) · Zbl 0766.05026
[2] Bodlaender, H. L., A tourist guide through treewidth, Acta Cybernet., 11, 1-21 (1993) · Zbl 0804.68101
[3] Bodlaender, H. L., Treewidth: algorithmic techniques, results, (Privara, I.; Ruzicka, P., Proceedings of the 22nd International Symposium on Mathematical Foundations of Computer Science. Proceedings of the 22nd International Symposium on Mathematical Foundations of Computer Science, Lecture Notes in Computer Science, Vol. 1295 (1997), Springer: Springer Berlin), 29-36 · Zbl 0941.05057
[4] Buer, H.; Möhring, R. H., A fast algorithm for the decomposition of graphs and posets, Math. Oper. Res., 8, 170-184 (1983) · Zbl 0517.05057
[5] Corneil, D. G.; Lerchs, H.; Stewart Burlingham, L., Complement reducible graphs, Discrete Appl. Math., 3, 164-174 (1981) · Zbl 0463.05057
[6] Cournier, A.; Habib, M., A new linear algorithm for modular decomposition, (Tison, S., Proceedings of the Colloquium on Trees in Algebra and Programming—CAAP’94. Proceedings of the Colloquium on Trees in Algebra and Programming—CAAP’94, Lecture Notes in Computer Science, Vol. 787 (1994), Springer: Springer Berlin), 68-84 · Zbl 0938.05502
[7] De Simone, C., On the vertex packing problem, Graphs Combin., 9, 19-30 (1993) · Zbl 0781.05041
[8] Dror, M.; Finke, G.; Gravier, S.; Kubiak, W., On the complexity of a restricted list coloring problem, Discrete Math., 195, 103-109 (1999) · Zbl 0928.05057
[9] P. Erdős, A.L. Rubin, H. Taylor, Choosability in graphs, Proceedings of the West Coast Conference on Combinatorics, Graph Theory and Computing, Arcata, CA, Congr. Numer. XXVI (1979) 125-157.; P. Erdős, A.L. Rubin, H. Taylor, Choosability in graphs, Proceedings of the West Coast Conference on Combinatorics, Graph Theory and Computing, Arcata, CA, Congr. Numer. XXVI (1979) 125-157.
[10] Fon-Der-Flaass, D. G., Arrays of distinct representatives—a very simple NP-complete problem, Discrete Math., 171, 295-298 (1997) · Zbl 0879.68040
[11] Garey, M. R.; Johnson, D. S., Computers and Intractability: a Guide to the Theory of NP-completeness (1979), Freeman: Freeman New York · Zbl 0411.68039
[12] Golumbic, M. C., Algorithmic Graph Theory and Perfect Graphs (1980), Academic Press: Academic Press New York · Zbl 0541.05054
[13] S. Gravier, Coloration et produits de graphes, Thesis, Université Joseph Fourier, Grenoble, France, 1996 (in French).; S. Gravier, Coloration et produits de graphes, Thesis, Université Joseph Fourier, Grenoble, France, 1996 (in French).
[14] Habib, M.; Maurer, M. C., On the X-join decomposition for undirected graphs, Discrete Appl. Math., 1, 201-210 (1979) · Zbl 0439.05041
[15] C. Hoàng, Thesis, McGill University, Montréal, Canada, 1985.; C. Hoàng, Thesis, McGill University, Montréal, Canada, 1985.
[16] Jansen, K.; Scheffler, P., Generalized coloring for tree-like graphs, Discrete Appl. Math., 75, 135-155 (1997) · Zbl 0879.68076
[17] D. Kobler, Modèles biologique en optimisation combinatoire et modèles mathématiques en génétique, Thesis, Swiss Federal Institute of Technology in Lausanne, Switzerland, 1999 (in French).; D. Kobler, Modèles biologique en optimisation combinatoire et modèles mathématiques en génétique, Thesis, Swiss Federal Institute of Technology in Lausanne, Switzerland, 1999 (in French).
[18] Kratochv’il, J., Precoloring extension with fixed color bound, Acta Math. Univ. Comenian, 62, 139-153 (1993) · Zbl 0821.05027
[19] Lovàsz, L., Normal hypergraphs and the perfect graph conjecture, Discrete Math., 2, 253-267 (1972) · Zbl 0239.05111
[20] R.M. McConnell, J. Spinrad, Linear-time modular decomposition and efficient transitive orientation of undirected graphs. Proceedings of the fifth Annual ACM-SIAM Symposium on Discrete Algorithms, 1994, pp. 536-545.; R.M. McConnell, J. Spinrad, Linear-time modular decomposition and efficient transitive orientation of undirected graphs. Proceedings of the fifth Annual ACM-SIAM Symposium on Discrete Algorithms, 1994, pp. 536-545. · Zbl 0867.05068
[21] Seinsche, S., On a property of the class of \(n\)-colorable graphs, J. Combin. Theory B, 16, 191-193 (1974) · Zbl 0269.05103
[22] V.G. Vizing, Vertex colorings with given colors, Metody Diskret. Analiz. 29 (1976) 3-10 (in Russian).; V.G. Vizing, Vertex colorings with given colors, Metody Diskret. Analiz. 29 (1976) 3-10 (in Russian).
[23] de Werra, D., Restricted coloring models for timetabling, Discrete Math., 165/166, 161-170 (1997) · Zbl 0876.90060
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.