Narrowing down the gap on the complexity of coloring Pk-free graphs

Hajo Broersma; Petr A. Golovach; Daniël Paulusma; Jian Song

doi:10.1007/978-3-642-16926-7_8

Narrowing down the gap on the complexity of coloring P_k-free graphs

Hajo Broersma^*, Petr A. Golovach, Daniël Paulusma, Jian Song

^*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

2 Citations (Scopus)

Abstract

A graph is P_k-free if it does not contain an induced subgraph isomorphic to a path on k vertices. We show that deciding whether a P ₈-free graph can be colored with at most four colors is an NP-complete problem. This improves a result of Le, Randerath, and Schiermeyer, who showed that 4-coloring is NP-complete for P₉-free graphs, and a result of Woeginger and Sgall, who showed that 5-coloring is NP-complete for P₈-free graphs. Additionally, we prove that the pre-coloring extension version of 4-coloring is NP-complete for P₇-free graphs, but that the pre-coloring extension version of 3-coloring is polynomially solvable for (P₂ + P₄)-free graphs, a subclass of P ₇-free graphs.

Original language	English
Title of host publication	Graph-Theoretic Concepts in Computer Science - 36th International Workshop, WG 2010, Revised Papers
Pages	63-74
Number of pages	12
DOIs	https://doi.org/10.1007/978-3-642-16926-7_8
Publication status	Published - 2010
Externally published	Yes
Event	36th International Workshop on Graph-Theoretic Concepts in Computer Science, WG 2010 - Zaros, Crete, Greece Duration: 28 Jun 2010 → 30 Jun 2010 Conference number: 36

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	6410 LNCS
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	36th International Workshop on Graph-Theoretic Concepts in Computer Science, WG 2010
Abbreviated title	WG 2010
Country/Territory	Greece
City	Zaros, Crete
Period	28/06/10 → 30/06/10

Keywords

n/a OA procedure

Access to Document

10.1007/978-3-642-16926-7_8

Cite this

Broersma, H., Golovach, P. A., Paulusma, D., & Song, J. (2010). Narrowing down the gap on the complexity of coloring P_k-free graphs. In Graph-Theoretic Concepts in Computer Science - 36th International Workshop, WG 2010, Revised Papers (pp. 63-74). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 6410 LNCS). https://doi.org/10.1007/978-3-642-16926-7_8

Broersma, Hajo ; Golovach, Petr A. ; Paulusma, Daniël et al. / Narrowing down the gap on the complexity of coloring P_k-free graphs. Graph-Theoretic Concepts in Computer Science - 36th International Workshop, WG 2010, Revised Papers. 2010. pp. 63-74 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{9537f5a4986a46e194f5afd2b4494845,

title = "Narrowing down the gap on the complexity of coloring Pk-free graphs",

abstract = "A graph is Pk-free if it does not contain an induced subgraph isomorphic to a path on k vertices. We show that deciding whether a P 8-free graph can be colored with at most four colors is an NP-complete problem. This improves a result of Le, Randerath, and Schiermeyer, who showed that 4-coloring is NP-complete for P9-free graphs, and a result of Woeginger and Sgall, who showed that 5-coloring is NP-complete for P8-free graphs. Additionally, we prove that the pre-coloring extension version of 4-coloring is NP-complete for P7-free graphs, but that the pre-coloring extension version of 3-coloring is polynomially solvable for (P2 + P4)-free graphs, a subclass of P 7-free graphs.",

keywords = "n/a OA procedure",

author = "Hajo Broersma and Golovach, \{Petr A.\} and Dani{\"e}l Paulusma and Jian Song",

year = "2010",

doi = "10.1007/978-3-642-16926-7\_8",

language = "English",

isbn = "3642169252",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

pages = "63--74",

booktitle = "Graph-Theoretic Concepts in Computer Science - 36th International Workshop, WG 2010, Revised Papers",

note = "36th International Workshop on Graph-Theoretic Concepts in Computer Science, WG 2010, WG 2010 ; Conference date: 28-06-2010 Through 30-06-2010",

}

Broersma, H, Golovach, PA, Paulusma, D & Song, J 2010, Narrowing down the gap on the complexity of coloring P_k-free graphs. in Graph-Theoretic Concepts in Computer Science - 36th International Workshop, WG 2010, Revised Papers. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 6410 LNCS, pp. 63-74, 36th International Workshop on Graph-Theoretic Concepts in Computer Science, WG 2010, Zaros, Crete, Greece, 28/06/10. https://doi.org/10.1007/978-3-642-16926-7_8

Narrowing down the gap on the complexity of coloring P_k-free graphs. / Broersma, Hajo; Golovach, Petr A.; Paulusma, Daniël et al.
Graph-Theoretic Concepts in Computer Science - 36th International Workshop, WG 2010, Revised Papers. 2010. p. 63-74 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 6410 LNCS).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

TY - GEN

T1 - Narrowing down the gap on the complexity of coloring Pk-free graphs

AU - Broersma, Hajo

AU - Golovach, Petr A.

AU - Paulusma, Daniël

AU - Song, Jian

N1 - Conference code: 36

PY - 2010

Y1 - 2010

N2 - A graph is Pk-free if it does not contain an induced subgraph isomorphic to a path on k vertices. We show that deciding whether a P 8-free graph can be colored with at most four colors is an NP-complete problem. This improves a result of Le, Randerath, and Schiermeyer, who showed that 4-coloring is NP-complete for P9-free graphs, and a result of Woeginger and Sgall, who showed that 5-coloring is NP-complete for P8-free graphs. Additionally, we prove that the pre-coloring extension version of 4-coloring is NP-complete for P7-free graphs, but that the pre-coloring extension version of 3-coloring is polynomially solvable for (P2 + P4)-free graphs, a subclass of P 7-free graphs.

AB - A graph is Pk-free if it does not contain an induced subgraph isomorphic to a path on k vertices. We show that deciding whether a P 8-free graph can be colored with at most four colors is an NP-complete problem. This improves a result of Le, Randerath, and Schiermeyer, who showed that 4-coloring is NP-complete for P9-free graphs, and a result of Woeginger and Sgall, who showed that 5-coloring is NP-complete for P8-free graphs. Additionally, we prove that the pre-coloring extension version of 4-coloring is NP-complete for P7-free graphs, but that the pre-coloring extension version of 3-coloring is polynomially solvable for (P2 + P4)-free graphs, a subclass of P 7-free graphs.

KW - n/a OA procedure

UR - https://www.scopus.com/pages/publications/78650208545

U2 - 10.1007/978-3-642-16926-7_8

DO - 10.1007/978-3-642-16926-7_8

M3 - Conference contribution

AN - SCOPUS:78650208545

SN - 3642169252

SN - 9783642169250

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 63

EP - 74

BT - Graph-Theoretic Concepts in Computer Science - 36th International Workshop, WG 2010, Revised Papers

T2 - 36th International Workshop on Graph-Theoretic Concepts in Computer Science, WG 2010

Y2 - 28 June 2010 through 30 June 2010

ER -

Broersma H, Golovach PA, Paulusma D, Song J. Narrowing down the gap on the complexity of coloring P_k-free graphs. In Graph-Theoretic Concepts in Computer Science - 36th International Workshop, WG 2010, Revised Papers. 2010. p. 63-74. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-642-16926-7_8