کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4949896 | 1364262 | 2017 | 22 صفحه PDF | دانلود رایگان |
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.We prove that for any kâ¥1, the k-colorability of (P6,C4)-free graphs has a finite forbidden induced subgraph characterization. For k=3 and k=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)-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 k-coloring problem for (Pt,Câ)-free graphs is NP-complete. Specifically, we prove that the k-coloring problem is NP-complete for (Pt,Câ)-free graphs when -â=5, kâ¥4, and tâ¥7.-ââ¥6, kâ¥5, and tâ¥6.-ââ¥6 but ââ 7, k=4, and tâ¥7.-ââ¥6 but ââ 9, k=4, and tâ¥9. Our results almost completely classify the complexity for the cases when kâ¥4,ââ¥4, and identify the last few open cases.
Journal: Discrete Applied Mathematics - Volume 216, Part 1, 10 January 2017, Pages 211-232