Vertex-critical graphs in subfamilies of $(P_4+\ell P_1)$-free graphs

Abstract

A graph $G$ is $k$-vertex-critical if $\chi (G)=k$ but $\chi (G-v)<k$ for all $v\in V(G)$. In this paper we make progress on the open problem of the finiteness of $k$-vertex-critical $(P_4+\ell P_1)$-free graphs by showing that there are only finitely many $k$-vertex-critical graphs in the following subfamilies of $(P_4+\ell P_1)$-free graphs for all $k\ge 1$ and $\ell \ge 0$: $\bullet$ $(P_4+\ell P_1,\text{chair})$-free graphs, $\bullet$ $(P_4+\ell P_1,P_5,\text{bull})$-free graphs, and $\bullet$ $(P_4+\ell P_1,P_5,\text{cricket})$-free graphs. In fact, all but the first of these are special cases of our general result that there are only finitely many $k$-vertex-critical $(P_4+\ell P_1,B_4(m),B_3(m{)}^{+})$-free graphs for all $k\ge 1$ and $\ell ,m\ge 0$. Here $B_n(m)$ is the graph obtained from a path of order $n$ by identifying one of its leaves with the centre vertex of $K_{1,m}$ and $B_n(m{)}^{+}$ is the graph obtained by identifying an edge of $K_3$ with the edge of $B_n(m)$ with endpoints of degrees $2$ and $m$, respectively. Our results imply the existence of simple polynomial-time certifying algorithms to decide the $k$-colourability of all graphs in these subfamilies for every fixed $k$. We also show that $\chi (G)\le \ell +2$ for all $(P_4+\ell P_1,K_3)$-free graphs and all $\ell \ge 0$, improving the previously known upper bound of $2\ell +2$ that followed from Randerath and Schiermeyer's 2004 result on $(P_t,K_3)$-free graphs. More generally, we provide a $\chi$-bound in $O({\ell }^{\omega -1})$ for $(P_4+\ell P_1)$-free graphs which improves the bound of $(2\ell +2{)}^{\omega -1}$ which followed from Gravier, Hoàng and Maffray in 2003 for $P_t$-free graphs.

To appear in IWOCA 2026