Abstract
In their paper, C.H.Papadimitriou and M.Yannakakis [PY] posed the problem of classifying the complexity of graph critical uncolorability; and in particular, they asked whether the minimal-3-uncolorability problem is DP-complete. This paper gives an affirmative answer to the above question. We show that minimal-k-uncolorability is DP-complete, for all fixed k≥3. Furthermore, the reduction can be modified by using “sensitive” transformations to resolve the planar case (for k=3), bounded vertex degree case and their combination.
Research supported by NSF grant DCR-8301766.
This is a preview of subscription content, log in via an institution to check access.
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
K. Appel and W. Haken, “Every Planar Graph is 4-Colorable”, Ill. J. Math 21, 429–567 [1977]
R. Brooks, “On Coloring the Nodes of a Network”, Proc. Combridge Philos. Soc. 37, 194–197. [1941]
A. Blass and Y. Gurevich, “On the Unique Satisfiability Problem”, Information and Control 55, 80–88. [1982]
T. Coleman and J. Cai, “The Cyclic Coloring Problems and Estimation of Sparse Hessian Matrices”, SIAM Journal on Algebraic and Discrete Methods. Vol 7, pp 221–235. [1986]
J. Cai and L. Hemachandra, “The Boolean Hierarchy: Hardware over NP”, Proc. of the Structure in Complexity Theory Conference, Springer-Verlag Lecture Notes in Computer Science 1986.
M.Garey and D.Johnson, Computers and Intractability. W.H.Freeman and Company. [1979]
M. Garey, D. Johnson and L. Stockmeyer, “Some Simplified NP-Complete Graph Problems”, Theoretical Computer Science 1, 237–267.[1976]
R. Karp, “Reducibility Among Combinatorial Problems”, in R.Miller and J.Thatcher (eds.), Complexity of Computer Computations, Plenum Press. 85–103. [1972]
O. Ore, “Four Color Conjecture.” Academic Press, [1976].
C.H.Papadimitriou and D. Wolfe, “The Complexity of Facet Resolved”, Proc. of IEEE Foundations on Computer Science. [1985].
C.H. Papadimitriou and M. Yannakakis, “The Complexity of Facets (and Some Facets of Complexity)”, JCSS 28,2,244–259[1982]
L. Stockmeyer, “Planar 3-Colorability is NP-Complete”, SIGACT News,5:3 19–25.[1973]
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 1987 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Cai, Jy., Meyer, G.E. (1987). On the complexity of graph critical uncolorability. In: Ottmann, T. (eds) Automata, Languages and Programming. ICALP 1987. Lecture Notes in Computer Science, vol 267. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-18088-5_34
Download citation
DOI: https://doi.org/10.1007/3-540-18088-5_34
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-18088-3
Online ISBN: 978-3-540-47747-1
eBook Packages: Springer Book Archive