Improved complexity results on k-coloring P_t-free graphs

DOI10.1016/J.EJC.2015.06.005MaRDI QIDQ499486zbMATH OpenOpenAlexFDO

Authors Shenwei Huang

Publication date 30 September 2015

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

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

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)

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$.

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

Cites work

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

Cited in

(54)

• A complete complexity dichotomy of the edge-coloring problem for all sets of 8-edge forbidden subgraphs
• \(H\)-colouring \(P_t\)-free graphs in subexponential time
• Narrowing Down the Gap on the Complexity of Coloring P k -Free Graphs
• On colouring \((2P_2,H)\)-free and \((P_5,H)\)-free graphs
• Coloring of pseudocubic graphs in three colors
• On 3-coloring of \((2P_4,C_5)\)-free graphs
• On 3-coloring of \((2P_4,C_5)\)-free graphs
• Complexity of coloring graphs without paths and cycles
• The vertex colourability problem for \(\{\text{claw}, \text{butterfly}\}\)-free graphs is polynomial-time solvable
• A complete classification of the complexity of the vertex 3-colourability problem for quadruples of induced 5-vertex prohibitions
• On the complexity of the vertex 3-coloring problem for the hereditary graph classes with forbidden subgraphs of small size
• Four-Coloring \(\boldsymbol{P_6}\)-Free Graphs. II. Finding an Excellent Precoloring
• Connected greedy coloring of \(H\)-free graphs
• \(P_4\)-colorings and \(P_4\)-bipartite graphs
• Complexity of \(C_k\)-coloring in hereditary classes of graphs
• 3-colorability \(\in\mathrm{P}\) for \(P_{6}\)-free graphs
• List 3-coloring graphs with no induced \(P_6 + rP_3\)
• A survey on the computational complexity of coloring graphs with forbidden subgraphs
• An intractability result for the vertex 3-colourability problem
• Colouring \((P_r + P_s)\)-free graphs
• Covering minimal separators and potential maximal cliques in \(P_t\)-free graphs
• The complexity of the vertex 3-colorability problem for some hereditary classes defined by 5-vertex forbidden induced subgraphs
• Three complexity results on coloring \(P _{k }\)-free graphs
• Vertex-critical \(( P_3 + \ell P_1 )\)-free and vertex-critical (gem, co-gem)-free graphs
• A refinement on the structure of vertex-critical \((P_5, \mathrm{gem})\)-free graphs
• Classifying \(k\)-edge colouring for \(H\)-free graphs
• Colouring (P_r+P_s)-Free Graphs
• scientific article; zbMATH DE number 7525468 (Why is no real title available?)
• Structural domination and coloring of some \(( P_7 , C_7)\)-free graphs
• List 3-coloring \(P_t\)-free graphs with no induced 1-subdivision of \(K_{1 , s}\)
• 4-coloring \((P_6, \text{bull})\)-free graphs
• scientific article; zbMATH DE number 7651174 (Why is no real title available?)
• Colouring square-free graphs without long induced paths
• Critical \((P_6, \mathrm{banner})\)-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
• Finding Large $H$-Colorable Subgraphs in Hereditary Graph Classes
• Complete complexity dichotomy for 7-edge forbidden subgraphs in the edge coloring problem
• Complexity of coloring graphs without paths and cycles
• 4-colorability of \(P_6\)-free graphs
• Three complexity results on coloring \(P_k\)-free graphs
• Two complexity results for the vertex coloring problem
• Complexity dichotomy for list-5-coloring with a forbidden induced subgraph
• Better 3-coloring algorithms: excluding a triangle and a seven vertex path
• Vizing bound for the chromatic number on some graph classes
• List \(k\)-colouring \(P_t\)-free graphs: a mim-width perspective
• 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
• Improved complexity results on \(k\)-coloring \(P _{t }\)-free graphs
• Colouring H-free graphs of bounded diameter.
• Colouring generalized claw-free graphs and graphs of large girth: bounding the diameter
• 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)