# 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.

##### MSC:
 68Q25 Analysis of algorithms and problem complexity 05C15 Coloring of graphs and hypergraphs 68Q15 Complexity classes (hierarchies, relations among complexity classes, etc.)
##### Keywords:
list coloring problem; Boolean satisfiability
Full Text:
##### References:
  Alon, N.; Tarsi, M., Colorings and orientations of graphs, Combinatorica, 12, 125-134, (1992) · Zbl 0756.05049  Biró, M.; Hujter, M.; Tuza, Zs., Precoloring extension. I. interval graph, Discrete math., 100, 267-279, (1992) · Zbl 0766.05026  Brooks, R.L., On coloring the nodes of a network, Proc. Cambridge philos. soc., 37, 194-197, (1941) · Zbl 0027.26403  Erdös, P.; Rubin, A.; Taylor, H., Choosability in graphs, Congr. numer., 26, 125-157, (1979)  M.R. Fellows, J. Kratochvil, M. Middendorf and F. Pfeiffer, The complexity of induced minors and related problems, Algorithmica, to appear. · Zbl 0816.68070  Garey, M.R.; Johnson, D.S., Computers and intractability: A guide to the theory of NP-completeness, (1979), Freeman New York · Zbl 0411.68039  Garey, M.R.; Johnson, D.S.; Stockmeyer, L., Some simplified NP-complete graph problems, Theoret. comput. sci., 1, 237-267, (1976) · Zbl 0338.05120  Hujter, M.; Tuza, Zs., Precoloring extension. II. graph classes related to bipartite graphs, Acta math. univ. Comenian., 62, 1-11, (1993) · Zbl 0821.05026  M. Hujter and Zs. Tuza, Precoloring extension. III. Classes of perfect graphs, to appear. · Zbl 0821.05026  M. Hujter and Zs. Tuza, Precoloring extension. IV. General bounds and list colorings, to appear. · Zbl 0821.05026  Jansen, K.; Scheffler, P., Generalized coloring for tree-like graphs, (), 50-59 · Zbl 0795.05057  J. Kratochvíl, Precoloring extension with fixed color bound, Acta Math. Univ. Comenian., to appear. · Zbl 0821.05027  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  Lichtenstein, D., Planar formulae and their uses, SIAM J. comput., 11, 329-343, (1982) · Zbl 0478.68043  Thomassen, C., Every planar graph is 5-choosable, Manuscript, (1993) · Zbl 0805.05023  Tovey, C.A., A simplified satisfiability problem, Discrete appl. math., 8, 85-89, (1984) · Zbl 0534.68028  Vizing, F., Vertex colouring with given colors, Discrete anal., 29, 3-10, (1976), (in Russian)  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.