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.
|Title of host publication||Graph-Theoretic Concepts in Computer Science (Proceedings 27th International Workshop, WG 2001, Boltenhagen, Germany, June 14-16, 2001)|
|Editors||A. Brandstädt, V.B. Le|
|Place of Publication||Berlin|
|Publication status||Published - 2001|
|Name||Lecture Notes in Computer Science|