  Dirac introduced the notion of a k-critical graph, a graph that is not
(k-1)-colorable but whose every proper subgraph is (k-1)-colorable. Brook's
Theorem states that every graph with maximum degree k is k-colorable unless it
contains a subgraph isomorphic to K_{k+1} (or an odd cycle for k=2).
Equivalently, for all k>=4, the only k-critical graph of maximum degree k-1 is
K_k. A natural generalization of Brook's theorem is to consider the Ore-degree
of a graph, which is the maximum of d(u)+d(v) over all edges uv. Kierstead and
Kostochka proved that for all k>=6 the only k-critical graph with Ore-degree at
most 2k-1 is K_k. Kostochka, Rabern and Steibitz proved that the only
5-critical graphs with Ore-degree at most 9 are K_5 and a graph they called
O_5.
  A different generalization of Brook's theorem, motivated by Hajos'
construction, is Gallai's conjectured bound on the minimum density of a
k-critical graph. Recently, Kostochka and Yancey proved Gallai's conjecture.
Their proof for k>=5 implies the above results on Ore-degree. However, the case
for k=4 remains open, which is the subject of this paper.
  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 alpha(D_3(G)) - .6, where D_3(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 K_4 and Ore compositions.

Combinatorics