A certifying algorithm for 3-colorability of P5-free graphs

Abstract

We provide a certifying algorithm for the problem of deciding whether a P5- free graph is 3-colorable by showing there are exactly six finite graphs that are P5-free and not 3-colorable and minimal with respect to this property.

Cited by in corpus (7)

• A Survey on the Computational Complexity of Colouring Graphs with Forbidden Subgraphs
• Better 3-coloring algorithms: excluding a triangle and a seven vertex path
• Obstructions for three-coloring graphs without induced paths on six vertices
• Exhaustive generation of $k$-critical $\mathcal{H}$-free graphs
• Critical Vertices and Edges in $H$-free Graphs
• Obstructions for three-coloring and list three-coloring $H$-free graphs
• 4-coloring ($P_6$, bull)-free graphs