Joe Sawada

School of Computer Science, University of Guelph

k-Critical P₅-free Graphs

A P₅ is a chordless path on 5 vertices. The chromatic number problem for P₅-free graphs is known to be NP-hard. However for fixed k, the k-colorability question for P5-free graphs can be answered in polynomial time [Algorithmica (2010) Hoang, Kaminski, Lozin, Sawada, Shu]. If such a graph is k-colorable, then a proper k-coloring is provided; however, if it is not k-colorable, no certificate or minimal obstruction is provided. This motivates studying k-critical P₅-free graphs: those with chromatic number k such that every proper P₅-free subgraph is k-1 colorable. In this talk, we outline the following results:

• There are exactly six 4-critical P₅-free graphs,
• There are an infinite number of 5-critical P₅-free graphs,
• There are exactly eight 5-critical (P₅, C₅)-free graphs.

A number of open problems in this area will also be presented.