3-Colorable Subclasses of $P_8$-Free Graphs

DOI10.1137/16M1104858zbMath1387.05084OpenAlexW2803695018MaRDI QIDQ4641762

Juraj Stacho, Maria Chudnovsky

Publication date: 18 May 2018

Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/16m1104858

zbMATH Keywords

forbidden induced subgraphscoloringinduced paths

Mathematics Subject Classification ID

Paths and cycles (05C38) Coloring of graphs and hypergraphs (05C15)

Related Items (8)

Colouring \((P_r + P_s)\)-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 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 ⋮ Colouring square-free graphs without long induced paths ⋮ Erdős-Gyárfás conjecture for \(P_8\)-free graphs

Uses Software

• CriticalPfreeGraphs

Cites Work

• The strong perfect graph theorem
• 3-colorability \(\in \mathcal P\) for \(P_{6}\)-free graphs.
• Three-coloring and list three-coloring of graphs without induced paths on seven vertices
• Coloring graphs without short cycles and long induced paths
• A Survey on the Computational Complexity of Coloring Graphs with Forbidden Subgraphs
• A Certifying Algorithm for 3-Colorability of P 5-Free Graphs
• The NP-Completeness of Edge-Coloring
• Obstructions for three-coloring graphs with one forbidden induced subgraph
• Exhaustive generation of k‐critical ‐free graphs
• Unnamed Item
• Unnamed Item

This page was built for publication: 3-Colorable Subclasses of $P_8$-Free Graphs