zbMATH — the first resource for mathematics

Complexity of unique list colorability. (English) Zbl 1146.05314
Summary: Given a list $$L(v)$$ for each vertex $$v$$, we say that the graph $$G$$ is $$L$$-colorable if there is a proper vertex coloring of $$G$$ where each vertex $$v$$ takes its color from $$L(v)$$. The graph is uniquely $$k$$-list colorable if there is a list assignment $$L$$ such that $$L(v)=k$$ for every vertex $$v$$ and the graph has exactly one $$L$$-coloring with these lists. M. Mahdian and E. S. Mahmoodian [A characterization of uniquely 2-list colorable graphs, Ars Combin. 51, 295–305 (1999; Zbl 0977.05046)] gave a polynomial-time characterization of uniquely 2-list colorable graphs. Answering an open question from M. Ghebleh and E. S. Mahmoodian [On uniquely list colorable graphs, Ars Comb. 59, 307–318 (2001; Zbl 1066.05063)] and M. Mahdian and E. S. Mahmoodian [loc. cit.], we show that uniquely 3-list colorable graphs are unlikely to have such a nice characterization, since recognizing these graphs is $$\Sigma_2^p$$-complete.

MSC:
 05C85 Graph algorithms (graph-theoretic aspects) 05C15 Coloring of graphs and hypergraphs 68Q15 Complexity classes (hierarchies, relations among complexity classes, etc.) 68R10 Graph theory (including graph drawing) in computer science
Full Text:
References:
 [1] Blass, A.; Gurevich, Y., On the unique satisfiability problem, Inform. control, 55, 1-3, 80-88, (1982) · Zbl 0543.03027 [2] Chang, R.; Rohatgi, P., On unique satisfiability and randomized reductions, Bull. eur. assoc. theoret. comput. sci., 42, 151-159, (October 1990), Columns: Structural Complexity [3] Dinitz, J.H.; Martin, W.J., The stipulation polynomial of a uniquely List-colorable graph, Australas. J. combin., 11, 105-115, (1995) · Zbl 0826.05025 [4] Eslahchi, Ch.; Ghebleh, M.; Hajiabolhassan, H., Some concepts in List coloring, J. combin. math. combin. comput., 41, 151-160, (2002) · Zbl 1043.05046 [5] P. Erdős, A.L. Rubin, H. Taylor, Choosability in graphs, in: Proceedings of the West Coast Conference on Combinatorics, Graph Theory and Computing (Humboldt State Univ., Arcata, Calif., 1979) Winnipeg, Man., Utilitas Math., 1980, pp. 125-157 [6] Ghebleh, M.; Mahmoodian, E.S., On uniquely List colorable graphs, Ars combin., 59, 307-318, (2001) · Zbl 1066.05063 [7] Gutner, S., The complexity of planar graph choosability, Discrete math., 159, 1-3, 119-130, (1996) · Zbl 0865.05066 [8] Mahdian, M.; Mahmoodian, E.S., A characterization of uniquely 2-List colorable graphs, Ars combin., 51, 295-305, (1999) · Zbl 0977.05046 [9] Papadimitriou, C.H., Computational complexity, (1994), Addison-Wesley Publishing Company Reading, MA · Zbl 0557.68033 [10] Schaefer, M.; Umans, C., Completeness in the polynomial-time hierarchy: A compendium, SIGACT news, 33, 3, 32-49, (2002) [11] Tuza, Zs., Graph colorings with local constraints—a survey, Discuss. math. graph theory, 17, 2, 161-228, (1997) · Zbl 0923.05027 [12] Vizing, V.G., Coloring the vertices of a graph in prescribed colors, Diskret. analiz (29 metody diskret. anal. v teorii kodov i shem), 101, 3-10, (1976) · Zbl 1249.90303 [13] Valiant, L.G.; Vazirani, V.V., NP is as easy as detecting unique solutions, Theoret. comput. sci., 47, 1, 85-93, (1986) · Zbl 0621.68030
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.