Improved complexity results on k-coloring P_t-free graphs

DOI10.1016/J.EJC.2015.06.005zbMATH Open1321.05085arXiv1304.5808OpenAlexW1695953772MaRDI QIDQ499486FDOQ499486

Shenwei Huang

Publication date: 30 September 2015

Published in: European Journal of Combinatorics (Search for Journal in Brave)

Abstract: A graph is $H$-free if it does not contain an induced subgraph isomorphic to $H$. We denote by $P_k$ and $C_k$ the path and the cycle on $k$ vertices, respectively. In this paper, we prove that 4-COLORING is NP-complete for $P_7$-free graphs, and that 5-COLORING is NP-complete for $P_6$-free graphs. These two results improve all previous results on $k$-coloring $P_t$-free graphs, and almost complete the classification of complexity of $k$-COLORING $P_t$-free graphs for $kge4$ and $tge1$, leaving as the only missing case 4-COLORING $P_6$-free graphs. We expect that 4-COLORING is polynomial time solvable for $P_6$-free graphs; in support of this, we describe a polynomial time algorithm for 4-COLORING $P_6$-free graphs which are also $P$-free, where $P$ is the graph obtained from $C_4$ by adding a new vertex and making it adjacent to exactly one vertex on the $C_4$.

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

Recommendations

• Improved complexity results on \(k\)-coloring \(P _{t }\)-free graphs
• Narrowing Down the Gap on the Complexity of Coloring P k -Free Graphs
• Three complexity results on coloring \(P _{k }\)-free graphs
• Three complexity results on coloring \(P_k\)-free graphs
• Complexity of coloring graphs without paths and cycles

zbMATH Keywords

4-coloring5-coloring

Mathematics Subject Classification ID

Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Coloring of graphs and hypergraphs (05C15)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Depth-First Search and Linear Graph Algorithms
• The complexity of colouring problems on dense graphs
• Complement reducible graphs
• 3-colorability \(\in \mathcal P\) for \(P_{6}\)-free graphs.
• 4-coloring \(H\)-free graphs when \(H\) is small
• Title not available (Why is that?)
• The NP-Completeness of Edge-Coloring
• Title not available (Why is that?)
• Updating the complexity status of coloring graphs without a fixed induced linear forest
• Deciding \(k\)-colorability of \(P_5\)-free graphs in polynomial time
• The strong perfect graph theorem
• Recognizing Berge graphs
• Graph colorings with local constraints -- a survey
• The complexity of coloring graphs without long induced paths
• Paw-free graphs
• Three complexity results on coloring \(P_k\)-free graphs
• On clique separators, nearly chordal graphs, and the Maximum Weight Stable Set Problem
• NP completeness of finding the chromatic index of regular graphs
• Vertex colouring and forbidden subgraphs -- a survey
• 4‐Coloring P ₆ ‐Free Graphs with No Induced 5‐Cycles
• Coloring edges and vertices of graphs without short or long cycles
• Coloring graphs without short cycles and long induced paths
• On the complexity of 4-coloring graphs without long induced paths
• Closing Complexity Gaps for Coloring Problems on H-Free Graphs
• Colouring vertices of triangle-free graphs without forests
• Stable sets of maximum weight in (\(P_{7}\), banner)-free graphs
• Complexity of Coloring Graphs without Paths and Cycles

Cited In (48)

• Complete complexity dichotomy for $7$-edge forbidden subgraphs in the edge coloring problem
• \(H\)-colouring \(P_t\)-free graphs in subexponential time
• Better 3-coloring algorithms: excluding a triangle and a seven vertex path
• The vertex colourability problem for \(\{\text{claw}, \text{butterfly}\}\)-free graphs is polynomial-time solvable
• On the Complexity of the Vertex 3-Coloring Problem for the Hereditary Graph Classes With Forbidden Subgraphs of Small Size
• A complete classification of the complexity of the vertex 3-colourability problem for quadruples of induced 5-vertex prohibitions
• Title not available (Why is that?)
• Structural domination and coloring of some \(( P_7 , C_7)\)-free graphs
• Title not available (Why is that?)
• Finding Large $H$-Colorable Subgraphs in Hereditary Graph Classes
• Narrowing Down the Gap on the Complexity of Coloring P k -Free Graphs
• Approximately coloring graphs without long induced paths
• Colouring H-free graphs of bounded diameter.
• A refinement on the structure of vertex-critical \((P_5, \mathrm{gem})\)-free graphs
• Complexity of \(C_k\)-coloring in hereditary classes of graphs
• 4-coloring \((P_6, \text{bull})\)-free graphs
• Colouring square-free graphs without long induced paths.
• Certifying coloring algorithms for graphs without long induced paths
• On the chromatic number of (\(P_6\), diamond)-free graphs
• Complexity Dichotomy for List-5-Coloring with a Forbidden Induced Subgraph
• An intractability result for the vertex 3-colourability problem
• Colouring \((P_r + P_s)\)-free graphs
• Three complexity results on coloring \(P _{k }\)-free graphs
• List 3-coloring \(P_t\)-free graphs with no induced 1-subdivision of \(K_{1 , s}\)
• List \(k\)-colouring \(P_t\)-free graphs: a mim-width perspective
• Colouring square-free graphs without long induced paths
• The complexity of the vertex 3-colorability problem for some hereditary classes defined by 5-vertex forbidden induced subgraphs
• A Survey on the Computational Complexity of Coloring Graphs with Forbidden Subgraphs
• Vizing bound for the chromatic number on some graph classes
• Colouring (P_r+P_s)-Free Graphs
• Coloring of pseudocubic graphs in three colors
• Critical \((P_6, \mathrm{banner})\)-free graphs
• Colouring generalized claw-free graphs and graphs of large girth: bounding the diameter
• \(P_4\)-colorings and \(P_4\)-bipartite graphs
• List 3-coloring graphs with no induced \(P_6 + rP_3\)
• Connected greedy coloring of \(H\)-free graphs
• A complete complexity dichotomy of the edge-coloring problem for all sets of 8-edge forbidden subgraphs
• On 3-coloring of \((2P_4,C_5)\)-free graphs
• On 3-coloring of \((2P_4,C_5)\)-free graphs
• Two complexity results for the vertex coloring problem
• Classifying \(k\)-edge colouring for \(H\)-free graphs
• 3-colouring \(P_t\)-free graphs without short odd cycles
• Infinite families of \(k\)-vertex-critical \((P_5, C_5)\)-free graphs
• Four-Coloring \(P_6\)-Free Graphs. I. Extending an Excellent Precoloring
• On colouring \((2P_2,H)\)-free and \((P_5,H)\)-free graphs
• Four-Coloring \(\boldsymbol{P_6}\)-Free Graphs. II. Finding an Excellent Precoloring
• Vertex-critical \(( P_3 + \ell P_1 )\)-free and vertex-critical (gem, co-gem)-free graphs
• On coloring a class of claw-free and hole-twin-free graphs

This page was built for publication: Improved complexity results on \(k\)-coloring \(P_t\)-free graphs

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