Ben Cameron

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...