### Abstract

Original language | Undefined |
---|---|

Pages (from-to) | 1-10 |

Number of pages | 10 |

Journal | Theoretical computer science |

Volume | 423 |

DOIs | |

Publication status | Published - 16 Mar 2012 |

### Keywords

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

### Cite this

*Theoretical computer science*,

*423*, 1-10. https://doi.org/10.1016/j.tcs.2011.12.076

}

*Theoretical computer science*, vol. 423, pp. 1-10. https://doi.org/10.1016/j.tcs.2011.12.076

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

Research output: Contribution to journal › Article › Academic › peer-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 -