### Abstract

Original language | English |
---|---|

Pages (from-to) | 609-619 |

Number of pages | 11 |

Journal | European journal of combinatorics |

Volume | 34 |

Issue number | 3 |

DOIs | |

Publication status | Published - 2013 |

### Fingerprint

### Keywords

- EWI-22741
- MSC-05C
- Induced subgraph
- Computational Complexity
- Coloring
- H-free graph

### Cite this

*European journal of combinatorics*,

*34*(3), 609-619. https://doi.org/10.1016/j.ejc.2011.12.008

}

*European journal of combinatorics*, vol. 34, no. 3, pp. 609-619. https://doi.org/10.1016/j.ejc.2011.12.008

**Three complexity results on coloring $P_k$-free graphs.** / Broersma, Haitze J.; Fomin, Vedor V.; Golovach, Petr A.; Paulusma, Daniël.

Research output: Contribution to journal › Article › Academic › peer-review

TY - JOUR

T1 - Three complexity results on coloring $P_k$-free graphs

AU - Broersma, Haitze J.

AU - Fomin, Vedor V.

AU - Golovach, Petr A.

AU - Paulusma, Daniël

PY - 2013

Y1 - 2013

N2 - We prove three complexity results on vertex coloring problems restricted to $P_k$-free graphs, i.e., graphs that do not contain a path on k vertices as an induced subgraph. First of all, we show that the pre-coloring extension version of 5-coloring remains NP-complete when restricted to P6-free graphs. Recent results of Hoàng et al. imply that this problem is polynomially solvable on P5-free graphs. Secondly, we show that the pre-coloring extension version of 3-coloring is polynomially solvable for P6-free graphs. This implies a simpler algorithm for checking the 3-colorability of P6-free graphs than the algorithm given by Randerath and Schiermeyer. Finally, we prove that 6-coloring is NP-complete for P7-free graphs. This problem was known to be polynomially solvable for P5-free graphs and NP-complete for P8-free graphs, so there remains one open case.

AB - We prove three complexity results on vertex coloring problems restricted to $P_k$-free graphs, i.e., graphs that do not contain a path on k vertices as an induced subgraph. First of all, we show that the pre-coloring extension version of 5-coloring remains NP-complete when restricted to P6-free graphs. Recent results of Hoàng et al. imply that this problem is polynomially solvable on P5-free graphs. Secondly, we show that the pre-coloring extension version of 3-coloring is polynomially solvable for P6-free graphs. This implies a simpler algorithm for checking the 3-colorability of P6-free graphs than the algorithm given by Randerath and Schiermeyer. Finally, we prove that 6-coloring is NP-complete for P7-free graphs. This problem was known to be polynomially solvable for P5-free graphs and NP-complete for P8-free graphs, so there remains one open case.

KW - EWI-22741

KW - MSC-05C

KW - Induced subgraph

KW - Computational Complexity

KW - Coloring

KW - H-free graph

U2 - 10.1016/j.ejc.2011.12.008

DO - 10.1016/j.ejc.2011.12.008

M3 - Article

VL - 34

SP - 609

EP - 619

JO - European journal of combinatorics

JF - European journal of combinatorics

SN - 0195-6698

IS - 3

ER -