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.

Three complexity results on coloring Pk-free graphs Thumbnail


Authors

H.J. Broersma

F.V. Fomin

P.A. Golovach



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 Mar 28, 2024
Journal European Journal of Combinatorics
Print ISSN 0195-6698
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

Files

Accepted Journal Article (359 Kb)
PDF

Copyright Statement
NOTICE: this is the author’s version of a work that was accepted for publication in European journal of combinatorics. Changes resulting from the publishing process, such as peer review, editing, corrections, structural formatting, and other quality control mechanisms may not be reflected in this document. Changes may have been made to this work since it was submitted for publication. A definitive version was subsequently published in European journal of combinatorics, 34, 3, 2013, 10.1016/j.ejc.2011.12.008





You might also like



Downloadable Citations