On the finiteness of k-vertex-critical 2P₂-free graphs with forbidden induced squids or bulls

A graph is k-vertex-critical if χ(G)=k but χ(G-v)<k for all v∈ V(G) and $(G,H)$-free if it contains no induced subgraph isomorphic to G or H. We show that there are only finitely many k-vertex-critical (2P₂,H)-free graphs for all k when H is isomorphic to any of the following graphs of order $5$: $bull$, $chair$, claw+P₁, or diamond+P₁̄. The latter three are corollaries of more general results where H is isomorphic to (m, )-$squid$ for $m=3,4$ and any ≥ 1 where an (m,)-$squid$ is the graph obtained from an m-cycle by attaching leaves to a single vertex of the cycle. For each of the graphs H above and any fixed k, our results imply the existence of polynomial-time certifying algorithms for deciding the k-colourability problem for (2P₂,H)-free graphs. Further, our structural classifications allow us to exhaustively generate, with aid of computer search, all k-vertex-critical (2P₂,H)-free graphs for k≤ 7 when $H=bull$ or $H=(4,1)$-$squid$ (also known as $banner$).