A dichotomy for the number of vertex-critical ($P_5$, $H$)-free graphs when $H$ is bipartite

A graph $G$ is $k$-vertex-critical if $\chi (G)=k$, but $\chi (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 $\chi (H)\ge 3$ there are infinitely many $k$-vertex-critical $(P_5,H)$-free graphs for all $k\ge 5$. Toward this problem, we show that there only finitely many $k$-vertex-critical $(P_5,K_{s,t}+e)$-free graphs for all $k,s,t\ge 1$, where $K_{s,t}+e$ is a complete bipartite graph plus a single edge. On the other hand, we show that there are infinitely many $k$-vertex-critical $(P_5,\mathrm{net},\mathrm{co-net},\overline{C_5},\overline{C_6},\dots \overline{C_{k-1}})$-free graphs for all $k\ge 5$. We also show that there are only finitely many $k$-vertex-critical $(P_4+\mathrm{\ell }{P}_1,\overline{L(K_{2,n})})$-free graphs for all $\mathrm{\ell },n\ge 0$, providing the largest known subfamily of $(P_4+\mathrm{\ell }{P}_1)$-free graphs to satisfy this property. Our results, together with known results, imply the existence of new polynomial-time certifying algorithms to determine the $k$-colourability of many subfamilies of $P_5$-free and $(P_4+\mathrm{\ell }{P}_1)$-free graphs for fixed $k\ge 5$. Our proof techniques apply a powerful theorem of Chudnovsky, Kim, Oum, and Seymour (2016) on prime graphs that we expect to be of interest and have further applications to bounding the number of $k$-vertex-critical graphs in other hereditary families of graphs.