Skip to main content

Research Repository

Advanced Search

4-Coloring H-free graphs when H is small

Golovach, P.A.; Paulusma, D.; Song, J.

Authors

P.A. Golovach

J. Song



Contributors

Mária Bieliková
Editor

Gerhard Friedrich
Editor

Georg Gottlob
Editor

Stefan Katzenbeisser
Editor

György Turán
Editor

Abstract

The k-Coloring problem is to test whether a graph can be colored with at most k colors such that no two adjacent vertices receive the same color. If a graph G does not contain a graph H as an induced subgraph, then G is called H-free. For any fixed graph H on at most 6 vertices, it is known that 3-Coloring is polynomial-time solvable on H-free graphs whenever H is a linear forest and NP-complete otherwise. By solving the missing case P2 + P3, we prove the same result for 4-Coloring provided that H is a fixed graph on at most 5 vertices.

Citation

Golovach, P., Paulusma, D., & Song, J. (2012). 4-Coloring H-free graphs when H is small. In M. Bieliková, G. Friedrich, G. Gottlob, S. Katzenbeisser, & G. Turán (Eds.), Theory and practice of computer science : 38th Conference on Current trends in theory and practice of computer science, SOFSEM 2012, Špindlerův Mlýn, Czech Republic, 21-27 January 2012 ; proceedings (289-300). https://doi.org/10.1007/978-3-642-27660-6_24

Publication Date 2012
Deposit Date Mar 11, 2013
Pages 289-300
Series Title Lecture notes in computer science
Series Number 7147
Series ISSN 0302-9743,1611-3349
Book Title Theory and practice of computer science : 38th Conference on Current trends in theory and practice of computer science, SOFSEM 2012, Špindlerův Mlýn, Czech Republic, 21-27 January 2012 ; proceedings.
ISBN 9783642276590
DOI https://doi.org/10.1007/978-3-642-27660-6_24
Public URL https://durham-repository.worktribe.com/output/1156242
Additional Information Series: Lecture Notes in Computer Science, Volume 7147


You might also like



Downloadable Citations