A certifying algorithm for 3-colorability of P5-free graphs
classification
💻 cs.DM
cs.DS
keywords
algorithmcertifyingcolorablegraphsp5-freecolorabilitydecidingexactly
read the original 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.
This paper has not been read by Pith yet.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.