Obstructions for three-coloring graphs without induced paths on six vertices

DOI10.1016/J.JCTB.2019.04.006MaRDI QIDQ2284725zbMATH OpenOpenAlexWikidataFDO

Authors Maria Chudnovsky, Jan Goedgebeur, Oliver Schaudt, Mingxian Zhong

Publication date 15 January 2020

Published in Journal of Combinatorial Theory. Series B (Search for Journal in Brave)

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

zbMATH Keywords

critical graphforbidden induced pathsgraph coloring

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Enumeration in graph theory (05C30) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60)

Abstract: We prove that there are 24 4-critical $P_6$-free graphs, and give the complete list. We remark that, if $H$ is connected and not a subgraph of $P_6$, there are infinitely many 4-critical $H$-free graphs. Our result answers questions of Golovach et al. and Seymour.

Recommendations

• Obstructions for three-coloring graphs with one forbidden induced subgraph
• Four-coloring \(P_6\)-free graphs
• 4-colorability of P₆-free graphs
• Exhaustive generation of \(k\)-critical \(\mathcal{H}\)-free graphs
• 4-coloring \(H\)-free graphs when \(H\) is small

Cites work

• A certifying algorithm for 3-colorability of \(P _{5}\)-free graphs
• A survey on the computational complexity of coloring graphs with forbidden subgraphs
• Complexity of coloring graphs without paths and cycles
• Constructions of k-critical P₅-free graphs
• Exhaustive generation of \(k\)-critical \(\mathcal{H}\)-free graphs
• Explicit construction of graphs with an arbitrary large girth and of large size
• Graph Theory and Probability
• House of Graphs: a database of interesting graphs
• scientific article; zbMATH DE number 2024859 (Why is no real title available?)
• Obstructions for three-coloring graphs with one forbidden induced subgraph
• Practical graph isomorphism. II.
• The strong perfect graph theorem
• Three-coloring and list three-coloring of graphs without induced paths on seven vertices
• Three-colourability and forbidden subgraphs. II: Polynomial algorithms

Cited in

(21)

• Triangle-free graphs with no six-vertex induced path
• Critical \((P_6, \mathrm{banner})\)-free graphs
• Three-coloring and list three-coloring of graphs without induced paths on seven vertices
• Better 3-coloring algorithms: excluding a triangle and a seven vertex path
• Obstructions for three-coloring graphs with one forbidden induced subgraph
• Obstructions for three-coloring and list three-coloring H-free graphs
• Four-coloring \(P_6\)-free graphs
• \(k\)-critical graphs in \(P_5\)-free graphs
• Strong cliques in diamond-free graphs
• k-critical graphs in P₅-free graphs
• Colouring graphs with no induced six-vertex path or diamond
• Colouring graphs with no induced six-vertex path or diamond
• Infinite families of \(k\)-vertex-critical \((P_5, C_5)\)-free graphs
• Some results on \(k\)-critical \(P_5\)-free graphs
• Vertex-critical graphs in co-gem-free graphs
• On the finiteness of k-vertex-critical 2P₂-free graphs with forbidden induced squids or bulls
• Minimal obstructions to C₅-Coloring in hereditary graph classes
• Minimal obstructions to C₅-coloring in hereditary graph classes
• There are finitely many 5-vertex-critical \((P_6, \mathrm{bull})\)-free graphs
• Three-coloring triangle-free graphs without long forbidden paths
• Dichotomizing \(k\)-vertex-critical \(H\)-free graphs for \(H\) of order four

Describes a project that uses

Uses Software

• nauty
• Traces
• House of Graphs
• OEIS
• CriticalPfreeGraphs

This page was built for publication: Obstructions for three-coloring graphs without induced paths on six vertices

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