On the finiteness of $k$-vertex-critical $2P_2$-free graphs with forbidden induced squids or bulls
<|reference_start|>On the finiteness of $k$-vertex-critical $2P_2$-free graphs with forbidden induced squids or bulls: 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$).<|reference_end|>
@article{adekanye2024on,
    title={On the finiteness of $k$-vertex-critical $2P_2$-free graphs with
  forbidden induced squids or bulls},
    author={Melvin Adekanye, Christopher Bury, Ben Cameron, Thaler Knodel},
    journal={arXiv preprint arXiv:2402.15908},
    year={2024},
    archivePrefix={arXiv},
    eprint={2402.15908},
    primaryClass={math.CO cs.DM}
}