{"id":"arxiv/2604.06999","url":"https://arxiv.org/abs/2604.06999","tags":["math.CO","cs.DM"],"score":0,"title":"Vertex-critical graphs in subfamilies of $(P_4+\\ell P_1)$-free graphs","domain":"math.CO","source":"arxiv","authors":["Iain Beaton","Ben Cameron"],"reviews":0,"subject":"math.CO","summary":"A graph $G$ is $k$-vertex-critical if $χ(G)=k$ but $χ(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…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-04-08","reactions":{}}