Structure in sparse $k$-critical graphs

Abstract

Recently, Kostochka and Yancey proved that a conjecture of Ore is asymptotically true by showing that every $k$-critical graph satisfies $|E(G)|\ge \lceil \left(\frac{k}{2}-\frac{1}{k-1}\right)|V(G)|-\frac{k(k-3)}{2(k-1)}\rceil .$ They also characterized the class of graphs that attain this bound and showed that it is equivalent to the set of $k$-Ore graphs. We show that for any $k\ge 33$ there exists an $\epsilon >0$ so that if $G$ is a $k$-critical graph, then $|E(G)|\ge \left(\frac{k}{2}-\frac{1}{k-1}+{\epsilon }_k\right)|V(G)|-\frac{k(k-3)}{2(k-1)}-(k-1)\epsilon T(G)$, where $T(G)$ is a measure of the number of disjoint $K_{k-1}$ and $K_{k-2}$ subgraphs in $G$. This also proves for $k\ge 33$ the following conjecture of Postle regarding the asymptotic density: For every $k\ge 4$ there exists an ${\epsilon }_k>0$ such that if $G$ is a $k$-critical $K_{k-2}$-free graph, then $|E(G)|\ge \left(\frac{k}{2}-\frac{1}{k-1}+{\epsilon }_k\right)|V(G)|-\frac{k(k-3)}{2(k-1)}$. As a corollary, our result shows that the number of disjoint $K_{k-2}$ subgraphs in a $k$-Ore graph scales linearly with the number of vertices and, further, that the same is true for graphs whose number of edges is close to Kostochka and Yancey's bound.

20 pages