Three complexity results on coloring Pk-free graphs

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

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. (2023, June). Three complexity results on coloring Pk-free graphs. Presented at 20th International Workshop on Combinatorial Algorithms (IWOCA 2009), Hradec nad Moravicí, Czech Republic

• Presentation Conference Type: Conference Paper (published)
• Conference Name: 20th International Workshop on Combinatorial Algorithms (IWOCA 2009)
• Start Date: Jun 28, 2023
• End Date: Jul 2, 2009
• Publication Date: Nov 1, 2009
• Deposit Date: Dec 15, 2009
• Print ISSN: 0302-9743
• 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/