{"id":"arxiv/2606.11757","url":"https://arxiv.org/abs/2606.11757","tags":["math.CO"],"score":0,"title":"Vertex-critical co-gem-free graphs","domain":"math.CO","source":"arxiv","authors":["Manoj Belavadi","T. Karthick"],"reviews":0,"subject":"math.CO","summary":"Given a graph $G$, let $χ(G)$ denote the chromatic number of $G$. For $k\\in \\mathbb{N}$, a graph $G$ is $k$-$vertex$-$critical$ if $χ(G)=k$ and $χ(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,…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-06-10","reactions":{}}