Complexity of coloring graphs without paths and cycles

DOI10.1007/978-3-642-54423-1_47zbMATH Open1405.68140arXiv1310.0340OpenAlexW1500269355MaRDI QIDQ5405071FDOQ5405071

Authors: Shenwei Huang, Pavol Hell 

Publication date: 31 March 2014

Published in: LATIN 2014: Theoretical Informatics (Search for Journal in Brave)

Abstract: Let $P_t$ and $C_{e}ll$ denote a path on $t$ vertices and a cycle on $ell$ vertices, respectively. In this paper we study the $k$-coloring problem for $(P_t,C_{e}ll)$-free graphs. Maffray and Morel, and Bruce, Hoang and Sawada, have proved that 3-colorability of $P_5$-free graphs has a finite forbidden induced subgraphs characterization, while Hoang, Moore, Recoskie, Sawada, and Vatshelle have shown that $k$-colorability of $P_5$-free graphs for $kgeq4$ does not. These authors have also shown, aided by a computer search, that 4-colorability of $(P_5,C_5)$-free graphs does have a finite forbidden induced subgraph characterization. We prove that for any $k$, the $k$-colorability of $(P_6,C_4)$-free graphs has a finite forbidden induced subgraph characterization. We provide the full lists of forbidden induced subgraphs for $k=3$ and $k=4$. As an application, we obtain certifying polynomial time algorithms for 3-coloring and 4-coloring $(P_6,C_4)$-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 $(P_t,C_{e}ll)$-free graphs is NP-complete. Specifically, for $ell=5$ we show that $k$-coloring is NP-complete for $(P_t,C_5)$-free graphs when $kge4$ and $tge7$; for $ellge6$ we show that $k$-coloring is NP-complete for $(P_t,C_{e}ll)$-free graphs when $kge5$, $tge6$; and additionally, for $ell=7$, we show that $k$-coloring is also NP-complete for $(P_t,C_7)$-free graphs if $k=4$ and $tge9$. This is the first systematic study of the complexity of the $k$-coloring problem for $(P_t,C_{e}ll)$-free graphs. We almost completely classify the complexity for the cases when $kgeq4,ellgeq4$, and identify the last three open cases.

Full work available at URL: https://arxiv.org/abs/1310.0340

Recommendations

• Complexity of coloring graphs without paths and cycles
• Improved complexity results on \(k\)-coloring \(P _{t }\)-free graphs
• Improved complexity results on \(k\)-coloring \(P_t\)-free graphs
• Three complexity results on coloring \(P _{k }\)-free graphs
• Three complexity results on coloring \(P_k\)-free graphs

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Coloring of graphs and hypergraphs (05C15)

Cited In (12)

• Colouring square-free graphs without long induced paths
• Title not available (Why is that?)
• Coloring graphs without short cycles and long induced paths
• On the complexity of 4-coloring graphs without long induced paths
• Updating the complexity status of coloring graphs without a fixed induced linear forest
• Certifying coloring algorithms for graphs without long induced paths
• Obstructions for three-coloring graphs without induced paths on six vertices
• Colouring square-free graphs without long induced paths
• Complexity of coloring graphs without paths and cycles
• Exhaustive Generation of k-Critical $${\mathcal H}$$ -Free Graphs
• 4‐Coloring P ₆ ‐Free Graphs with No Induced 5‐Cycles
• Improved complexity results on \(k\)-coloring \(P_t\)-free graphs

This page was built for publication: Complexity of coloring graphs without paths and cycles

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5405071)