4‐Coloring P 6 ‐Free Graphs with No Induced 5‐Cycles

DOI10.1002/jgt.22025zbMath1359.05036arXiv1407.2487OpenAlexW2216934276MaRDI QIDQ2978175

Mingxian Zhong, Juraj Stacho, Peter Maceli, Maria Chudnovsky

Publication date: 21 April 2017

Published in: Journal of Graph Theory (Search for Journal in Brave)

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

zbMATH Keywords

algorithmpathinduced subgraphscoloring

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Graph algorithms (graph-theoretic aspects) (05C85) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60)

Related Items (11)

4-colorability of \(P_6\)-free graphs ⋮ Complexity of coloring graphs without paths and cycles ⋮ 4-coloring \((P_6, \text{bull})\)-free graphs ⋮ Colouring square-free graphs without long induced paths. ⋮ Colouring \((P_r + P_s)\)-free graphs ⋮ A Survey on the Computational Complexity of Coloring Graphs with Forbidden Subgraphs ⋮ Improved complexity results on \(k\)-coloring \(P_t\)-free graphs ⋮ Three-coloring and list three-coloring of graphs without induced paths on seven vertices ⋮ On 3-coloring of \((2P_4,C_5)\)-free graphs ⋮ On 3-coloring of \((2P_4,C_5)\)-free graphs ⋮ Colouring (P_r+P_s)-Free Graphs

Cites Work

• 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
• The complexity of colouring problems on dense graphs
• Complement reducible graphs
• A linear-time algorithm for testing the truth of certain quantified Boolean formulas
• 3-colorability \(\in \mathcal P\) for \(P_{6}\)-free graphs.
• Three-colourability and forbidden subgraphs. II: Polynomial algorithms
• Three-coloring and list three-coloring of graphs without induced paths on seven vertices
• Three complexity results on coloring \(P_k\)-free graphs
• Coloring graphs without short cycles and long induced paths
• On the complexity of 4-coloring graphs without long induced paths
• Recognizing Berge graphs
• The NP-Completeness of Edge-Coloring
• NP completeness of finding the chromatic index of regular graphs
• Complexity of Coloring Graphs without Paths and Cycles

This page was built for publication: 4‐Coloring P ₆ ‐Free Graphs with No Induced 5‐Cycles