A certifying algorithm for 3-colorability of P5-free graphs
Daniel Bruce, Chı́nh T. Hoàng, Joe Sawada · arXiv (Cornell University) · 2009
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.