×

zbMATH — the first resource for mathematics

Exploring the complexity boundary between coloring and list-coloring. (English) Zbl 1279.05021
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.

MSC:
05C15 Coloring of graphs and hypergraphs
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Bandelt, H., & Mulder, H. (1986). Distance–hereditary graphs. Journal of Combinatorial Theory. Series B, 41, 182–208. · Zbl 0605.05024
[2] Bertossi, A. (1984). Dominating sets for split and bipartite graphs. Information Processing Letters, 19, 37–40. · Zbl 0539.68058
[3] Biro, M., Hujter, M., & Tuza, Zs. (1992). Precoloring extension. I. Interval graphs. Discrete Mathematics, 100(1–3), 267–279. · Zbl 0766.05026
[4] Bonomo, F., & Cecowski, M. (2005). Between coloring and list-coloring: {\(\mu\)}-coloring. Electronic Notes in Discrete Mathematics, 19, 117–123. · Zbl 1203.05047
[5] Bonomo, F., Durán, G., & Marenco, J. (2006). Exploring the complexity boundary between coloring and list-coloring. Electronic Notes in Discrete Mathematics, 25, 41–47. · Zbl 1134.68374
[6] Booth, K., & Lueker, G. (1976). Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms. Journal of Computer Science and Technology, 13, 335–379. · Zbl 0367.68034
[7] Brandstädt, A., Le, V., & Spinrad, J. (1999). Graph classes: A survey. Philadelphia: SIAM. · Zbl 0919.05001
[8] Colbourn, C. J. (1984). The complexity of completing partial Latin squares. Annals of Discrete Mathematics, 8, 25–30. · Zbl 0538.05013
[9] Corneil, D., & Perl, Y. (1984). Clustering and domination in perfect graphs. Discrete Applied Mathematics, 9, 27–39. · Zbl 0581.05053
[10] Easton, T., Horton, S., & Parker, R. (2000). On the complexity of certain completion problems. Congressus Numerantium, 145, 9–31. · Zbl 0976.05048
[11] Garey, M., Johnson, D., Miller, G., & Papadimitriou, C. (1980). The complexity of coloring circular arcs and chords. SIAM Journal on Algebraic and Discrete Methods, 1, 216–227. · Zbl 0499.05058
[12] Golumbic, M. (2004). Annals of discrete mathematics: Vol. 57. Algorithmic graph theory and perfect graphs (2nd ed.). Amsterdam: North–Holland.
[13] Grötschel, M., Lovász, L., & Schrijver, A. (1981). The ellipsoid method and its consequences in combinatorial optimization. Combinatorica, 1, 169–197. · Zbl 0492.90056
[14] Hall, P. (1935). On representatives of subsets. Journal of the London Mathematical Society, 10, 26–30. · Zbl 0010.34503
[15] Hell, P. (2006). Personal communication.
[16] Holyer, I. (1981). The NP-completeness of edge-coloring. SIAM Journal on Computing, 10, 718–720. · Zbl 0473.68034
[17] Hujter, M., & Tuza, Zs. (1993). Precoloring extension. II. Graph classes related to bipartite graphs. Acta Mathematica Universitatis Comenianae, 62(1), 1–11. · Zbl 0821.05026
[18] Hujter, M., & Tuza, Zs. (1996). Precoloring extension. III. Classes of perfect graphs. Combinatorics, Probability and Computing, 5, 35–56. · Zbl 0846.05034
[19] Jansen, K. (1997). The optimum cost chromatic partition problem. Lecture Notes in Computer Science, 1203, 25–36. · Zbl 1401.68353
[20] Jansen, K., & Scheffler, P. (1997). Generalized coloring for tree-like graphs. Discrete Applied Mathematics, 75, 135–155. · Zbl 0879.68076
[21] König, D. (1916). Über graphen und ihre anwendung auf determinantentheorie und mengenlehre. Mathematische Annalen, 77, 453–465. · JFM 46.0146.03
[22] Kubale, M. (1992). Some results concerning the complexity of restricted colorings of graphs. Discrete Applied Mathematics, 36, 35–46. · Zbl 0755.05036
[23] Marx, D. (2006). Precoloring extension on unit interval graphs. Discrete Applied Mathematics, 154, 995–1002. · Zbl 1090.05028
[24] Nemhauser, G., & Wolsey, L. (1988). Wiley interscience series in discrete mathematics and optimization: Integer and combinatorial optimization. New York: Wiley. · Zbl 0652.90067
[25] Tuza, Zs. (1997). Graph colorings with local constraints–a survey. Discussiones Mathematicae. Graph Theory, 17, 161–228. · 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.