Abstract
| Original language | Undefined |
|---|---|
| Pages (from-to) | 9-19 |
| Number of pages | 11 |
| Journal | Theoretical computer science |
| Volume | 414 |
| Issue number | 1 |
| DOIs | |
| Publication status | Published - 13 Jan 2012 |
Keywords
- MSC-05C
- Linear forest
- EWI-21077
- METIS-293161
- Forbidden induced subgraph
- Graph coloring
- IR-82685
Cite this
}
Updating the complexity status of coloring graphs without a fixed induced linear forest. / Broersma, Haitze J.; Golovach, P.A.; Paulusma, Daniël; Song, Jian.
In: Theoretical computer science, Vol. 414, No. 1, 13.01.2012, p. 9-19.Research output: Contribution to journal › Article › Academic › peer-review
TY - JOUR
T1 - Updating the complexity status of coloring graphs without a fixed induced linear forest
AU - Broersma, Haitze J.
AU - Golovach, P.A.
AU - Paulusma, Daniël
AU - Song, Jian
N1 - eemcs-eprint-21077
PY - 2012/1/13
Y1 - 2012/1/13
N2 - A graph is H-free if it does not contain an induced subgraph isomorphic to the graph H. The graph Pk denotes a path on k vertices. The ℓ-Coloring problem is the problem to decide whether a graph can be colored with at most ℓ colors such that adjacent vertices receive different colors. We show that 4-Coloring is NP-complete for P8-free graphs. This improves a result of Le, Randerath, and Schiermeyer, who showed that 4-Coloring is NP-complete for P9-free graphs, and a result of Woeginger and Sgall, who showed that 5-Coloring is NP-complete for P8-free graphs. Additionally, we prove that the precoloring extension version of 4-Coloring is NP-complete for P7-free graphs, but that the precoloring extension version of 3-Coloring can be solved in polynomial time for (P2+P4)-free graphs, a subclass of P7-free graphs. Here P2+P4 denotes the disjoint union of a P2 and a P4. We denote the disjoint union of s copies of a P3 by sP3 and involve Ramsey numbers to prove that the precoloring extension version of 3-Coloring can be solved in polynomial time for sP3-free graphs for any fixed s. Combining our last two results with known results yields a complete complexity classification of (precoloring extension of) 3-Coloring for H-free graphs when H is a fixed graph on at most 6 vertices: the problem is polynomial-time solvable if H is a linear forest; otherwise it is NP-complete.
AB - A graph is H-free if it does not contain an induced subgraph isomorphic to the graph H. The graph Pk denotes a path on k vertices. The ℓ-Coloring problem is the problem to decide whether a graph can be colored with at most ℓ colors such that adjacent vertices receive different colors. We show that 4-Coloring is NP-complete for P8-free graphs. This improves a result of Le, Randerath, and Schiermeyer, who showed that 4-Coloring is NP-complete for P9-free graphs, and a result of Woeginger and Sgall, who showed that 5-Coloring is NP-complete for P8-free graphs. Additionally, we prove that the precoloring extension version of 4-Coloring is NP-complete for P7-free graphs, but that the precoloring extension version of 3-Coloring can be solved in polynomial time for (P2+P4)-free graphs, a subclass of P7-free graphs. Here P2+P4 denotes the disjoint union of a P2 and a P4. We denote the disjoint union of s copies of a P3 by sP3 and involve Ramsey numbers to prove that the precoloring extension version of 3-Coloring can be solved in polynomial time for sP3-free graphs for any fixed s. Combining our last two results with known results yields a complete complexity classification of (precoloring extension of) 3-Coloring for H-free graphs when H is a fixed graph on at most 6 vertices: the problem is polynomial-time solvable if H is a linear forest; otherwise it is NP-complete.
KW - MSC-05C
KW - Linear forest
KW - EWI-21077
KW - METIS-293161
KW - Forbidden induced subgraph
KW - Graph coloring
KW - IR-82685
U2 - 10.1016/j.tcs.2011.10.005
DO - 10.1016/j.tcs.2011.10.005
M3 - Article
VL - 414
SP - 9
EP - 19
JO - Theoretical computer science
JF - Theoretical computer science
SN - 0304-3975
IS - 1
ER -