zbMATH — the first resource for mathematics

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.

68Q25 Analysis of algorithms and problem complexity
05C15 Coloring of graphs and hypergraphs
68Q15 Complexity classes (hierarchies, relations among complexity classes, etc.)
Full Text: DOI
[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. · Zbl 0816.68070
[6] Garey, M.R.; Johnson, D.S., Computers and intractability: A guide to the theory of NP-completeness, (1979), 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. · Zbl 0821.05026
[10] 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, (), 50-59 · Zbl 0795.05057
[12] 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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.