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

Daniel Bruce, Chinh T. Hoang, Joe Sawada

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-colo…