Kostochka and Yancey resolved a famous conjecture of Ore on the asymptotic density of $k$-critical graphs by proving that every $k$-critical graph $G$ satisfies $|E(G)| geq (frac{k}{2} - frac{1}{k-1})|V(G)| - frac{k(k-3)}{2(k-1)}$. The class of graphs for which this bound is tight, $k$-Ore graphs, contain a notably large number of $K_{k-2}$-subgraphs. Subsequent work attempted to determine the asymptotic density for $k$-critical graphs that do emph{not} contain large cliques as subgraphs, but only partial progress has been made on this problem. The second author showed that if $G$ is 5-critical and has no $K_3$-subgraphs, then for $varepsilon = 1/84$, $|E(G)| geq (frac{9}{4} + varepsilon)|V(G)| - frac{5}{4}$. It has also been shown that for all $k geq 33$, there exists $varepsilon_k > 0$ such that $k$-critical graphs with no $K_{k-2}$-subgraphs satisfy $|E(G)| geq (frac{k}{2} - frac{1}{k-1} + varepsilon_k)|V(G)| - frac{k(k-3)}{2(k-1)}$. In this work, we develop general structural results that are applicable to resolving the remaining difficult cases $6 leq k leq 32$. We apply our results to carefully analyze the structure of 6-critical graphs and use a discharging argument to show that for $varepsilon_6 = 1/1050$, 6-critical graphs with no $K_4$ subgraph satisfy $|E(G)| geq ( frac{k}{2} - frac{1}{k-1} + varepsilon_6 ) |V(G)| - frac{k(k-3)}{2(k-1)}$.
تحميل البحث