Constructions of k k -critical P5 P 5 -free graphs
With respect to a hereditary class C C of graphs, a k k -chromatic graph G?C G ? C is said to be k k -critical  if every proper subgraph of G G belonging to C C is k?1 k ? 1 colorable. It is known that there is a finite number of 4-critical P5 P 5 -free graphs. We construct an infinite set of k k -critical P5 P 5 -free graphs for every k?5 k ? 5 . We also prove that there are exactly eight 5-critical {P5,C5} { P 5 , C 5 } -free graphs and thirteen 5-vertex-critical {P5,C5} { P 5 , C 5 } -free graphs.
graph coloring p5 p 5 -free graphs p5 p 5 p5 p 5 p 5 critical graphs