Paper Info
Title
Complexity of Coloring Graphs without Paths and Cycles.
Abstract
Let Pt and Cℓ denote a path on t vertices and a cycle on ℓ vertices, respectively. In this paper we study the k-coloring problem for (Pt,Cℓ)-free graphs. Bruce et al. (2009), and Maffray and Morel (2012) have proved that 3-colorability of P5-free graphs has a finite forbidden induced subgraphs characterization, while Hoàng et al. (2015) have shown that k-colorability of P5-free graphs for k≥4 does not. These authors have also shown, aided by a computer search, that 4-colorability of (P5,C5)-free graphs does have a finite forbidden induced subgraph characterization.
Year
DOI
Venue
2014
10.1016/j.dam.2015.10.024
Discrete Applied Mathematics
Keywords
DocType
Volume
Coloring,Certifying algorithms,Paths and cycles,NP-complete,Obstructions
Conference
216
ISSN
Citations 
PageRank 
0166-218X
8
0.65
References 
Authors
16
2
Name
Order
Citations
PageRank
Pavol Hell12638288.75
Shenwei Huang2312.89