×

Algorithmic complexity of list colorings. (English) Zbl 0807.68055

Summary: Given a graph \(G = (V,E)\) and a finite set \(L(v)\) at each vertex \(v \in V\), the List Coloring problem asks whether there exists a function \(f : V \to \cup_{v \in V} L(v)\) such that (i) \(f(v) \in L(v)\) for each \(v \in V\) and (ii) \(f(u) \neq f(v)\) whenever \(u,v \in V\) and \(uv \in E\). One of our results states that this decision problem remains NP-complete even if all of the following conditions are met: (1) each set \(L(v)\) has at most three elements, (2) each “color” \(x \in \cup_{v \in V} L(v)\) occurs in at most three sets \(L(v)\), (3) each vertex \(v \in V\) has degree at most three, and (4) \(G\) is a planar graph. On the other hand, strengthening any of the three assumptions given in the paper yields a polynomially solvable problem. The connection between List Coloring and Boolean Satisfiability is discussed, too.

MSC:

68Q25 Analysis of algorithms and problem complexity
05C15 Coloring of graphs and hypergraphs
68Q15 Complexity classes (hierarchies, relations among complexity classes, etc.)
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Alon, N.; Tarsi, M., Colorings and orientations of graphs, Combinatorica, 12, 125-134 (1992) · Zbl 0756.05049
[2] Biró, M.; Hujter, M.; Tuza, Zs., Precoloring extension. I. Interval graph, Discrete Math., 100, 267-279 (1992) · Zbl 0766.05026
[3] Brooks, R. L., On coloring the nodes of a network, Proc. Cambridge Philos. Soc., 37, 194-197 (1941) · Zbl 0027.26403
[4] Erdös, P.; Rubin, A.; Taylor, H., Choosability in graphs, Congr. Numer., 26, 125-157 (1979)
[5] M.R. Fellows, J. Kratochvil, M. Middendorf and F. Pfeiffer, The complexity of induced minors and related problems, Algorithmica, to appear.; M.R. Fellows, J. Kratochvil, M. Middendorf and F. Pfeiffer, The complexity of induced minors and related problems, Algorithmica, to appear. · Zbl 0816.68070
[6] 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
[7] Garey, M. R.; Johnson, D. S.; Stockmeyer, L., Some simplified NP-complete graph problems, Theoret. Comput. Sci., 1, 237-267 (1976) · Zbl 0338.05120
[8] Hujter, M.; Tuza, Zs., Precoloring extension. II. Graph classes related to bipartite graphs, Acta Math. Univ. Comenian., 62, 1-11 (1993) · Zbl 0821.05026
[9] M. Hujter and Zs. Tuza, Precoloring extension. III. Classes of perfect graphs, to appear.; M. Hujter and Zs. Tuza, Precoloring extension. III. Classes of perfect graphs, to appear. · Zbl 0821.05026
[10] M. Hujter and Zs. Tuza, Precoloring extension. IV. General bounds and list colorings, to appear.; M. Hujter and Zs. Tuza, Precoloring extension. IV. General bounds and list colorings, to appear. · Zbl 0821.05026
[11] Jansen, K.; Scheffler, P., Generalized coloring for tree-like graphs, (Proceedings 18th International Workshop on Graph-Theoretic Concepts in Computer Science (WG’92). Proceedings 18th International Workshop on Graph-Theoretic Concepts in Computer Science (WG’92), Lecture Notes in Computer Science, 652 (1993), Springer: Springer Berlin), 50-59 · Zbl 0795.05057
[12] J. Kratochvíl, Precoloring extension with fixed color bound, Acta Math. Univ. Comenian., to appear.; J. Kratochvíl, Precoloring extension with fixed color bound, Acta Math. Univ. Comenian., to appear. · Zbl 0821.05027
[13] Kratochvíl, J.; Savický, P.; Tuza, Zs., One more occurrence of variables makes SATISFIABILITY jump from trivial to NP-complete, SIAM J. Comput., 22, 203-210 (1993) · Zbl 0767.68057
[14] Lichtenstein, D., Planar formulae and their uses, SIAM J. Comput., 11, 329-343 (1982) · Zbl 0478.68043
[15] Thomassen, C., Every planar graph is 5-choosable, Manuscript (1993) · Zbl 0805.05023
[16] Tovey, C. A., A simplified satisfiability problem, Discrete Appl. Math., 8, 85-89 (1984) · Zbl 0534.68028
[17] Vizing, F., Vertex colouring with given colors, Discrete Anal., 29, 3-10 (1976), (in Russian)
[18] Voigt, M., List colourings of planar graphs, Discrete Math., 120, 215-219 (1993) · Zbl 0790.05030
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.