Vertex-critical graphs in co-gem-free graphs
<|reference_start|>Vertex-critical graphs in co-gem-free graphs: A graph $G$ 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 (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 $2P_2$, $K_3+P_1$, and $K_4$. For the first two cases we actually prove stronger results when forbidding graphs of order $5$ that contain the graphs of interest as induced subgraphs and 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 actually shows the stronger result that every $(\text{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.<|reference_end|>
@article{beaton2024vertex-critical,
    title={Vertex-critical graphs in co-gem-free graphs},
    author={Iain Beaton and Ben Cameron},
    journal={arXiv preprint arXiv:2408.05027},
    year={2024},
    archivePrefix={arXiv},
    eprint={2408.05027},
    primaryClass={math.CO cs.DM}
}