Updating the complexity status of coloring graphs without a fixed induced linear forest

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

Abstract

A graph is H-free if it does not contain an induced subgraph isomorphic to the graph H. The graph Pk denotes a path on k vertices. The ℓ-Coloring problem is the problem to decide whether a graph can be colored with at most ℓ colors such that adjacent vertices receive different colors. We show that 4-Coloring is NP-complete for P8-free graphs. This improves a result of Le, Randerath, and Schiermeyer, who showed that 4-Coloring is NP-complete for P9-free graphs, and a result of Woeginger and Sgall, who showed that 5-Coloring is NP-complete for P8-free graphs. Additionally, we prove that the precoloring extension version of 4-Coloring is NP-complete for P7-free graphs, but that the precoloring extension version of 3-Coloring can be solved in polynomial time for (P2+P4)-free graphs, a subclass of P7-free graphs. Here P2+P4 denotes the disjoint union of a P2 and a P4. We denote the disjoint union of s copies of a P3 by sP3 and involve Ramsey numbers to prove that the precoloring extension version of 3-Coloring can be solved in polynomial time for sP3-free graphs for any fixed s. Combining our last two results with known results yields a complete complexity classification of (precoloring extension of) 3-Coloring for H-free graphs when H is a fixed graph on at most 6 vertices: the problem is polynomial-time solvable if H is a linear forest; otherwise it is NP-complete.

Citation

Broersma, H., Golovach, P., Paulusma, D., & Song, J. (2012). Updating the complexity status of coloring graphs without a fixed induced linear forest. Theoretical Computer Science, 414(1), 9-19. https://doi.org/10.1016/j.tcs.2011.10.005

• Journal Article Type: Article
• Publication Date: Jan 13, 2012
• Deposit Date: Dec 6, 2011
• Journal: Theoretical Computer Science
• Print ISSN: 0304-3975
• Publisher: Elsevier
• Peer Reviewed: Peer Reviewed
• Volume: 414
• Issue: 1
• Pages: 9-19
• DOI: https://doi.org/10.1016/j.tcs.2011.10.005
• Keywords: Graph coloring, Forbidden induced subgraph, Linear forest.
• Public URL: https://durham-repository.worktribe.com/output/1501878