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

Abstract

A graph is $k$-vertex-critical if $\chi (G)=k$ but $\chi (G-v)<k$ for all $v\in 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_2,H)$-free graphs for all $k$ when $H$ is isomorphic to any of the following graphs of order $5$: $bull$, $chair$, $claw+P_1$, or $\overline{diamond+P_1}$. The latter three are corollaries of more general results where $H$ is isomorphic to $(m,\ell )$-$squid$ for $m=3,4$ and any $\ell \ge 1$ where an $(m,\ell )$-$squid$ is the graph obtained from an $m$-cycle by attaching $\ell$ 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_2,H)$-free graphs. Further, our structural classifications allow us to exhaustively generate, with aid of computer search, all $k$-vertex-critical $(2P_2,H)$-free graphs for $k\le 7$ when $H=bull$ or $H=(4,1)$-$squid$ (also known as $banner$).

Submitted to IWOCA 2024