Complexity of coloring graphs without paths and cycles

详细信息    查看全文

• 作者：Pavol Hell ^pavol@sfu.ca ; Shenwei Huang ; ^{shenweih@sfu.ca}
• 关键词：Coloring ; Certifying algorithms ; Paths and cycles ; NP-complete ; Obstructions
• 刊名：Discrete Applied Mathematics
• 出版年：2017
• 出版时间：10 January 2017
• 年：2017
• 卷：216
• 期：part_P1
• 页码：211-232
• 全文大小：1178 K
• 卷排序：216

文摘

Let PtPt and CℓCℓ denote a path on tt vertices and a cycle on ℓℓ vertices, respectively. In this paper we study the kk-coloring problem for (Pt,Cℓ)(Pt,Cℓ)-free graphs. Bruce et al. (2009), and Maffray and Morel (2012) have proved that 3-colorability of P5P5-free graphs has a finite forbidden induced subgraphs characterization, while Hoàng et al. (2015) have shown that kk-colorability of P5P5-free graphs for k≥4k≥4 does not. These authors have also shown, aided by a computer search, that 4-colorability of (P5,C5)(P5,C5)-free graphs does have a finite forbidden induced subgraph characterization.We prove that for any k≥1k≥1, the kk-colorability of (P6,C4)(P6,C4)-free graphs has a finite forbidden induced subgraph characterization. For k=3k=3 and k=4k=4, we provide the full lists of minimal forbidden induced subgraphs. As an application, we obtain certifying polynomial time algorithms for 3-coloring and 4-coloring (P6,C4)(P6,C4)-free graphs. (Polynomial time algorithms have been previously obtained by Golovach, Paulusma, and Song, but those algorithms are not certifying.) To complement these results we show that in most other cases the kk-coloring problem for (Pt,Cℓ)(Pt,Cℓ)-free graphs is NP-complete. Specifically, we prove that the kk-coloring problem is NP-complete for (Pt,Cℓ)(Pt,Cℓ)-free graphs when –ℓ=5ℓ=5, k≥4k≥4, and t≥7t≥7.–ℓ≥6ℓ≥6, k≥5k≥5, and t≥6t≥6.–ℓ≥6ℓ≥6 but ℓ≠7ℓ≠7, k=4k=4, and t≥7t≥7.–ℓ≥6ℓ≥6 but ℓ≠9ℓ≠9, k=4k=4, and t≥9t≥9. Our results almost completely classify the complexity for the cases when k≥4,ℓ≥4k≥4,ℓ≥4, and identify the last few open cases.