zbMATH — the first resource for mathematics

Exploring the complexity boundary between coloring and list-coloring. (English) Zbl 1134.68374
Faigle, U. (ed.) et al., CTW2006. Cologne-Twente Workshop on graphs and combinatorial optimization, Lambrecht, Germany, June 5–9, 2006. Amsterdam: Elsevier. Electronic Notes in Discrete Mathematics 25, 41-47 (2006).
Summary: Many classes of graphs where the vertex coloring problem is polynomially solvable are known, the most prominent being the class of perfect graphs. However, the list-coloring problem is NP-complete for many subclasses of perfect graphs. In this work we explore the complexity boundary between vertex coloring and list-coloring on such subclasses of perfect graphs, where the former admits polynomial-time algorithms but the latter is NP-complete. Our goal is to analyze the computational complexity of coloring problems lying “between” (from a computational complexity viewpoint) these two problems: precoloring extension, \(\mu\) -coloring, and \((\gamma, \mu)\)-coloring.
For the entire collection see [Zbl 1109.05003].

68Q25 Analysis of algorithms and problem complexity
05C15 Coloring of graphs and hypergraphs
05C85 Graph algorithms (graph-theoretic aspects)
Full Text: DOI
[1] Biro, M.; Hujter, M.; Tuza, Zs., Precoloring extension. I. interval graphs, Discrete mathematics, 100, 1-3, 267-279, (1992) · Zbl 0766.05026
[2] Bonomo, F.; Cecowski, M., Between coloring and List-coloring: μ-coloring, Electronic notes in discrete mathematics, 19, 117-123, (2005) · Zbl 1203.05047
[3] Colbourn, C.J., The complexity of completing partial Latin squares, Annals of discrete mathematics, 8, 25-30, (1984) · Zbl 0538.05013
[4] Grötschel, M.; Lovász, L.; Schrijver, A., The ellipsoid method and its consequences in combinatorial optimization, Combinatorica, 1, 169-197, (1981) · Zbl 0492.90056
[5] Holyer, I., The NP-completeness of edge-coloring, SIAM journal on computing, 10, 718-720, (1981) · Zbl 0473.68034
[6] Hujter, M.; Tuza, Zs., Precoloring extension. II. graph classes related to bipartite graphs, Acta Mathematica universitatis comenianae, 62, 1, 1-11, (1993) · Zbl 0821.05026
[7] Hujter, M.; Tuza, Zs., Precoloring extension. III. classes of perfect graphs, Combinatorics, probability and computing, 5, 35-56, (1996) · Zbl 0846.05034
[8] Jansen, K., The optimum cost chromatic partition problem, (), 25-36
[9] Jansen, K.; Scheffler, P., Generalized coloring for tree-like graphs, Discrete applied mathematics, 75, 135-155, (1997) · Zbl 0879.68076
[10] König, D., Über graphen und ihre anwendung auf determinantentheorie und mengenlehre, Mathematische annalen, 77, 453-465, (1916) · JFM 46.0146.03
[11] Kubale, M., Some results concerning the complexity of restricted colorings of graphs, Discrete applied mathematics, 36, 35-46, (1992) · Zbl 0755.05036
[12] D. Marx, Precoloring extension on unit interval graphs, manuscript, 2004
[13] Tuza, Zs., Graph colorings with local constraints – a survey, Discussiones mathematicae. graph theory, 17, 161-228, (1997) · Zbl 0923.05027
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.