On coloring graphs without induced forests

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

doi:10.1007/978-3-642-17514-5_14

On coloring graphs without induced forests

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

The ℓ-Coloring problem is the problem to decide whether a graph can be colored with at most ℓ colors. Let P_k denote the path on k vertices and G + H and 2H the disjoint union of two graphs G and H or two copies of H, respectively. We solve a known open problem by showing that 3-Coloring is polynomial-time solvable for the class of graphs with no induced 2P ₃. This implies that the complexity of 3-Coloring for graphs with no induced graph H is now classified for any fixed graph H on at most 6 vertices. The Vertex Coloring problem is the problem to determine the chromatic number of a graph. We show that Vertex Coloring is polynomial-time solvable for the class of triangle-free graphs with no induced 2P₃ and for the class of triangle-free graphs with no induced P₂ + P₄. This solves two open problems of Dabrowski, Lozin, Raman and Ries and implies that the complexity of Vertex Coloring for triangle-free graphs with no induced graph H is now classified for any fixed graph H on at most 6 vertices. Our proof technique for the case H = 2P₃ is based on a novel structural result on the existence of small dominating sets in 2P₃-free graphs that admit a k-coloring for some fixed k.

Original language	English
Title of host publication	Algorithms and Computation - 21st International Symposium, ISAAC 2010, Proceedings
Pages	156-167
Number of pages	12
Edition	PART 2
DOIs	https://doi.org/10.1007/978-3-642-17514-5_14
Publication status	Published - 2010
Externally published	Yes
Event	21st Annual International Symposium on Algorithms and Computations, ISAAC 2010 - Jeju Island, Korea, Republic of Duration: 15 Dec 2010 → 17 Dec 2010 Conference number: 21

Publication series

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

Conference

Conference	21st Annual International Symposium on Algorithms and Computations, ISAAC 2010
Abbreviated title	ISAAC 2010
Country/Territory	Korea, Republic of
City	Jeju Island
Period	15/12/10 → 17/12/10

Keywords

n/a OA procedure

Access to Document

10.1007/978-3-642-17514-5_14

Cite this

Broersma, H., Golovach, P. A., Paulusma, D., & Song, J. (2010). On coloring graphs without induced forests. In Algorithms and Computation - 21st International Symposium, ISAAC 2010, Proceedings (PART 2 ed., pp. 156-167). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 6507 LNCS, No. PART 2). https://doi.org/10.1007/978-3-642-17514-5_14

@inproceedings{094e539c0b27437e9feb1099182d7535,

title = "On coloring graphs without induced forests",

abstract = "The ℓ-Coloring problem is the problem to decide whether a graph can be colored with at most ℓ colors. Let Pk denote the path on k vertices and G + H and 2H the disjoint union of two graphs G and H or two copies of H, respectively. We solve a known open problem by showing that 3-Coloring is polynomial-time solvable for the class of graphs with no induced 2P 3. This implies that the complexity of 3-Coloring for graphs with no induced graph H is now classified for any fixed graph H on at most 6 vertices. The Vertex Coloring problem is the problem to determine the chromatic number of a graph. We show that Vertex Coloring is polynomial-time solvable for the class of triangle-free graphs with no induced 2P3 and for the class of triangle-free graphs with no induced P2 + P4. This solves two open problems of Dabrowski, Lozin, Raman and Ries and implies that the complexity of Vertex Coloring for triangle-free graphs with no induced graph H is now classified for any fixed graph H on at most 6 vertices. Our proof technique for the case H = 2P3 is based on a novel structural result on the existence of small dominating sets in 2P3-free graphs that admit a k-coloring for some fixed k.",

keywords = "n/a OA procedure",

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

note = "Funding Information: This work has been supported by EPSRC (EP/G043434/1).; 21st Annual International Symposium on Algorithms and Computations, ISAAC 2010, ISAAC 2010 ; Conference date: 15-12-2010 Through 17-12-2010",

year = "2010",

doi = "10.1007/978-3-642-17514-5_14",

language = "English",

isbn = "3642175163",

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

number = "PART 2",

pages = "156--167",

booktitle = "Algorithms and Computation - 21st International Symposium, ISAAC 2010, Proceedings",

edition = "PART 2",

}

Broersma, H, Golovach, PA, Paulusma, D & Song, J 2010, On coloring graphs without induced forests. in Algorithms and Computation - 21st International Symposium, ISAAC 2010, Proceedings. PART 2 edn, Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), no. PART 2, vol. 6507 LNCS, pp. 156-167, 21st Annual International Symposium on Algorithms and Computations, ISAAC 2010, Jeju Island, Korea, Republic of, 15/12/10. https://doi.org/10.1007/978-3-642-17514-5_14

On coloring graphs without induced forests. / Broersma, Hajo; Golovach, Petr A.; Paulusma, Daniël et al.
Algorithms and Computation - 21st International Symposium, ISAAC 2010, Proceedings. PART 2. ed. 2010. p. 156-167 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 6507 LNCS, No. PART 2).

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

TY - GEN

T1 - On coloring graphs without induced forests

AU - Broersma, Hajo

AU - Golovach, Petr A.

AU - Paulusma, Daniël

AU - Song, Jian

N1 - Conference code: 21

PY - 2010

Y1 - 2010

N2 - The ℓ-Coloring problem is the problem to decide whether a graph can be colored with at most ℓ colors. Let Pk denote the path on k vertices and G + H and 2H the disjoint union of two graphs G and H or two copies of H, respectively. We solve a known open problem by showing that 3-Coloring is polynomial-time solvable for the class of graphs with no induced 2P 3. This implies that the complexity of 3-Coloring for graphs with no induced graph H is now classified for any fixed graph H on at most 6 vertices. The Vertex Coloring problem is the problem to determine the chromatic number of a graph. We show that Vertex Coloring is polynomial-time solvable for the class of triangle-free graphs with no induced 2P3 and for the class of triangle-free graphs with no induced P2 + P4. This solves two open problems of Dabrowski, Lozin, Raman and Ries and implies that the complexity of Vertex Coloring for triangle-free graphs with no induced graph H is now classified for any fixed graph H on at most 6 vertices. Our proof technique for the case H = 2P3 is based on a novel structural result on the existence of small dominating sets in 2P3-free graphs that admit a k-coloring for some fixed k.

AB - The ℓ-Coloring problem is the problem to decide whether a graph can be colored with at most ℓ colors. Let Pk denote the path on k vertices and G + H and 2H the disjoint union of two graphs G and H or two copies of H, respectively. We solve a known open problem by showing that 3-Coloring is polynomial-time solvable for the class of graphs with no induced 2P 3. This implies that the complexity of 3-Coloring for graphs with no induced graph H is now classified for any fixed graph H on at most 6 vertices. The Vertex Coloring problem is the problem to determine the chromatic number of a graph. We show that Vertex Coloring is polynomial-time solvable for the class of triangle-free graphs with no induced 2P3 and for the class of triangle-free graphs with no induced P2 + P4. This solves two open problems of Dabrowski, Lozin, Raman and Ries and implies that the complexity of Vertex Coloring for triangle-free graphs with no induced graph H is now classified for any fixed graph H on at most 6 vertices. Our proof technique for the case H = 2P3 is based on a novel structural result on the existence of small dominating sets in 2P3-free graphs that admit a k-coloring for some fixed k.

KW - n/a OA procedure

UR - http://www.scopus.com/inward/record.url?scp=78650865692&partnerID=8YFLogxK

U2 - 10.1007/978-3-642-17514-5_14

DO - 10.1007/978-3-642-17514-5_14

M3 - Conference contribution

AN - SCOPUS:78650865692

SN - 3642175163

SN - 9783642175169

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

SP - 156

EP - 167

BT - Algorithms and Computation - 21st International Symposium, ISAAC 2010, Proceedings

T2 - 21st Annual International Symposium on Algorithms and Computations, ISAAC 2010

Y2 - 15 December 2010 through 17 December 2010

ER -

Broersma H, Golovach PA, Paulusma D, Song J. On coloring graphs without induced forests. In Algorithms and Computation - 21st International Symposium, ISAAC 2010, Proceedings. PART 2 ed. 2010. p. 156-167. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); PART 2). doi: 10.1007/978-3-642-17514-5_14

On coloring graphs without induced forests

Abstract

Publication series

Conference

Keywords

Access to Document

Other files and links

Fingerprint

Cite this