Skip to main content

Research Repository

Advanced Search

Three complexity results on coloring Pk-free graphs

Broersma, H. J.; Fomin, F. V.; Golovach, P. A.; Paulusma, D.

Authors

H. J. Broersma

F. V. Fomin

P. A. Golovach



Contributors

J. Fiala
Editor

J. Kratochvíl
Editor

M. Miller
Editor

Abstract

We prove three complexity results on vertex coloring problems restricted to Pk-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.

Citation

Broersma, H. J., Fomin, F. V., Golovach, P. A., & Paulusma, D. (2009). Three complexity results on coloring Pk-free graphs. In J. Fiala, J. Kratochvíl, & M. Miller (Eds.), Combinatorial algorithms : 20th InternationalWorkshop, IWOCA 2009, 28 June - 2 July 2009, Hradec nad Moravicí, Czech Republic ; revised selected papers (95-104). https://doi.org/10.1007/978-3-642-10217-2_12

Conference Name 20th International Workshop on Combinatorial Algorithms (IWOCA 2009)
Conference Location Hradec nad Moravicí, Czech Republic
Start Date Jun 28, 2023
End Date Jul 2, 2009
Publication Date Nov 1, 2009
Deposit Date Dec 15, 2009
Publisher Springer Verlag
Pages 95-104
Series Title Lecture notes in computer science
Series Number 5874
Book Title Combinatorial algorithms : 20th InternationalWorkshop, IWOCA 2009, 28 June - 2 July 2009, Hradec nad Moravicí, Czech Republic ; revised selected papers.
DOI https://doi.org/10.1007/978-3-642-10217-2_12
Keywords Graph coloring, Pk-free graph, Computational complexity.
Public URL https://durham-repository.worktribe.com/output/1159595
Publisher URL http://www.springerlink.com/content/l86r753h15045304/