Recently, Kostochka and Yancey proved that a conjecture of Ore is asymptotically true by showing that every $k$-critical graph satisfies $|E(G)|geqleftlceilleft(frac{k}{2}-frac{1}{k-1}right)|V(G)|-frac{k(k-3)}{2(k-1)}rightrceil.$ 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 $kgeq33$ there exists an $varepsilon>0$ so that if $G$ is a $k$-critical graph, then $|E(G)|geqleft(frac{k}{2}-frac{1}{k-1}+varepsilon_kright)|V(G)|-frac{k(k-3)}{2(k-1)}-(k-1)varepsilon 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 $kgeq33$ the following conjecture of Postle regarding the asymptotic density: For every $kgeq4$ there exists an $varepsilon_k>0$ such that if $G$ is a $k$-critical $K_{k-2}$-free graph, then $|E(G)|geq left(frac{k}{2}-frac{1}{k-1}+varepsilon_kright)|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 Yanceys bound.
Download