Three complexity results on coloring $P_k$-free graphs

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

Research output: Contribution to journalArticleAcademicpeer-review

17 Citations (Scopus)
9 Downloads (Pure)

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 P6-free graphs. Recent results of Hoàng et al. imply that this problem is polynomially solvable on P5-free graphs. Secondly, we show that the pre-coloring extension version of 3-coloring is polynomially solvable for P6-free graphs. This implies a simpler algorithm for checking the 3-colorability of P6-free graphs than the algorithm given by Randerath and Schiermeyer. Finally, we prove that 6-coloring is NP-complete for P7-free graphs. This problem was known to be polynomially solvable for P5-free graphs and NP-complete for P8-free graphs, so there remains one open case.
Original languageEnglish
Pages (from-to)609-619
Number of pages11
JournalEuropean journal of combinatorics
Volume34
Issue number3
DOIs
Publication statusPublished - 2013

Fingerprint

Colouring
Graph in graph theory
NP-complete problem
Imply
Vertex Coloring
Induced Subgraph
Path

Keywords

  • EWI-22741
  • MSC-05C
  • Induced subgraph
  • Computational Complexity
  • Coloring
  • H-free graph

Cite this

Broersma, Haitze J. ; Fomin, Vedor V. ; Golovach, Petr A. ; Paulusma, Daniël. / Three complexity results on coloring $P_k$-free graphs. In: European journal of combinatorics. 2013 ; Vol. 34, No. 3. pp. 609-619.
@article{02f557ebbe104a12b5da08316f60128a,
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 P6-free graphs. Recent results of Hoàng et al. imply that this problem is polynomially solvable on P5-free graphs. Secondly, we show that the pre-coloring extension version of 3-coloring is polynomially solvable for P6-free graphs. This implies a simpler algorithm for checking the 3-colorability of P6-free graphs than the algorithm given by Randerath and Schiermeyer. Finally, we prove that 6-coloring is NP-complete for P7-free graphs. This problem was known to be polynomially solvable for P5-free graphs and NP-complete for P8-free graphs, so there remains one open case.",
keywords = "EWI-22741, MSC-05C, Induced subgraph, Computational Complexity, Coloring, H-free graph",
author = "Broersma, {Haitze J.} and Fomin, {Vedor V.} and Golovach, {Petr A.} and Dani{\"e}l Paulusma",
year = "2013",
doi = "10.1016/j.ejc.2011.12.008",
language = "English",
volume = "34",
pages = "609--619",
journal = "European journal of combinatorics",
issn = "0195-6698",
publisher = "Academic Press Inc.",
number = "3",

}

Three complexity results on coloring $P_k$-free graphs. / Broersma, Haitze J.; Fomin, Vedor V.; Golovach, Petr A.; Paulusma, Daniël.

In: European journal of combinatorics, Vol. 34, No. 3, 2013, p. 609-619.

Research output: Contribution to journalArticleAcademicpeer-review

TY - JOUR

T1 - Three complexity results on coloring $P_k$-free graphs

AU - Broersma, Haitze J.

AU - Fomin, Vedor V.

AU - Golovach, Petr A.

AU - Paulusma, Daniël

PY - 2013

Y1 - 2013

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

KW - EWI-22741

KW - MSC-05C

KW - Induced subgraph

KW - Computational Complexity

KW - Coloring

KW - H-free graph

U2 - 10.1016/j.ejc.2011.12.008

DO - 10.1016/j.ejc.2011.12.008

M3 - Article

VL - 34

SP - 609

EP - 619

JO - European journal of combinatorics

JF - European journal of combinatorics

SN - 0195-6698

IS - 3

ER -