Characterizing 4-critical graphs with Ore-degree at most seven

Kostochka and Yancey's short but beautiful proof for the case k=4 says that if G is a 4-critical graph, then |E(G)|≥(5|V(G)|−2)/3. We prove the following bound which is better when there exists a large independent set of degree three vertices: if G is a 4-critical graph G, then |E(G)|≥1.6|V(G)|+.2α(D3(G))−.6, where D3(G) is the graph induced by the degree three vertices of G. As a corollary, we characterize the 4-critical graphs with Ore-degree at most seven as precisely the graphs of Ore-degree seven in the family of graphs obtained from K4 and Ore compositions.