publication . Conference object . Book . Part of book or chapter of book . 2001

Complexity of Coloring Graphs without Forbidden Induced Subgraphs

Král, D.; Jan Kratochvíl; Tuza, Z.; Woeginger, G. J.;
Closed Access English
  • Published: 01 Jan 2001
  • Publisher: Springer
  • Country: Netherlands
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.
Subjects
free text keywords: Complete coloring, 1-planar graph, Greedy coloring, Discrete mathematics, Combinatorics, Chordal graph, Indifference graph, Strong perfect graph theorem, Brooks' theorem, Graph coloring, Mathematics
Download fromView all 3 versions
http://link.springer.com/conte...
Part of book or chapter of book
Provider: Crossref
Repository TU/e
Conference object . 2001
Provider: NARCIS
Powered by OpenAIRE Open Research Graph
Any information missing or wrong?Report an Issue
publication . Conference object . Book . Part of book or chapter of book . 2001

Complexity of Coloring Graphs without Forbidden Induced Subgraphs

Král, D.; Jan Kratochvíl; Tuza, Z.; Woeginger, G. J.;