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 PkPk-free graphs, i.e., graphs that do not contain a path on kk 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 P6P6-free graphs. Recent results of Hoàng et al. imply that this problem is polynomially solvable on P5P5-free graphs. Secondly, we show that the pre-coloring extension version of 3-coloring is polynomially solvable for P6P6-free graphs. This implies a simpler algorithm for checking the 3-colorability of P6P6-free graphs than the algorithm given by Randerath and Schiermeyer. Finally, we prove that 6-coloring is NP-complete for P7P7-free graphs. This problem was known to be polynomially solvable for P5P5-free graphs and NP-complete for P8P8-free graphs, so there remains one open case.

Citation

Broersma, H., Fomin, F., Golovach, P., & Paulusma, D. (2013). Three complexity results on coloring Pk-free graphs. European Journal of Combinatorics, 34(3), 609-619. https://doi.org/10.1016/j.ejc.2011.12.008

• Journal Article Type: Article
• Publication Date: Apr 1, 2013
• Deposit Date: Mar 11, 2013
• Publicly Available Date: Apr 17, 2013
• Journal: European Journal of Combinatorics
• Print ISSN: 0195-6698
• Electronic ISSN: 1095-9971
• Publisher: Elsevier
• Peer Reviewed: Peer Reviewed
• Volume: 34
• Issue: 3
• Pages: 609-619
• DOI: https://doi.org/10.1016/j.ejc.2011.12.008
• Public URL: https://durham-repository.worktribe.com/output/1466833