文摘
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.