Vertex-critical (P5,chair)-free and (P5,cricket)-free graphs

For graphs G , F 1 and F 2 , we say that G is ( F 1 , F 2 ) -free if neither F 1 nor F 2 is an induced subgraph of G . We say that G is k -vertex-critical if the chromatic number of G is k , but every proper induced subgraph of G has chromatic number at most k − 1 . The chair graph is a 5-vertex graph obtained by adding a pendant vertex to one of the two central vertices of a path on 4 vertices. The cricket graph is a 5-vertex graph obtained by adding two pendant vertices to a common vertex of a triangle. The path on 5 vertices is denoted by P 5 . We prove that for every k ≥ 1 , there are only finitely many ( P 5 , chair ) -free k -vertex-critical graphs. We also prove that the same conclusion holds if chair is replaced by cricket. We further characterize all 5-vertex-critical ( P 5 , chair ) -free graphs, all 5-vertex-critical ( P 5 , cricket ) -free graphs and all 6-vertex-critical ( P 5 , cricket ) -free graphs. Our proofs rely on bounding the size of antichains and developing Ramsey-theoretic ideas. For any fixed integer k ≥ 1 , our results imply the existence of a polynomial time algorithm to decide whether a ( P 5 , chair ) -free (or ( P 5 , cricket ) -free) graph is ( k − 1 ) -colourable such that this algorithm can also present a negative constant-size certificate in case the graph is not ( k − 1 ) -colourable.