Three Complexity Results on Coloring $P_k$-Free Graphs

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

doi:10.1007/978-3-642-10217-2_12

Three Complexity Results on Coloring $P_k$-Free Graphs

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

Discrete Mathematics and Mathematical Programming

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-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 language	Undefined
Title of host publication	Combinatioral Algorithms - Proceedings of the 20th International Workshop , IWOCA 2009
Editors	Jiri Fiala, Jan Kratochvil, Mirka Miller
Place of Publication	Berlin
Publisher	Springer
Pages	95-104
Number of pages	10
ISBN (Print)	978-3-642-10216-5
DOIs	https://doi.org/10.1007/978-3-642-10217-2_12
Publication status	Published - 2009
Event	20th International Workshop on Combinatioral Algorithms, IWOCA 2009 - Hradec nad Moravicí, Czech Republic, Hradec nad Moravicí, Czech Republic Duration: 28 Jun 2009 → 2 Jul 2009 Conference number: 20

Publication series

Name	Lecture Notes in Computer Science
Publisher	Springer Verlag
Volume	5874
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	20th International Workshop on Combinatioral Algorithms, IWOCA 2009
Abbreviated title	IWOCA 2009
Country/Territory	Czech Republic
City	Hradec nad Moravicí
Period	28/06/09 → 2/07/09
Other	28 June - 2 July 2009

Keywords

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

Access to Document

10.1007/978-3-642-10217-2_12

http://eprints.eemcs.utwente.nl/secure2/17840/01/6512.0.fulltext.pdf

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). Springer. https://doi.org/10.1007/978-3-642-10217-2_12

@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",

note = "null ; Conference date: 28-06-2009 Through 02-07-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, 20th International Workshop on Combinatioral Algorithms, IWOCA 2009, Hradec nad Moravicí, Czech Republic, 28/06/09. 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. et al.

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 proceeding › Conference contribution › Academic › peer-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

N1 - Conference code: 20

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

Y2 - 28 June 2009 through 2 July 2009

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). doi: 10.1007/978-3-642-10217-2_12