Three Complexity Results on Coloring $P_k$-Free Graphs

Haitze J. Broersma, Fedor V. Fomin, Petr A. Golovach, Daniël Paulusma

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

15 Citations (Scopus)

Abstract

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.
Original languageUndefined
Title of host publicationCombinatioral Algorithms - Proceedings of the 20th International Workshop , IWOCA 2009
EditorsJiri Fiala, Jan Kratochvil, Mirka Miller
Place of PublicationBerlin
PublisherSpringer
Pages95-104
Number of pages10
ISBN (Print)978-3-642-10216-5
DOIs
Publication statusPublished - 2009

Publication series

NameLecture Notes in Computer Science
PublisherSpringer Verlag
Volume5874
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Keywords

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

Cite this

Broersma, H. J., Fomin, F. V., Golovach, P. A., & Paulusma, D. (2009). Three Complexity Results on Coloring $P_k$-Free Graphs. In J. Fiala, J. Kratochvil, & M. Miller (Eds.), 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
Broersma, Haitze J. ; Fomin, Fedor V. ; Golovach, Petr A. ; Paulusma, Daniël. / Three Complexity Results on Coloring $P_k$-Free Graphs. Combinatioral Algorithms - Proceedings of the 20th International Workshop , IWOCA 2009. editor / Jiri Fiala ; Jan Kratochvil ; Mirka Miller. Berlin : Springer, 2009. pp. 95-104 (Lecture Notes in Computer Science).
@inproceedings{12e81a754eda4240bfd75ca8c94e513a,
title = "Three Complexity Results on Coloring $P_k$-Free Graphs",
abstract = "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{\`a}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.",
keywords = "METIS-266491, IR-71249, EWI-17840, Computational Complexity, Pk-free graph, Graph coloring",
author = "Broersma, {Haitze J.} and Fomin, {Fedor V.} and Golovach, {Petr A.} and Dani{\"e}l Paulusma",
year = "2009",
doi = "10.1007/978-3-642-10217-2_12",
language = "Undefined",
isbn = "978-3-642-10216-5",
series = "Lecture Notes in Computer Science",
publisher = "Springer",
pages = "95--104",
editor = "Jiri Fiala and Jan Kratochvil and Mirka Miller",
booktitle = "Combinatioral Algorithms - Proceedings of the 20th International Workshop , IWOCA 2009",

}

Broersma, HJ, Fomin, FV, Golovach, PA & Paulusma, D 2009, Three Complexity Results on Coloring $P_k$-Free Graphs. in J Fiala, J Kratochvil & M Miller (eds), 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.

Combinatioral Algorithms - Proceedings of the 20th International Workshop , IWOCA 2009. ed. / Jiri Fiala; Jan Kratochvil; Mirka Miller. Berlin : Springer, 2009. p. 95-104 10.1007/978-3-642-10217-2_12 (Lecture Notes in Computer Science; Vol. 5874).

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-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 -

Broersma HJ, Fomin FV, Golovach PA, Paulusma D. Three Complexity Results on Coloring $P_k$-Free Graphs. In Fiala J, Kratochvil J, Miller M, editors, Combinatioral Algorithms - Proceedings of the 20th International Workshop , IWOCA 2009. Berlin: Springer. 2009. p. 95-104. 10.1007/978-3-642-10217-2_12. (Lecture Notes in Computer Science). https://doi.org/10.1007/978-3-642-10217-2_12