Complexity of coloring graphs without forbidden induced subgraphs

D. Král, J. Kratochvil, Zs. Tuza, G.J. Woeginger

    Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

    146 Citations (Scopus)


    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.
    Original languageEnglish
    Title of host publicationGraph-Theoretic Concepts in Computer Science (Proceedings 27th International Workshop, WG 2001, Boltenhagen, Germany, June 14-16, 2001)
    EditorsA. Brandstädt, V.B. Le
    Place of PublicationBerlin
    Publication statusPublished - 2001

    Publication series

    NameLecture Notes in Computer Science
    ISSN (Print)0302-9743


    Dive into the research topics of 'Complexity of coloring graphs without forbidden induced subgraphs'. Together they form a unique fingerprint.

    Cite this