4-Coloring H-free graphs when H is small

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

Abstract

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

Citation

Golovach, P., Paulusma, D., & Song, J. (2013). 4-Coloring H-free graphs when H is small. Discrete Applied Mathematics, 161(1-2), 140-150. https://doi.org/10.1016/j.dam.2012.08.022

• Journal Article Type: Article
• Publication Date: Jan 1, 2013
• Deposit Date: Mar 11, 2013
• Publicly Available Date: Apr 17, 2013
• Journal: Discrete Applied Mathematics
• Print ISSN: 0166-218X
• Electronic ISSN: 1872-6771
• Publisher: Elsevier
• Peer Reviewed: Peer Reviewed
• Volume: 161
• Issue: 1-2
• Pages: 140-150
• DOI: https://doi.org/10.1016/j.dam.2012.08.022
• Public URL: https://durham-repository.worktribe.com/output/1487663