Complexity of coloring graphs without paths and cycles

DOI10.1007/978-3-642-54423-1_47MaRDI QIDQ5405071zbMATH OpenOpenAlexFDO

Authors Shenwei Huang, Pavol Hell

Publication date 31 March 2014

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

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

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)

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.

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

Cited in

(12)

• 4‐Coloring P ₆ ‐Free Graphs with No Induced 5‐Cycles
• Coloring graphs without short cycles and long induced paths
• Exhaustive Generation of k-Critical $${\mathcal H}$$ -Free Graphs
• Complexity of coloring graphs without paths and cycles
• On the complexity of 4-coloring graphs without long induced paths
• Obstructions for three-coloring graphs without induced paths on six vertices
• Updating the complexity status of coloring graphs without a fixed induced linear forest
• Colouring square-free graphs without long induced paths
• Colouring square-free graphs without long induced paths
• Certifying coloring algorithms for graphs without long induced paths
• scientific article; zbMATH DE number 1953091 (Why is no real title available?)
• 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)