View PDF HTML (experimental)

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$\}$.

Submission history

From: Manoj Belavadi [view email]
[v1] Wed, 10 Jun 2026 07:31:54 UTC (13 KB)
[v2] Thu, 11 Jun 2026 09:53:14 UTC (13 KB)
[v3] Mon, 10 Aug 2026 13:42:42 UTC (72 KB)