{"id":"arxiv/2608.20045","url":"https://arxiv.org/abs/2608.20045","tags":["math.CO"],"score":0,"title":"A dichotomy for the number of vertex-critical ($P_5$, $H$)-free graphs when $H$ is bipartite","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 $χ(H)<k$ for every induced subgraph $H$ of $G$. A graph $G$ is $(H_1,H_2,\\dots,H_m)$-free if does not contain $H_i$ as an induced subgraph for any $i\\in\\{1,2,\\dots,m\\}$.We provide the following dichotomy that for bipartite graphs $H$ and any fixed integer $k\\ge 5$ , there are only finitely many $k$-vertex-critical $(P_5,H)$-free graphs if and only if $H$ is $2P_2$-free. This leads us to pose the problem about determining for which graphs $H$ with $χ(H)\\ge 3$ there are infinitely many $k$-vertex-critical $(P_5,H)$-free graphs for all $k\\ge…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-08-20","reactions":{}}