Vertex-critical co-gem-free graphs

Abstract

Given a graph $G$, let $\chi (G)$ denote the chromatic number of $G$. For $k\in \mathbb{N}$, a graph $G$ is $k$-$vertex$-$critical$ if $\chi (G)=k$ and $\chi (G-v)<k$ for all $v\in V(G)$. A recent problem of Beaton and Cameron [TCS 1042 (2025) 115234] asks for which graphs $H$ of order five, are there finitely many $k$-vertex-critical (co-gem, $H$)-free graphs, for all $k\in \mathbb{N}$? Here we identify three distinct graphs on five vertices that yield an affirmative answer to this problem. More precisely, we show that for each $k\in \mathbb{N}$, there are finitely many $k$-vertex-critical (co-gem, $H$)-free graphs, where $H\in \{$paraglider, dart, house$\}$, by analysing the structure of such graphs. Our results together with a result of Couturier et al. [Algorithmica 71:1 (2015) 21--35] imply that for each $k\in \mathbb{N}$, there is a polynomial-time certifying algorithm for $k$-COLORING of (co-gem, $H$)-free graphs, where $H\in \{$paraglider, dart, house$\}$.

15pages