Dichotomizing $k$-vertex-critical $H$-free graphs for $H$ of order four

Abstract

For $k\ge 3$, we prove (i) there is a finite number of $k$-vertex-critical $(P_2+\ell P_1)$-free graphs and (ii) $k$-vertex-critical $(P_3+P_1)$-free graphs have at most $2k-1$ vertices. Together with previous research, these results imply the following characterization where $H$ is a graph of order four: There is a finite number of $k$-vertex-critical $H$-free graphs for fixed $k\ge 5$ if and only if $H$ is one of $\overline{K_4},P_4,P_2+2P_1$, or $P_3+P_1$. Our results imply the existence of new polynomial-time certifying algorithms for deciding the $k$-colorability of $(P_2+\ell P_1)$-free graphs for fixed $k$.

References in corpus (1)

• $k$-Critical Graphs in $P_5$-Free Graphs