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 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
- APA
- Author
- BIBTEX
- Harvard
- Standard
- RIS
- Vancouver