4-Coloring H-free graphs when H is small

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

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, December). 4-Coloring H-free graphs when H is small

• Presentation Conference Type: Conference Paper (Published)
• Publication Date: 2012
• Deposit Date: Mar 11, 2013
• Print ISSN: 0302-9743
• 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