### Abstract

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

Title of host publication | Combinatioral Algorithms - Proceedings of the 20th International Workshop , IWOCA 2009 |

Editors | Jiri Fiala, Jan Kratochvil, Mirka Miller |

Place of Publication | Berlin |

Publisher | Springer |

Pages | 95-104 |

Number of pages | 10 |

ISBN (Print) | 978-3-642-10216-5 |

DOIs | |

Publication status | Published - 2009 |

### Publication series

Name | Lecture Notes in Computer Science |
---|---|

Publisher | Springer Verlag |

Volume | 5874 |

ISSN (Print) | 0302-9743 |

ISSN (Electronic) | 1611-3349 |

### Keywords

- METIS-266491
- IR-71249
- EWI-17840
- Computational Complexity
- Pk-free graph
- Graph coloring

### Cite this

*Combinatioral Algorithms - Proceedings of the 20th International Workshop , IWOCA 2009*(pp. 95-104). [10.1007/978-3-642-10217-2_12] (Lecture Notes in Computer Science; Vol. 5874). Berlin: Springer. https://doi.org/10.1007/978-3-642-10217-2_12

}

*Combinatioral Algorithms - Proceedings of the 20th International Workshop , IWOCA 2009.*, 10.1007/978-3-642-10217-2_12, Lecture Notes in Computer Science, vol. 5874, Springer, Berlin, pp. 95-104. https://doi.org/10.1007/978-3-642-10217-2_12

**Three Complexity Results on Coloring $P_k$-Free Graphs.** / Broersma, Haitze J.; Fomin, Fedor V.; Golovach, Petr A.; Paulusma, Daniël.

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

TY - GEN

T1 - Three Complexity Results on Coloring $P_k$-Free Graphs

AU - Broersma, Haitze J.

AU - Fomin, Fedor V.

AU - Golovach, Petr A.

AU - Paulusma, Daniël

PY - 2009

Y1 - 2009

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 $P_6$-ree graphs. Recent results of Hoàng et al. imply that this problem is polynomially solvable on $P_5$-free graphs. Secondly, we show that the pre-coloring extension version of 3-coloring is polynomially solvable for $P_6$-free graphs. This implies a simpler algorithm for checking the 3-colorability of $P_6$-free graphs than the algorithm given by Randerath and Schiermeyer. Finally, we prove that 6-coloring is NP-complete for $P_7$-free graphs. This problem was known to be polynomially solvable for $P_5$-free graphs and NP-complete for $P_8$-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 $P_6$-ree graphs. Recent results of Hoàng et al. imply that this problem is polynomially solvable on $P_5$-free graphs. Secondly, we show that the pre-coloring extension version of 3-coloring is polynomially solvable for $P_6$-free graphs. This implies a simpler algorithm for checking the 3-colorability of $P_6$-free graphs than the algorithm given by Randerath and Schiermeyer. Finally, we prove that 6-coloring is NP-complete for $P_7$-free graphs. This problem was known to be polynomially solvable for $P_5$-free graphs and NP-complete for $P_8$-free graphs, so there remains one open case.

KW - METIS-266491

KW - IR-71249

KW - EWI-17840

KW - Computational Complexity

KW - Pk-free graph

KW - Graph coloring

U2 - 10.1007/978-3-642-10217-2_12

DO - 10.1007/978-3-642-10217-2_12

M3 - Conference contribution

SN - 978-3-642-10216-5

T3 - Lecture Notes in Computer Science

SP - 95

EP - 104

BT - Combinatioral Algorithms - Proceedings of the 20th International Workshop , IWOCA 2009

A2 - Fiala, Jiri

A2 - Kratochvil, Jan

A2 - Miller, Mirka

PB - Springer

CY - Berlin

ER -