Skip to main content

Research Repository

Advanced Search

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

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

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


Authors

H.J. Broersma

P.A. Golovach

J. Song



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

Files

Accepted Journal Article (355 Kb)
PDF

Copyright Statement
NOTICE: this is the author’s version of a work that was accepted for publication in Theoretical computer science. Changes resulting from the publishing process, such as peer review, editing, corrections, structural formatting, and other quality control mechanisms may not be reflected in this document. Changes may have been made to this work since it was submitted for publication. A definitive version was subsequently published in Theoretical computer science, 423, 2012, 10.1016/j.tcs.2011.12.076






You might also like



Downloadable Citations