Determining the chromatic number of triangle-free 2P3-free graphs in polynomial time

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

Abstract

Let 2P3 denote the disjoint union of two paths on three vertices. A graph G that has no subgraph isomorphic to a graph H is called H-free. The Vertex Coloring problem is the problem to determine the chromatic number of a graph. Its computational complexity for triangle-free H-free graphs has been classified for every fixed graph H on at most 6 vertices except for the case H=2P3. This remaining case is posed as an open problem by Dabrowski, Lozin, Raman and Ries. We solve their open problem by showing polynomial-time solvability.

Citation

Broersma, H., Golovach, P., Paulusma, D., & Song, J. (2012). Determining the chromatic number of triangle-free 2P3-free graphs in polynomial time. Theoretical Computer Science, 423, 1-10. https://doi.org/10.1016/j.tcs.2011.12.076

• Journal Article Type: Article
• Publication Date: Mar 1, 2012
• Deposit Date: Dec 20, 2014
• Publicly Available Date: Jan 9, 2015
• Journal: Theoretical Computer Science
• Print ISSN: 0304-3975
• Publisher: Elsevier
• Peer Reviewed: Peer Reviewed
• Volume: 423
• Pages: 1-10
• DOI: https://doi.org/10.1016/j.tcs.2011.12.076
• Keywords: Chromatic number, Triangle-free, Forbidden induced subgraph.
• Public URL: https://durham-repository.worktribe.com/output/1447908