Abstract
We give a complete characterization of parameter graphs H for which the problem of coloring H-free graphs is polynomial and for which it is NP-complete. We further initiate a study of this problem for two forbidden subgraphs.
This author acknowledges further partial support of Czech research grant GAUK 158/1999.
Research supported in part by the Hungarian Scientific Research Fund, grants OTKA T-026575 and T-032969, and Czech Grant GAFFCR 201/99/0242 (DIMATIA).
Project LN00A056 supported by The Ministry of Education of Czech Republic
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Chvátal, V.: Perfectly ordered graphs, in: Topics on Perfect Graphs (C. Berge, V. Chvátal, eds.), Annals of Discrete Mathematics 21 (1984) 63–65
Erdős, P.: Graph theory and probability, Canad. J. Math. 11 (1959) 34–38.
Fellows, M.R., Kratochvíl, J., Middendorf, M., Pfeiffer, F.: The complexity of induced minors and related problems, Algorithmica 13 (1995) 266–282
Holyer, I.: The NP-completeness of edge-coloring, SIAM J. Comput. 10 (1981) 718–720.
Lichtenstein, D.: Planar formulae and their uses, SIAM J. Comput. 11 (1982) 329–343.
Maffray, F., Preissmann, M.: On the NP-completeness of the k-colorability problem for triangle-free graphs, Discr. Math. 162 (1996), 313–317
Olariu, S.: Paw-free graphs, Inform. Process. Lett. 28 (1988), 53–54
Randerath, B., Schiermeyer, I.: 3-colorability in P for P 6-free graphs, Rutcor Research Report 39-2001, ext. abstract in Electronic Notes in Discrete Math., Vol. 8 (2001).
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2001 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Král’, D., Kratochvíl, J., Tuza, Z., Woeginger, G.J. (2001). Complexity of Coloring Graphs without Forbidden Induced Subgraphs. In: Brandstädt, A., Le, V.B. (eds) Graph-Theoretic Concepts in Computer Science. WG 2001. Lecture Notes in Computer Science, vol 2204. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-45477-2_23
Download citation
DOI: https://doi.org/10.1007/3-540-45477-2_23
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-42707-0
Online ISBN: 978-3-540-45477-9
eBook Packages: Springer Book Archive