Complexity of coloring graphs without paths and cycles

DOI10.1016/j.dam.2015.10.024zbMath1350.05037OpenAlexW2204215863MaRDI QIDQ344861

Shenwei Huang, Pavol Hell

Publication date: 24 November 2016

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.dam.2015.10.024

zbMATH Keywords

pathscyclesobstructionsNP-completenesscoloringcertifying algorithms

Mathematics Subject Classification ID

Paths and cycles (05C38) Coloring of graphs and hypergraphs (05C15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (22)

The vertex colourability problem for \(\{\text{claw}, \text{butterfly}\}\)-free graphs is polynomial-time solvable ⋮ Dichotomizing \(k\)-vertex-critical \(H\)-free graphs for \(H\) of order four ⋮ An intractability result for the vertex 3-colourability problem ⋮ Colouring square-free graphs without long induced paths. ⋮ Certifying coloring algorithms for graphs without long induced paths ⋮ Vertex-critical \((P_5, \mathrm{chair})\)-free graphs ⋮ Critical (\(P_5\), bull)-free graphs ⋮ Some results on \(k\)-critical \(P_5\)-free graphs ⋮ Vertex-critical \(( P_3 + \ell P_1 )\)-free and vertex-critical (gem, co-gem)-free graphs ⋮ 3-colouring \(P_t\)-free graphs without short odd cycles ⋮ On colouring \((2P_2,H)\)-free and \((P_5,H)\)-free graphs ⋮ A Survey on the Computational Complexity of Coloring Graphs with Forbidden Subgraphs ⋮ Better 3-coloring algorithms: excluding a triangle and a seven vertex path ⋮ Critical vertices and edges in \(H\)-free graphs ⋮ Critical \((P_6, \mathrm{banner})\)-free graphs ⋮ The computational complexity of weighted vertex coloring for \(\{P_5,K_{2,3},K^+_{2,3}\}\)-free graphs ⋮ \(k\)-critical graphs in \(P_5\)-free graphs ⋮ On 3-coloring of \((2P_4,C_5)\)-free graphs ⋮ \(k\)-critical graphs in \(P_5\)-free graphs ⋮ Obstructions for Three-Coloring and List Three-Coloring $H$-Free Graphs ⋮ On 3-coloring of \((2P_4,C_5)\)-free graphs ⋮ Colouring square-free graphs without long induced paths

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• 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
• Decomposition by clique separators
• 3-colorability \(\in \mathcal P\) for \(P_{6}\)-free graphs.
• Vertex colouring and forbidden subgraphs -- a survey
• Three complexity results on coloring \(P_k\)-free graphs
• Constructions of \(k\)-critical \(P_5\)-free graphs
• Coloring graphs without short cycles and long induced paths
• On clique separators, nearly chordal graphs, and the Maximum Weight Stable Set Problem
• On the complexity of 4-coloring graphs without long induced paths
• Improved Complexity Results on k-Coloring P t -Free Graphs
• Linear Time Algorithm for Computing a Small Biclique in Graphs without Long Induced Paths
• 4‐Coloring P ₆ ‐Free Graphs with No Induced 5‐Cycles
• Graph Theory and Probability. II
• A Certifying Algorithm for 3-Colorability of P 5-Free Graphs
• The NP-Completeness of Edge-Coloring
• Graph colorings with local constraints -- a survey
• NP completeness of finding the chromatic index of regular graphs
• On $3$-Colorable $P_5$-Free Graphs
• The complexity of satisfiability problems

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