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

DOI10.1002/JGT.22025MaRDI QIDQ2978175zbMATH OpenOpenAlexFDO

Authors Maria Chudnovsky, Peter Maceli, Juraj Stacho, Mingxian Zhong

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

algorithmcoloringinduced subgraphspath

Mathematics Subject Classification ID

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

Abstract: We show that the 4-coloring problem can be solved in polynomial time for graphs with no induced 5-cycle $C_5$ and no induced 6-vertex path $P_6$.

Cites work

• 3-colorability \(\in \mathcal P\) for \(P_{6}\)-free graphs.
• A linear-time algorithm for testing the truth of certain quantified Boolean formulas
• Coloring graphs without short cycles and long induced paths
• Complement reducible graphs
• Complexity of coloring graphs without paths and cycles
• Deciding \(k\)-colorability of \(P_5\)-free graphs in polynomial time
• Decomposition by clique separators
• scientific article; zbMATH DE number 772747 (Why is no real title available?)
• NP completeness of finding the chromatic index of regular graphs
• On the complexity of 4-coloring graphs without long induced paths
• Recognizing Berge graphs
• The complexity of coloring graphs without long induced paths
• The complexity of colouring problems on dense graphs
• The NP-Completeness of Edge-Coloring
• The strong perfect graph theorem
• Three complexity results on coloring \(P_k\)-free graphs
• Three-coloring and list three-coloring of graphs without induced paths on seven vertices
• Three-colourability and forbidden subgraphs. II: Polynomial algorithms
• Updating the complexity status of coloring graphs without a fixed induced linear forest

Cited in

(12)

• Three-coloring and list three-coloring of graphs without induced paths on seven vertices
• Colouring \((P_r + P_s)\)-free graphs
• 4-coloring \((P_6, \text{bull})\)-free graphs
• A survey on the computational complexity of coloring graphs with forbidden subgraphs
• 4-colorability of P₆-free graphs
• Colouring square-free graphs without long induced paths
• Complexity of coloring graphs without paths and cycles
• Improved complexity results on \(k\)-coloring \(P_t\)-free graphs
• Colouring (P_r+P_s)-Free Graphs
• On 3-coloring of \((2P_4,C_5)\)-free graphs
• On 3-coloring of \((2P_4,C_5)\)-free graphs
• There are finitely many 5-vertex-critical \((P_6, \mathrm{bull})\)-free graphs

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

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