Updating the complexity status of coloring graphs without a fixed induced linear forest

Haitze J. Broersma, P.A. Golovach, Daniël Paulusma, Jian Song

Research output: Contribution to journalArticleAcademicpeer-review

34 Citations (Scopus)

Abstract

A graph is H-free if it does not contain an induced subgraph isomorphic to the graph H. The graph Pk denotes a path on k vertices. The ℓ-Coloring problem is the problem to decide whether a graph can be colored with at most ℓ colors such that adjacent vertices receive different colors. We show that 4-Coloring is NP-complete for P8-free graphs. 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 precoloring extension version of 4-Coloring is NP-complete for P7-free graphs, but that the precoloring extension version of 3-Coloring can be solved in polynomial time for (P2+P4)-free graphs, a subclass of P7-free graphs. Here P2+P4 denotes the disjoint union of a P2 and a P4. We denote the disjoint union of s copies of a P3 by sP3 and involve Ramsey numbers to prove that the precoloring extension version of 3-Coloring can be solved in polynomial time for sP3-free graphs for any fixed s. Combining our last two results with known results yields a complete complexity classification of (precoloring extension of) 3-Coloring for H-free graphs when H is a fixed graph on at most 6 vertices: the problem is polynomial-time solvable if H is a linear forest; otherwise it is NP-complete.
Original languageUndefined
Pages (from-to)9-19
Number of pages11
JournalTheoretical computer science
Volume414
Issue number1
DOIs
Publication statusPublished - 13 Jan 2012

Keywords

  • MSC-05C
  • Linear forest
  • EWI-21077
  • METIS-293161
  • Forbidden induced subgraph
  • Graph coloring
  • IR-82685

Cite this

Broersma, Haitze J. ; Golovach, P.A. ; Paulusma, Daniël ; Song, Jian. / Updating the complexity status of coloring graphs without a fixed induced linear forest. In: Theoretical computer science. 2012 ; Vol. 414, No. 1. pp. 9-19.
@article{1f667a22dac3446fa23b7dcc787ac243,
title = "Updating the complexity status of coloring graphs without a fixed induced linear forest",
abstract = "A graph is H-free if it does not contain an induced subgraph isomorphic to the graph H. The graph Pk denotes a path on k vertices. The ℓ-Coloring problem is the problem to decide whether a graph can be colored with at most ℓ colors such that adjacent vertices receive different colors. We show that 4-Coloring is NP-complete for P8-free graphs. 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 precoloring extension version of 4-Coloring is NP-complete for P7-free graphs, but that the precoloring extension version of 3-Coloring can be solved in polynomial time for (P2+P4)-free graphs, a subclass of P7-free graphs. Here P2+P4 denotes the disjoint union of a P2 and a P4. We denote the disjoint union of s copies of a P3 by sP3 and involve Ramsey numbers to prove that the precoloring extension version of 3-Coloring can be solved in polynomial time for sP3-free graphs for any fixed s. Combining our last two results with known results yields a complete complexity classification of (precoloring extension of) 3-Coloring for H-free graphs when H is a fixed graph on at most 6 vertices: the problem is polynomial-time solvable if H is a linear forest; otherwise it is NP-complete.",
keywords = "MSC-05C, Linear forest, EWI-21077, METIS-293161, Forbidden induced subgraph, Graph coloring, IR-82685",
author = "Broersma, {Haitze J.} and P.A. Golovach and Dani{\"e}l Paulusma and Jian Song",
note = "eemcs-eprint-21077",
year = "2012",
month = "1",
day = "13",
doi = "10.1016/j.tcs.2011.10.005",
language = "Undefined",
volume = "414",
pages = "9--19",
journal = "Theoretical computer science",
issn = "0304-3975",
publisher = "Elsevier",
number = "1",

}

Updating the complexity status of coloring graphs without a fixed induced linear forest. / Broersma, Haitze J.; Golovach, P.A.; Paulusma, Daniël; Song, Jian.

In: Theoretical computer science, Vol. 414, No. 1, 13.01.2012, p. 9-19.

Research output: Contribution to journalArticleAcademicpeer-review

TY - JOUR

T1 - Updating the complexity status of coloring graphs without a fixed induced linear forest

AU - Broersma, Haitze J.

AU - Golovach, P.A.

AU - Paulusma, Daniël

AU - Song, Jian

N1 - eemcs-eprint-21077

PY - 2012/1/13

Y1 - 2012/1/13

N2 - A graph is H-free if it does not contain an induced subgraph isomorphic to the graph H. The graph Pk denotes a path on k vertices. The ℓ-Coloring problem is the problem to decide whether a graph can be colored with at most ℓ colors such that adjacent vertices receive different colors. We show that 4-Coloring is NP-complete for P8-free graphs. 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 precoloring extension version of 4-Coloring is NP-complete for P7-free graphs, but that the precoloring extension version of 3-Coloring can be solved in polynomial time for (P2+P4)-free graphs, a subclass of P7-free graphs. Here P2+P4 denotes the disjoint union of a P2 and a P4. We denote the disjoint union of s copies of a P3 by sP3 and involve Ramsey numbers to prove that the precoloring extension version of 3-Coloring can be solved in polynomial time for sP3-free graphs for any fixed s. Combining our last two results with known results yields a complete complexity classification of (precoloring extension of) 3-Coloring for H-free graphs when H is a fixed graph on at most 6 vertices: the problem is polynomial-time solvable if H is a linear forest; otherwise it is NP-complete.

AB - A graph is H-free if it does not contain an induced subgraph isomorphic to the graph H. The graph Pk denotes a path on k vertices. The ℓ-Coloring problem is the problem to decide whether a graph can be colored with at most ℓ colors such that adjacent vertices receive different colors. We show that 4-Coloring is NP-complete for P8-free graphs. 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 precoloring extension version of 4-Coloring is NP-complete for P7-free graphs, but that the precoloring extension version of 3-Coloring can be solved in polynomial time for (P2+P4)-free graphs, a subclass of P7-free graphs. Here P2+P4 denotes the disjoint union of a P2 and a P4. We denote the disjoint union of s copies of a P3 by sP3 and involve Ramsey numbers to prove that the precoloring extension version of 3-Coloring can be solved in polynomial time for sP3-free graphs for any fixed s. Combining our last two results with known results yields a complete complexity classification of (precoloring extension of) 3-Coloring for H-free graphs when H is a fixed graph on at most 6 vertices: the problem is polynomial-time solvable if H is a linear forest; otherwise it is NP-complete.

KW - MSC-05C

KW - Linear forest

KW - EWI-21077

KW - METIS-293161

KW - Forbidden induced subgraph

KW - Graph coloring

KW - IR-82685

U2 - 10.1016/j.tcs.2011.10.005

DO - 10.1016/j.tcs.2011.10.005

M3 - Article

VL - 414

SP - 9

EP - 19

JO - Theoretical computer science

JF - Theoretical computer science

SN - 0304-3975

IS - 1

ER -