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

Haitze J. Broersma, Petr A. Golovach, Daniël Paulusma, Jiupeng Song

Research output: Contribution to journalArticleAcademicpeer-review

21 Citations (Scopus)

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.
Original languageUndefined
Pages (from-to)1-10
Number of pages10
JournalTheoretical computer science
Volume423
DOIs
Publication statusPublished - 16 Mar 2012

Keywords

  • Graph coloring
  • Complexity
  • Forbidden subgraphs
  • IR-87792
  • MSC-05C
  • EWI-23727
  • METIS-300016

Cite this

Broersma, Haitze J. ; Golovach, Petr A. ; Paulusma, Daniël ; Song, Jiupeng. / Determining the chromatic number of triangle-free 2P3-free graphs in polynomial time. In: Theoretical computer science. 2012 ; Vol. 423. pp. 1-10.
@article{3b0ef39d08a44569b9c52db3e36d5abb,
title = "Determining the chromatic number of triangle-free 2P3-free graphs in polynomial time",
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.",
keywords = "Graph coloring, Complexity, Forbidden subgraphs, IR-87792, MSC-05C, EWI-23727, METIS-300016",
author = "Broersma, {Haitze J.} and Golovach, {Petr A.} and Dani{\"e}l Paulusma and Jiupeng Song",
note = "eemcs-eprint-23727",
year = "2012",
month = "3",
day = "16",
doi = "10.1016/j.tcs.2011.12.076",
language = "Undefined",
volume = "423",
pages = "1--10",
journal = "Theoretical computer science",
issn = "0304-3975",
publisher = "Elsevier",

}

Determining the chromatic number of triangle-free 2P3-free graphs in polynomial time. / Broersma, Haitze J.; Golovach, Petr A.; Paulusma, Daniël; Song, Jiupeng.

In: Theoretical computer science, Vol. 423, 16.03.2012, p. 1-10.

Research output: Contribution to journalArticleAcademicpeer-review

TY - JOUR

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

AU - Broersma, Haitze J.

AU - Golovach, Petr A.

AU - Paulusma, Daniël

AU - Song, Jiupeng

N1 - eemcs-eprint-23727

PY - 2012/3/16

Y1 - 2012/3/16

N2 - 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.

AB - 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.

KW - Graph coloring

KW - Complexity

KW - Forbidden subgraphs

KW - IR-87792

KW - MSC-05C

KW - EWI-23727

KW - METIS-300016

U2 - 10.1016/j.tcs.2011.12.076

DO - 10.1016/j.tcs.2011.12.076

M3 - Article

VL - 423

SP - 1

EP - 10

JO - Theoretical computer science

JF - Theoretical computer science

SN - 0304-3975

ER -