Vertex-critical graphs in co-gem-free graphs

A graph G is k -vertex-critical if χ ( G ) = k but χ ( G − v ) < k for all v ∈ V ( G ) and ( H 1 , H 2 ) -free if it contains no induced subgraph isomorphic to H 1 or H 2 . We show that there are only finitely many k -vertex-critical (co-gem, H )-free graphs for all k when H is any graph of order 4 by showing finiteness in the three remaining open cases, those are the cases when H is 2 P 2 , K 3 + P 1 , and K 4 . For the first two cases we actually prove the stronger results: • There are only finitely many k -vertex-critical (co-gem, paw + P 1 )-free graphs for all k ≥ 1 . • There are only finitely many k -vertex-critical (co-gem, P 5 , P 3 + c P 2 )-free graphs for all k ≥ 1 and c ≥ 0 . To prove the latter result, we employ a novel application of Sperner's Theorem on the number of antichains in a partially ordered set. Our result for K 4 uses exhaustive computer search and is proved by showing the stronger result that every ( co-gem, K 4 ) -free graph is 4-colourable. Our results imply the existence of simple polynomial-time certifying algorithms to decide the k -colourability of (co-gem, H )-free graphs for all k and all H of order 4 by searching the vertex-critical graphs as induced subgraphs.