Lecture notes on sparse color-critical graphs

Alexandr Kostochka

1 Introduction
This text together with the attached paper [8] surveys results on color-critical graphs, with emphasis
on sparse ones. The first two sections discuss the important contributions by Dirac and Gallai
and present proofs of some remarkable results of them. The next two sections discuss the later
progress and a number of applications of the recent results. We also use [8] for description of
some applications. In Section 6 we present a proof for 4-critical graphs of a conjecture of Gallai on
sparsest color-critical graphs. In the last section, we briefly survey similar problems for hypergraphs
and triangle-free graphs and mention some unsolved problems.
Recall that a (proper) k-coloring of a graph G is a mapping g : V (G) → {1, . . . , k} such that
g(v) 6= g(u) for each vu ∈ E(G). The minimum k such that G has a k-coloring is the chromatic
number of G, denoted by χ(G).
For a positive integer k, a graph G is k-critical if χ(G) = k, but every proper subgraph of G is
(k − 1)-colorable.
It is easy to check that the complete k-vertex graph Kk is k-critical and that each odd cycle is
3-critical.

Exercise 1. Let k ≥ 3. Prove that there are no k-critical (k + 1)-vertex graphs. Describe all
k-critical (k + 2)-vertex graphs.

2 Dirac
Dirac [10, 11, 12, 20, 15, 22, 19] introduced the notion of k-critical graphs and started a systematic
study of them.

Lemma 1 (Dirac [15]). Let k ≥ 3 and let G be a k-critical graph. Then G is (k −1)-edge-connected.
In particular, δ(G) ≥ k − 1.

Proof (Kopon). Suppose that V (G) has a partition V (G) = V1 ∪ V2 into nonempty sets such
that |EG (V1 , V2 )| = t ≤ k − 2. Let EG (V1 , V2 ) = {x1 y1 , . . . , xt yt }, where {x1 , . . . , xt } ⊆ V1 and
{y1 , . . . , yt } ⊆ V2 (the vertices x1 , . . . , xt (respectively, y1 , . . . , yt ) do not need to be distinct). For
i = 1, 2, let Gi = G[Vi ]. Since G1 and G2 are proper subgraphs of G, by the definition of k-critical
graphs, for i = 1, 2, graph Gi has a proper (k − 1)-coloring gi with colors 1, . . . , k − 1.
There are (k − 1)! ways to rename the colors in g2 with 1, . . . , k − 1. For every 1 ≤ j ≤ t,
the number of color permutations such that g2 (yj ) = g1 (xj ) is (k − 2)!. Hence there are at least
(k − 1)! − t(k − 2)! = (k − 2)!(k − 1 − t) ≥ (k − 2)! permutations such that g2 (yj ) 6= g1 (xj ) for all

1
j = 1, . . . , t. Any such permutation yields a proper (k − 1)-coloring g of G; a contradiction. 2

Exercise 2 (Toft). Let k ≥ 3 and let G be a k-critical graph. Suppose V (G) has a partition V (G) =
V1 ∪ V2 into nonempty sets such that |EG (V1 , V2 )| = k − 1. Let EG (V1 , V2 ) = {x1 y1 , . . . , xk−1 yk−1 },
where {x1 , . . . , xk−1 } ⊆ V1 and {y1 , . . . , yk−2 } ⊆ V2 . For i = 1, 2, let Gi = G[Vi ]. Then one of the
following holds:
(1) for each (k − 1)-coloring of G1 , the colors of all x1 , . . . , xk−1 are the same and for each (k − 1)-
coloring of G2 , the colors of all y1 , . . . , yk−1 are distinct;
(2) for each (k − 1)-coloring of G1 , the colors of all x1 , . . . , xk−1 are distinct and for each (k − 1)-
coloring of G2 , the colors of all y1 , . . . , yk−1 are the same.

Already this simple lemma yields the Heawood Formula for the chromatic number of graphs
embeddable into surfaces of a given genus.

Theorem 2 (Heawood,
j √1890).k If G is graph embeddable into an orientable surface Sγ of genus
γ ≥ 1, then χ(G) ≤ 7+ 1+48γ
2 .
√
Proof. Let c := cγ := 7+ 1+48γ
2 . Suppose χ(G) > c. Then G contains a (bcc + 1)-critical
subgraph G . Let n = |V (G )|, e = |E(G0 )| and f be the number of faces in an embedding of G0
0 0

into Sγ . Then n > c. From the Euler Formula n − e + f = 2(1 − γ) and the fact that 3f ≤ 2e, we
obtain
2e 12(γ − 1) 12(γ − 1)
≤6+ ≤6+ . (1)
n n c
12(γ−1)
Since c is a root of the equation c2 − 7c − 12(γ − 1) = 0, we have 6 + c = c − 1, so (1) yields
n ≤ c − 1. But by Lemma 1, n ≥ δ(G ) ≥ bcc, a contradiction. 2
2e 2e 0

In a series of papers [13, 14, 16, 17, 18], Dirac sharpened Theorem 2 by showing that for γ ≥ 1
every graph embeddable into Sγ and having chromatic number bcγ c contains the complete graph
with bcγ c vertices. For this he used properties of critical graphs with few vertices, but a really
short proof he obtained in [18] by using the following general lower bound on the number of edges
in critical graphs.

Theorem 3 (Dirac [20]). If n > k ≥ 4 and G is an n-vertex k-critical graph, then

2|E(G)| ≥ (k − 1)n + k − 3. (2)

Proof (Deuber, A.K., Sachs). For a graph F , let (F ) := 2|E(F )| − (k − 1)|V (F )|. Then the
theorem is equivalent to the assertion that if k ≥ 4, then

(G) ≥ k − 3 for each k-critical graph G ∼

6 Kk .
= (3)

We will use induction on |V (G)| for a fixed k ≥ 4. So, let G be a smallest k-critical graph G
distinct from Kk for which (3) does not hold.

2
 If y, z ∈ V (G) and yz ∈/ E(G), then H(G; y, z) is the graph obtained from G by gluing y and
z into one vertex. Then χ(H(G; y, z)) ≥ χ(G) = k. So, H(G; y, z) contains a k-critical subgraph
G∗ = G∗ (y, z). Since G itself is k-critical,

y ∗ z ∈ V (G∗ ). (4)

Let H = H(G; y, z) and U = U (G∗ ) := V (G) − V (G∗ ) − y − z. If x ∈ V (G) with dG (x) = k − 1

and y, z ∈ NG (x), then dH (x) = k − 2 and hence by Lemma 1,

x ∈ U. (5)

The main idea of the proof is the following relation:

X
2e(G) ≥ 2e(G∗ ) + dG (u) + eG (U, V (G) − U ) + 2|(NG (y) ∩ NG (z)) − U |.
u∈U

It implies that
X
(G) ≥ (G∗ ) + (dG (u) − k + 1) − (k − 1) + eG (U, V (G) − U ) + 2|(NG (y) ∩ NG (z)) − U |. (6)
u∈U

We claim that

G∗ ∼
= Kk for any x, y, z ∈ V (G) with dG (x) = k − 1, xy, xz ∈ E(G) and yz ∈
/ E(G). (7)

Indeed, if G∗ ∼6 Kk , then by the minimality of G, (G∗ ) ≥ k − 3. By (5), U 6= ∅, and so by

=
Lemma 1, eG (U, V (G) − U ) ≥ k − 1. Then by (6),
X
(G) ≥ (G∗ ) + (dG (u) − k + 1) − (k − 1) + (k − 1) ≥ (G∗ ) ≥ k − 3.
u∈U

This proves (7).

Since |V (G)| ≥ k + 2 and (G) ≤ k − 4, there is v ∈ V (G) with dG (v) = k − 1. Then by (7),
there is W ⊂ V (G) with G[W ] = Kk−1 . Again, since (G) ≤ k − 4, there are x1 , x2 , x3 ∈ W with
dG (xi ) = k − 1 for 1 ≤ i ≤ 3. Let yi be the neighbor of xi in V (G) − W . Let W1 := W ∩ NG (1 )
and W10 = W − W1 . Choose W and x1 to maximize |W1 |.
Let z1 be a vertex in W10 of minimum degree. Let H := H(G; y1 , z1 ), G∗ := G∗ (y1 , z1 ), U =
U (G∗ ) and UW := U ∩ W . By the symmetry between x2 and x3 , we may assume z1 6= x2 . Since
dG−x1 (x2 ) = k − 2, by (5), {x1 , x2 } ⊆ UW . So, by (4),

2 ≤ |UW | ≤ k − 2. (8)

Case 1: j := |UW | = k −2. Let S := V (G∗ )−y1 ∗z1 . By (7), G[S] = Kk−1 . Let S 0 := S ∩N (y1 ),
s := |S 0 |, and S 00 = S − S 0 . Since G∗ = Kk , S 00 ⊂ NG (z1 ) and so dG (z1 ) ≥ (|W | − 1) + |S 00 | =
k − 2 + (k − 1 − s). Thus if dG (v) ≥ k for each v ∈ S 0 , then (G) ≥ (dG (z1 ) − k + 1) + s ≥ k − 2,
a contradiction. Hence we may assume that S 0 contains a vertex x0 with dG (x0 ) = k − 1 and hence
by the choice of W and x1 ,
s ≤ |W1 |. (9)

3
Also, since G does not contain Kk , 1 ≤ s ≤ k − 2 and 1 ≤ |W1 | ≤ k − 2. By the choice of z1 and (9),

(G) ≥ (dG (y1 ) − k + 1) + |W10 |(dG (z1 ) − k + 1)

≥ (|W1 | + s − k + 1) + (k − 1 − |W1 |)(k − 2 − s) = |W1 | − 1 + (k − 2 − |W1 |)(k − 2 − s)

≥ |W1 | − 1 + (k − 2 − |W1 |)2 ≥ |W1 | − 1 + (k − 2 − |W1 |) = k − 3;
a contradiction.
Case 2: 2 ≤ j ≤ k − 3. Each of the k − 2 − j vertices in W − U − z1 has k − 2 neighbors in W
and j + 1 neighbors in V (G∗ ) − W . Thus
X
(G) ≥ (dG (z) − k + 1) ≥ (k − 2 − j)(k − 2 + j + 1 − k + 1) = j(k − 2 − j) ≥ k − 3;
z∈W −U −z1

a contradiction. 2

Example 1 (Dirac). Let k ≥ 4. Every graph G in the family D(k) has 2k − 1 vertices partitioned
into 3 sets: V0 , V1 and V2 , where |V0 | = 2, |V1 | = k − 1 and |V2 | = k − 2. We have G[V1 ] = Kk−1 ,
G[V2 ] = Kk−2 , each v ∈ V2 is adjacent to both vertices in V0 , and each vertex in V1 is adjacent to
exactly one vertex in V0 . Furthermore each of the two vertices in V0 has a neighbor in V1 . There
are no other edges.

Exercise 3 (Dirac). Let k ≥ 5. Prove that each graph G ∈ D(k) is k-critical and has 0.5((k −
1)|V (G)| + k − 3) edges, i.e., is a sharpness example for Theorem 3.

Exercise 4 (Dirac). Let k ≥ 5. Extending the ideas of a proof of Theorem 3, show that every
k-critical graph G distinct from Kk and not belonging to D(k) satisfies (G) ≥ k − 1.

Exercise 5. Using Theorem 3, mimic the proof of Theorem 2 to prove the Dirac’s result that for
γ ≥ 1, every graph embeddable into Sγ with chromatic number bcγ c contains the complete graph on
bcγ c vertices.

3 Gallai
In his fundamental papers [25] and [26], Gallai proved a series of important properties of color-
critical graphs.

Theorem 4 (Gallai). If k ≥ 4, k + 2 ≤ n ≤ 2k − 2 and G is an n-vertex k-critical graph, then the

complement of G is disconnected.

Theorem 5 (Gallai). Let k ≥ 4 and G be a k-critical graph. Let B = B(G) be the set of vertices
of degree k − 1 in G. Then each block of G[B] is a complete graph or an odd cycle.

k

Let f (n, k) denote the minimum number of edges in an n-vertex k-critical graph. Then f (k, k) =
2 and f (k + 1, k) is not well defined. Theorem 3 states that if k ≥ 4 and n ≥ k + 2, then
f (n, k) ≥ 12 ((k − 1)n + k − 3). Using Theorem 4, Gallai found exact values of f (n, k) for small n.

4
Theorem 6 (Gallai). If k ≥ 4 and k + 2 ≤ n ≤ 2k − 1, then
1
f (n, k) = ((k − 1)n + (n − k)(2k − n)) − 1.
2
Note that the function is quadratic in k.
Theorem 5 in turn implies the following lower bound on f (n, k).

Theorem 7 (Gallai). If k ≥ 4 and k + 2 ≤ n, then

k−1 k−3
f (n, k) ≥ n+ n. (10)
2 2(k 2 − 3)
For large n, this bound is much stronger than the bound in Theorem 3.

3.1 Deriving Theorem 7 from Theorem 5

A Gallai tree is a graph in which every block is a complete graph or an odd cycle.

Lemma 8. Let k ≥ 4 and let T be an n-vertex Gallai tree with maximum degree ∆(T ) ≤ k − 1 not
containing Kk . Then  
2
2|E(T )| ≤ k − 2 + n. (11)
k−1
Proof. If T is a block, then, since T ∼6 Kk and k ≥ 4, ∆(T ) ≤ k − 2 which is stronger than (11).
=
Suppose (11) holds for all Gallai trees with at most s blocks and T is a Gallai tree with s + 1
blocks. Let B be a leaf block in T and x be the cut vertex in V (B). Let D := ∆(B).
Case 1: D ≤ k − 3. Let T 0 := T − (V (B) − {x}). Then T0 is a Gallai tree with s blocks. So
0 0 2
2|E(T )| = 2|E(T )| + D|V (B)| and, by induction, 2|E(T )| ≤ k − 2 + k−1 (n − |V (B)| + 1). If
B = Kr , then r = D + 1 ≤ k − 2. So in this case
 
2
2|E(T )| − k − 2 + n
k−1
   
2 2
≤ k−2+ (n − D) + D(D + 1) − k − 2 + n
k−1 k−1
 
2 2
= D −k + 2 − + D + 1 ≤ −D < 0,
k−1 k−1
as claimed. Similarly, if B = Ct , then, by the case, k ≥ 5 and
 
2
2|E(T )| − k − 2 + n
k−1
   
2 2
≤ k−2+ (n − t + 1) + 2t − n k − 2 +
k−1 k−1
 
2
= (t − 1) −k + 2 − + 2 + 2 < 2 (−k + 4) + 2 ≤ 0.
k−1

Case 2: D = k − 2. Since ∆(T ) ≤ k − 1, only one block B 0 apart from B may contain x
and this B 0 must be K2 . Let T 00 = T − V (B). Then T 00 is a Gallai tree with s − 1 blocks. So

5
  
2|E(T )| = 2|E(T 00 )| + D|V (B)| + 2 and, by induction, 2|(T 00 )| ≤ k − 2 + k−12
(n − |V (B)|). Hence
in this case, since |V (B)| ≥ D + 1 = k − 1,
 
2
2|E(T )| − k − 2 + n
k−1
   
2 2
≤ k−2+ (n − |V (B)|) + (k − 2)|V (B)| + 2 − k − 2 + n
k−1 k−1
 
2 2
= |V (B)| −k + 2 − +k−2 +2≤− |V (B)| + 2 ≤ 0,
k−1 k−1

again. 2

Proof of Theorem 7. We use discharging. Let G be an n-vertex k-critical graph distinct from
Kk . By Lemma 1, the minimum degree of G is at least k − 1. The initial charge of each vertex
v ∈ V (G) is ch(v) := dG (v). The only discharging rule is this:
(R1) Each vertex v ∈ V (G) with dG (v) ≥ k sends to each neighbor the charge kk−1
2 −3 .

Denote the new charge of each vertex v by ch∗ (v). We will show that
 
X
∗ k−3
ch (v) ≥ k − 1 + 2 n. (12)
k −3
v∈V (G)

Indeed, if dG (v) ≥ k, then

 
∗ k−1 k−1 k−3
ch (v) ≥ dG (v) − 2 · dG (v) ≥ k 1 − 2 =k−1+ 2 . (13)
k −3 k −3 k −3

Also, if T is a component of the subgraph G0 of G induced by the vertices of degree k − 1, then

X k−1
ch∗ (v) ≥ (k − 1)|V (T )| + |EG (V (T ), V (G) − V (T )| .
k2 − 3
v∈V (T )

Since T is a Gallai tree and does not contain Kk , by Lemma 8,

 
2 k−3
|E(V (T ), V (G) − V (T )| ≥ (k − 1)|V (T )| − k − 2 + |V (T )| = |V (T )|.
k−1 k−1

Thus for every component T of G0 we have

 
X
∗ k−1 k−3 k−3
ch (v) ≥ (k − 1)|V (T )| + 2 · · |V (T )| = k−1+ 2 |V (T )|.
k −3 k−1 k −3
v∈V (T )

Together with (13), this implies (12). 2

6
3.2 List coloring and proving Theorem 5
The original proof of Theorem 5 was difficult, but the notion of list coloring as a biproduct yields a
significantly simpler proof. This notion was introduced by Vizing [57] and independently by Erdős,
Rubin and Taylor [23].
A list L for a graph G is a map L : V (G) → Pow(Z>0 ) that assigns to each vertex v ∈ V (G)
a set L(v) ⊆ Z>0 . An L-coloring of G is a mapping f : V (G) → Z>0 such that f (v) ∈ L(v) for
each v ∈ V (G) and f (v) 6= f (u) whenever vu ∈ E(G). The list chromatic number, χ` (G), is the
minimum k such that G has an L-coloring for each L satisfying |L(v)| = k for every v ∈ V (G).
Since G is k-colorable if and only if it is L-colorable with the list L : v 7→ [k], we have χ` (G) ≥
χ(G) for every G; however, the difference χ` (G) − χ(G) can be arbitrarily large. Moreover, graphs
with chromatic number 2 may have arbitrarily high list chromatic number. While 2-colorable
graphs may have arbitrarily high minimum degree, Alon [2] showed that χ` (G) ≥ (1/2 − o(1)) log2 δ
for each graph G with minimum degree δ. On the other hand, some well-known upper bounds on
χ(G) in terms of vertex degrees hold for χ` (G) as well. For example, Brooks’ theorem [9] and the
degeneracy upper bound hold for χ` (G). The following simple fact also holds.

Lemma 9 (Vizing [57]). Suppose that G is a connected graph and L is a list for G such that
|L(v)| ≥ dG (v) for every v ∈ V (G), and there is x ∈ V (G) with |L(x)| > dG (v). Then G is
L-colorable.

Proof. Suppose the lemma does not hold and choose a counter-example (G, L) with smallest
|V (G)|. Consider (G − x, L). Then each component Ci of G − x has a vertex zi adjacent to x
and hence with |L(zi ) > dG−x (zi ). By induction, each of Ci and hence the whole G − x has an L-
coloring. We now can choose a color for x from L(x) distinct from the colors of all dG (x) neighbors
of x. 2

Furthermore, Borodin [4, 5] and independently Erdős, Rubin, and Taylor [23] generalized Brooks’
Theorem to degree lists. Recall that a list L for a graph G is a degree list if |L(v)| = dG (v) for
every v ∈ V (G).

Theorem 10 ([4, 5, 23]; a simple proof in [34]). Suppose that G is a connected graph. Then G is
not L-colorable for some degree list L if and only if each block of G is either a complete graph or
an odd cycle.

Proof. Suppose there exists a pair (G, L), where G is a connected graph that is not a Gallai
tree and L is a list for G with |L(v)| ≥ dG (v) for each v ∈ V (G) such that G is not L-colorable.
We may assume that (G, L) is such a pair with the smallest |V (G)|. If |V (G)| = 1, then G = K1 ,
i.e., is a Gallai tree. So |V (G)| ≥ 2.
Given y ∈ V (G) and α ∈ L(y), let (G0y , L0α ) denote the pair such that G0y = G − y and L0α be

L(v) if yv ∈
/ E(G);
the list for G0 (y) where L0α (v) =
L(v) − α if yv ∈ E(G).
Case 1: G is a block. First, we show that

L(x) = L(y) for all x, y ∈ V (G), and G is regular. (14)

7
If there are vertices in G with distinct lists, then there are such vertices that are adjacent to each
other. Suppose that xy ∈ E(G) and α ∈ L(y) − L(x). Consider (G0y , L0α ). Since G is a block, G0y is
connected. By construction, dG0y (v) ≤ |L0α (v)| for each v ∈ V (G0y ). Moreover, by the choice of α,
dG0y (x) < |L0α (x)|. Thus, by Lemma 9, G0y has an L0α -coloring g. We extend g to an L-coloring of
G by letting g(y) := α. This proves the first part of (14). The second part follows from the first
and the fact that vertices of distinct degrees have distinct lists (of the size of the degrees).
So by (14), we are seeking an ordinary d-coloring of a d-regular graph G (for some d). Then G
is a complete graph or an odd cycle by Brooks’ Theorem (also by Theorem 3).
Case 2: G has a cut vertex. Let B1 and B2 be distinct leaf blocks. For i = 1, 2, let bi be the
cut vertex, let ai be a non-cut vertex in Bi , and let αi ∈ L(ai ). Again for i = 1, 2, consider the
pair (G0ai , L0αi ). Since ai is a non-cut vertex, G0ai is connected. By definition, L0αi is a degree list for
G0ai . Since G is not L-colorable, G0ai is not L0αi -colorable. So by the minimality of G, each block of
G0ai is a complete graph or an odd cycle. In particular, this holds for each block of G distinct from
Bi . This implies the theorem. 2

Deriving Theorem 5 from Theorem 10: Let B1 be a component of G[B]. Since G is k-critical,
there is a (k − 1)-coloring g of G − B1 . For every v ∈ B1 , define L(v) := {1, . . . , k − 1} − {g(u) :
u ∈ N (v)}. Then L is a degree list for G[B1 ]. So Theorem 10 yields the claim. 2

Remark 1. Similarly to k-critical graphs, one can define list-k-critical graphs as the graphs
whose list chromatic number is k but the list chromatic number of any proper subgraph is less than
k. And similarly to f (n, k) one can define f` (n, k) - the minimum number of edges in an n-vertex
list-k-critical graph. Then the proof in the previous paragraph shows that the claim of Theorem 5
holds also for list-critical graphs. This in turn implies that similarly to (10) we have

k−1 k−3
f` (n, k) ≥ n+ n. (15)
2 2(k 2 − 3)

Remark 2. Bounds (10) and (15) imply that

for every fixed γ and any k ≥ 6, there is a polynomial-time algorithm for checking any graph G
embeddable into Sγ whether G is k-colorable and whether G is list-k-colorable.

Exercise 6. Prove the claim in Remark 2.

3.3 Critical graphs with one high vertex and a conjecture

Theorem 5 allowed Gallai to describe for k ≥ 4 all k-critical graphs with exactly one vertex of degree
≥ k. Indeed, if G is a k-critical graph and x is the only vertex of degree ≥ k, then B(G) = V (G)−x.
By Theorem 5, G − x is a Gallai tree with maximum degree at most k − 1 and minimum degree at
least k − 2. And for every such special Gallai tree T , the graph, obtained by adding an extra vertex
x adjacent to all vertices of degree k − 2 and only to them is k-critical. If k ≥ 5, then the blocks of
such special T are of only two types: Kk−1 s and K2 s. In particular, every k-critical graph G with
exactly one vertex of degree ≥ k has 1 (mod k − 1) vertices and (k+1)(k−2)|V (G)|−k(k−3)
2(k−1) edges.

8
 Gallai thought that for n ≥ k there are no k-critical n-vertex graphs with fewer edges and posed
the following.
Conjecture 11 (Gallai [25]). If k ≥ 4 and n ≡ 1 (mod k − 1), then
(k + 1)(k − 2)n − k(k − 3)
f (n, k) = .
2(k − 1)

4 Ore and others

For a graph G and vertex u ∈ V (G), a split of u is a construction of a new graph G0 such
that V (G0 ) = V (G) − u + {u0 , u00 }, where G − u ∼
= G0 − {u0 , u00 }, N (u0 ) ∪ N (u00 ) = N (u), and
N (u0 ) ∩ N (u00 ) = ∅. A DHGO-composition O(G1 , G2 ) of graphs G1 and G2 is a graph obtained
as follows: Delete some edge yz from G2 , split some vertex x of G1 into two vertices x1 and x2
of positive degree, and identify x1 with y and x2 with z. Note that DHGO-composition could be
found in Dirac’s paper [21] and has roots in [15]. It was also used by Gallai [25] and Hajós [28].
Ore [46] used it for a composition of complete graphs.
y

z
x

Figure 1: DHGO-composition O(K5 , K5 ).

The mentioned authors observed that if G1 and G2 are k-critical and G1 is not k-critical after
x has been split, then O(G1 , G2 ) also is k-critical. This observation implies
(k + 1)(k − 2) (k + 1)(k − 2)
f (n + k − 1, k) ≤ f (n, k) + = f (n, k) + (k − 1) , (16)
2 2(k − 1)
fk (n)
which yields that φk := limn→∞ n exists and satisfies
k 1
φk ≤ − . (17)
2 k−1
 
Gallai’s bound gives φk ≥ 12 k − 1 + kk−3 2 −3 . Ore believed that using this construction starting

from an extremal graph on at most 2k vertices repeatedly with G2 = Kk at each iteration is best
possible for constructing sparse critical graphs.

9
Conjecture 12 (Ore [46]). If k ≥ 4, n ≥ k and n 6= k + 1, then

f (n + k − 1, k) = f (n, k) + (k − 2)(k + 1)/2.

Note that Conjecture 11 is equivalent to the case n ≡ 1 (mod k − 1) of Conjecture 12.

Krivelevich [42, 43] improved the bound of Theorem 7 to
k−1 k−3
f (n, k) ≥ n+ 2
n (18)
2 2(k − 2k − 1)
and demonstrated nice applications of his bound: he constructed graphs with high chromatic
number and low independence number such that the chromatic numbers of all their small subgraphs
are at most 3 or 4. We discuss a couple of his applications later. Then Kostochka and Stiebitz [36]
proved that for k ≥ 6 and n ≥ k + 2,
k−1 k−3
f (n, k) ≥ n+ 2 n. (19)
2 k + 6k − 11 − 6/(k − 2)
Farzad and Molloy [24] proved the claim of Conjecture 11 in the case when k = 4 and the subgraph
of G induced by the vertices of degree 3 is connected.
Some time ago, Kostochka and Yancey [39] proved Conjecture 11 valid.
l m
Theorem 13 ([39]). If k ≥ 4 and G is k-critical, then |E(G)| ≥ (k+1)(k−2)|V (G)|−k(k−3)
2(k−1) . In other
words, if k ≥ 4 and n ≥ k, n 6= k + 1, then
 
(k + 1)(k − 2)n − k(k − 3)
f (n, k) ≥ F (n, k) := .
2(k − 1)
The result also confirms Conjecture 12 in several cases.

Corollary 14 ([39]). Conjecture 12 is true if (i) k = 4, (ii) k = 5 and n ≡ 2 (mod 4), or (iii)
n ≡ 1 (mod k − 1).

Also, it determines φk :

Corollary 15. For every k ≥ 4 and n ≥ k + 2,

k(k − 1)
0 ≤ f (n, k) − F (n, k) ≤ − 1.
8
k 1
In particular, φk = 2 − k−1 .

A simple but helpful tool was the following claim.

Corollary 16. Let k ≥ 4 and G be a k-critical graph. Let disjoint vertex subsets A and B be such
that
(a) either A or B is independent;
(b) d(a) = k − 1 for every a ∈ A;
(c) d(b) = k for every b ∈ B;
(d) |A| + |B| ≥ 3.
Then (i) e(G(A, B)) ≤ 2(|A| + |B|) − 4 and (ii) e(G(A, B)) ≤ |A| + 3|B| − 3.

10
 (k+1)(k−2)|V (G)|−k(k−3)
Call a graph G k-extremal, if G is k-critical and |E(G)| = 2(k−1) . By definition,
if G is k-extremal, then (k+1)(k−2)|V (G)|−k(k−3)
2(k−1) is an integer, and so |V (G)| ≡ 1 (mod k − 1). For
example, Kk is k-extremal. Another example of a 5-extremal graph is on the bottom of Fig. 1.
Suppose that G1 and G2 are k-extremal and G = O(G1 , G2 ). Then

(k + 1)(k − 2)(|V (G1 )| + |V (G2 )|) − 2k(k − 3)

|E(G)| = |E(G1 )| + |E(G2 )| − 1 = −1
2(k − 1)

(k + 1)(k − 2)|V (G)| − k(k − 3)

= .
2(k − 1)
After x is split, G1 will still have F (|V (G1 )|, k) < F (|V (G1 )| + 1, k) edges, and therefore will not
be k-critical. Thus the DHGO-composition of any two k-extremal graphs is again k-extremal.
A graph is a k-Ore graph if it is obtained from a set of copies of Kk by a sequence of DHGO-
compositions. By the above, every k-Ore graph is k-extremal. This yields an explicit construction
of infinitely many k-extremal graphs. Kostochka and Yancey [41] proved that there are no other
k-extremal graphs.

Theorem 17. Let k ≥ 4 and G be a k-critical graph. Then G is k-extremal if and only if it is
a k-Ore graph. Moreover, if G is not a k-Ore graph, then |E(G)| ≥ (k+1)(k−2)|V (G)|−yk
2(k−1) , where
2 2
yk = max{2k − 6, k − 5k + 2}. Thus y4 = 2, y5 = 4, and yk = k − 5k + 2 for k ≥ 6.

The message of Theorem 17 is that although for every k ≥ 4 there are infinitely many k-extremal
graphs, they all have a simple structure. In particular, every k-extremal graph distinct from Kk
has a separating set of size 2. The theorem gives a slightly better approximation for f (n, k) and
adds new cases for which we now know the exact values of f (n, k):

Corollary 18. Conjecture 12 holds and the value of f (n, k) is known if (i) k ∈ {4, 5}, (ii) k = 6
and n ≡ 0 (mod 5), (iii) k = 6 and n ≡ 2 (mod 5), (iv) k = 7 and n ≡ 2 (mod 6), or (v) k ≥ 4
and n ≡ 1 (mod k − 1).

This value of yk in Theorem 17 is best possible in the sense that for every k ≥ 4, there exist
infinitely many 3-connected graphs G with |E(G)| = (k+1)(k−2)|V (G)|−yk
2(k−1) . The idea of this construc-
tion and the examples for k = 4, 5 are due to Toft ([55], based on [54]). There are other examples
for k ≥ 6.

5 Some applications
5.1 Ore-degrees
The Ore-degree, Θ(G), of a graph G is the maximum of d(x) + d(y) over all edges xy of G. Let
Gt = {G : Θ(G) ≤ t}.

Exercise 7. Prove that χ(G) ≤ 1 + bt/2c for every G ∈ Gt .

Clearly Θ(Kd+1 ) = 2d and χ(Kd+1 ) = d+1. The graph O5 in Fig 2 is the only 9-vertex 5-critical
graph with Θ at most 9. We have Θ(O5 ) = 9 and χ(O5 ) = 5.

11
 x y

Figure 2: The graph O5 .

A natural question is to describe the graphs in G2d+1 with chromatic number d+1. Kierstead and
Kostochka [30] proved that for d ≥ 6 each such graph contains Kd+1 . Then Rabern [50] extended
the result to d = 5. Each (d + 1)-chromatic graph G contains a (d + 1)-critical subgraph G0 . Since
δ(G0 ) ≥ d and Θ(G0 ) ≤ Θ(G) ≤ 2d + 1,

∆(G0 ) ≤ d + 1, and vertices of degree d + 1 form an independent set. (20)

Thus the results in [30] and [50] mentioned above could be stated in the following form.

Theorem 19 ([30, 50]). Let d ≥ 5. Then the only (d + 1)-critical graph G0 satisfying (20) is Kd+1 .

The case d = 4 was settled by Kostochka, Rabern, and Stiebitz [35]:

Theorem 20 ([35]). Let d = 4. Then the only 5-critical graphs G0 satisfying (20) are K5 and O5 .

Theorem 13 and Corollary 16 yield simpler proofs of Theorems 19 and 20. The key observation
is the following.

Lemma 21. Let d ≥ 4 and let G0 be a (d + 1)-critical graph satisfying (20). If G0 has n vertices of
which h > 0 vertices have degree d + 1, then
 
(d − 2)n − (d + 1)(d − 2)
h≥ (21)
d
and  
n−3
h≤ . (22)
d−1
Proof. By definition, 2e(G0 ) = dn + h. So, by Theorem 13 with k = d + 1,
2 (d + 1)(d − 2)
dn + h ≥ (d + 1 − )n − ,
d d
which yields (21).
Let B be the set of vertices of degree d + 1 in G0 and A = V (G0 ) − B. By (20), e(G0 (A, B)) =
h(d + 1). So, by Corollary 16(ii) with k = d + 1,

h(d + 1) ≤ 3h + (n − h) − 3 = 2h + n − 3,

12
which yields (22). 2

Another ingredient is Exercise 1: Let k ≥ 3. There are no k-critical graphs with k + 1 vertices,
and the only k-critical graph (call it Dk ) with k + 2 vertices is obtained from the 5-cycle by adding
k − 3 all-adjacent vertices.
Suppose G0 with n vertices of which h vertices have degree d + 1 is a counter-example to
Theorems 19 or 20. Since the graph Dd+1 from Exercise 1 has a vertex of degree d + 2, n ≥ d + 4.
So since d ≥ 4, by (21),
   
(d − 2)(d + 4) − (d + 1)(d − 2) 3(d − 2)
h≥ = ≥ 2.
d d
On the other hand, if n ≤ 2d, then by (22),
 
2d − 3
h≤ = 1.
d−1
Thus n ≥ 2d + 1.
Combining (21) and (22) together, we get
(d − 2)n − (d + 1)(d − 2) n−3
≤ .
d d−1
Solving with respect to n, we obtain
 
(d + 1)(d − 1)(d − 2) − 3d
n≤ . (23)
d2 − 4d + 2
For d ≥ 5, the RHS of (23) is less than 2d+1, a contradiction to n ≥ 2d+1. This proves Theorem 19.
Suppose d = 4. Then (23) yields n ≤ 9. So, in this case, n = 9. By (21) and (22), we get h = 2.
Let B = {b1 , b2 } be the set of vertices of degree 5 in G0 . By a theorem of Stiebitz [53], G0 − B
has at least two components. Since |B| = 2 and δ(G0 ) = 4, each such component has at least 3
vertices. Since |V (G0 ) − B| = 7, we may assume that G0 − B has exactly two components, C1 and
C2 , and that |V (C1 )| = 3. Again because δ(G0 ) = 4, C1 = K3 and all vertices of C1 are adjacent
to both vertices in B. So, if we color both b1 and b2 with the same color, this can extended to a
4-coloring of G0 − V (C2 ). Thus to have G0 5-chromatic, we need χ(C2 ) ≥ 4 which yields C2 = K4 .
Since δ(G0 ) = 4, e(V (C2 ), B) = 4. So, since each of b1 and b2 has degree 5 and 3 neighbors in C1 ,
each of them has exactly two neighbors in C2 . This proves Theorem 20.
Remark. Recently Postle [47] and independently Kierstead and Rabern [31] have used Theo-
rem 17 to describe the infinite family of 4-critical graphs G with the property that for each edge
xy ∈ E(G), d(x) + d(y) ≤ 7. It turned out that such graphs form a subfamily of the family of 4-Ore
graphs.

5.2 Local vs. global graph properties

Krivelevich [42] presented several nice applications of his lower bounds on f (n, k) and related graph
parameters to questions of existence of complicated graphs whose small subgraphs are simple. We
indicate here how to improve two of his bounds using Theorem 13.

13
 √
Let f ( n, 3, n) denote the maximum chromatic number over n-vertex graphs in which every
√
n-vertex subgraph has chromatic number at most 3. Krivelevich proved that for every fixed  > 0
and sufficiently large n,
√
f ( n, 3, n) ≥ n6/31− . (24)
For this, he used his result that every 4-critical t-vertex graph with odd girth at least 7 has at least
31t/19 edges. If instead of this result, we use our bound on f (n, 4), then repeating almost word
0
by word Krivelevich’s proof of (24) (Theorem 4 in[42]) and choosing p = n−4/5− , we get that for
every fixed  and sufficiently large n,
√
f ( n, 3, n) ≥ n1/5− . (25)

Another result of Krivelevich is:

Theorem 22 ([42]). There exists C > 0 such that for every s ≥ 5 there exists a graph Gs with at

33
least C lnss 14 vertices and independence number less than s such that the independence number
of each 20-vertex subgraph is at least 5.
He used the fact that for every m ≤ 20 and every m-vertex 5-critical graph H,
|E(H)| − 1 d17m/8e − 1 33
≥ ≥ .
m−2 m−2 14
From Theorem 13 we instead get
 9m−5 
|E(H)| − 1 4 −1 43
≥ ≥ .
m−2 m−2 18
33 43
Then repeating the argument in [42] we can replace 14 in the statement of Theorem 22 with 18 .

5.3 Coloring planar graphs

In the attached paper [8], we use Theorem 13 to give simple proofs of some well-known results on
3-coloring of planar graphs, in particular of the Axenov-Grünbaum Theorem, and an one-paragraph
proof of Grötzsch’s Theorem [27]. Note that although the proof of the general case of Theorem 13
is somewhat long, the proof of the used case k = 4 is quite reasonable, and we present it in the
next section.
In [7], Theorem 17 was used to describe the 4-critical planar graphs with exactly 4 triangles.
This problem was studied by Axenov [1] in the seventies, and then mentioned by Steinberg [52]
(quoting Erdős from 1990), and Borodin [6]. In particular, it was proved that the 4-critical planar
graphs with exactly 4 triangles and no 4-faces are exactly the 4-Ore graphs with exactly 4 triangles.

6 Proof of Case k = 4 of Theorem 13

Theorem 13 for k = 4 reads:  
5n − 2
f (n, 4) = . (26)
3
The proof in this section is from [40].

14
Definition 1. For R ⊆ V (G), define the potential of R to be ρG (R) = 5|R| − 3|E(G[R])|. When
there is no chance for confusion, we will use ρ(R). Let P (G) = min∅6=R⊆V (G) ρ(R).
Exercise 8. Calculate that ρK1 (V (K1 )) = 5, ρK2 (V (K2 )) = 7, ρK3 (V (K3 )) = 6, ρK4 (V (K4 )) = 2.
By definition, we have the following.
Exercise 9. Let G be a graph and A, B, C ⊆ V (G) be such that A ⊃ B and A ∩ C = ∅. Prove
that ρG (A − B) = ρG (A) − ρG (B) + 3|EG (A − B, B)| (equivalently, ρG (A ∪ C) = ρG (A) + ρG (C) −
3|EG (A, C)|).
Note that |E(G)| < 5|V (G)|−2
3 is equivalent to ρ(V (G)) > 2. Let G be a vertex-minimal 4-critical
graph with ρ(V (G)) > 2. This implies that

if |V (H)| < |V (G)| and P (H) > 2, then H is 3-colorable. (27)

Definition 2. For a graph G, a set R ⊂ V (G) and a 3-coloring φ of G[R], the graph Y (G, R, φ) is
constructed as follows. First, for 1 ≤ i ≤ 3, let Ri0 denote the set of vertices in V (G) − R adjacent
to at least one vertex v ∈ R with φ(v) = i. Second, let X = {x1 , x2 , x3 } be a set of new vertices
disjoint from V (G). Now, let Y = Y (G, R, φ) be the graph with vertex set V (G) − R + X, such that
Y [V (G) − R] = G − R and N (xi ) = Ri0 ∪ (X − xi ) for 1 ≤ i ≤ 3.
Claim 1. Suppose R ⊂ V (G), and φ is a 3-coloring of G[R]. Then χ(Y (G, R, φ)) ≥ 4.
Proof. Let G0 = Y (G, R, φ). Suppose G0 has a 3-coloring φ0 : V (G0 ) → C = {1, 2, 3}. By
construction of G0 , the colors of all xi in φ0 are distinct. So we may assume that φ0 (xi ) = i for
1 ≤ i ≤ 3. By construction of G0 , for all vertices u ∈ Ri0 , φ0 (u) 6= i. Therefore φ|R ∪ φ0 |V (G)−R is a
proper 3-coloring of G, a contradiction. 2

Claim 2. There is no R ( V (G) with |R| ≥ 2 and ρG (R) ≤ 5.

Proof. Let 2 ≤ |R| < |V (G)| and ρ(R) = m = min{ρ(W ) : W ( V (G), |W | ≥ 2}. Suppose
m ≤ 5. Then by Exercise 8, |R| ≥ 4. Since G is 4-critical, G[R] has a proper coloring φ : R →
C = {1, 2, 3}. Let G0 = Y (G, R, φ). By Claim 1, G0 is not 3-colorable. Then it contains a 4-critical
subgraph G00 . Let W = V (G00 ). Since |R| ≥ 4 > |X|, |V (G00 )| < |V (G)|. So, by the minimality of
G, ρG0 (W ) ≤ 2. Let X 0 = W ∩ X. Since G is 4-critical by itself, every proper subgraph of G is
3-colorable and so X 0 6= ∅. Since 0 < |X 0 | ≤ 3, by Exercise 8, ρG0 (X 0 ) ≥ 5. Since

|EG0 (W − X 0 , X 0 )| ≤ |EG0 (W − X 0 , X)| = |EG (W − X 0 , R)|,

by Exercise 9,

ρG ((W − X 0 ) + R) = ρG (W − X 0 ) + ρG (R) − 3|EG (W − X 0 , R)|

= ρG0 (W − X 0 ) + m − 3|EG0 (W − X 0 , X)| (28)

≤ ρG0 (W ) − ρG0 (X 0 ) + 3|EG0 (W − X 0 , X 0 )| + m − 3|EG0 (W − X 0 , X)|
≤ ρG0 (W ) − ρG0 (X 0 ) + m ≤ 2 − 5 + m.

15
Since W − X + R ⊃ R, |W − X + R| ≥ 2. Since ρG (W − X + R) < ρG (R), by the choice of R,
W − X + R = V (G). But then ρG (V (G)) ≤ m − 3 ≤ 2, a contradiction. 2

Claim 3. If R ( V (G), |R| ≥ 2 and ρk (R) ≤ 6, then R is a K3 .

Proof. Let R have the smallest ρ(R) among R ( V (G), |R| ≥ 2. Suppose m = ρ(R) ≤ 6 and
G[R] 6= K3 . Then |R| ≥ 4. By Claim 2, m = 6.
Let R∗ = {u1 , . . . , us } be the set of vertices in R that have neighbors outside of R. Because G is
2-connected, s ≥ 2. Let H = G[R] + u1 u2 . Since R 6= V (G), |V (H)| < |V (G)|. By the minimality
of ρ(R), for every U ⊆ R with |U | ≥ 2, ρH (U ) ≥ ρG (U ) − 3 ≥ ρG (R) − 3 ≥ 3. Thus P (H) ≥ 3,
and by (27), H has a proper 3-coloring φ with colors in C = {1, 2, 3}. Let G0 = Y (G, R, φ).
Since |R| ≥ 4, |V (G0 )| < |V (G)|. By Claim 1, G0 is not 3-colorable. Thus G0 contains a 4-critical
subgraph G00 . Let W = V (G00 ). By the minimality of |V (G)|, ρG0 (W ) ≤ 2. Since G is 4-critical
by itself, W ∩ X 6= ∅. Let X 0 = W ∩ X. By Exercise 8, if |X 0 | ≥ 2 then similarly to (28),
ρk,G (W − X 0 + R) ≤ ρG0 (W ) − 6 + 6 ≤ 2, a contradiction again. So, we may assume that X 0 = {x1 }.
Then again as in (28),

ρG (W − {x1 } + R) ≤ (ρG0 (W ) − 5) + ρG (R) ≤ ρG (R) − 3. (29)

By the minimality of ρG (R), W − {x1 } + R = V (G). This implies that W = V (G0 ) − X + x1 .

Let R1 = {u ∈ R∗ : φ(u) = φ(x1 )}. If |R1 | = 1, then ρG (W − x1 ∪ R1 ) = ρH (W ) ≤ 2, a
contradiction. Thus, |R1 | ≥ 2. Since R1 is an independent set in H and u1 u2 ∈ E(H), we may
assume that u2 ∈ / R1 . Then EG0 (W − x1 , X − x1 ) 6= ∅. So, in this case repeating the argument of
(28), instead of (29) we have

ρG (W − {x1 } + R) ≤ ρG0 (W ) − 5 + ρG (R) − 3|EG0 (W − x1 , X − x1 )| ≤ ρG (R) − 6 ≤ 0. 2

Claim 4. G does not contain K4 − e.

Proof. If G[R] = K4 − e, then ρG (R) = 5(4) − 3(5) = 5, a contradiction to Claim 3. 2

Claim 5. Each triangle in G contains at most one vertex of degree 3.

Proof. By contradiction, assume that G[{x1 , x2 , x3 }] = K3 and d(x1 ) = d(x2 ) = 3. Let

N (x1 ) = X − x1 + a and N (x2 ) = X − x2 + b. By Claim 4, a 6= b. Define G0 = G − {x1 , x2 } + ab.
Because ρG (W ) ≥ 6 for all W ⊆ G − {x1 , x2 } with |W | ≥ 2, and adding an edge decreases the
potential of a set by 3, P (G0 ) ≥ min{5, 6 − 3} = 3. So, by (27), G0 has a proper 3-coloring φ0 with
φ0 (a) 6= φ0 (b). This easily extends to a proper 3-coloring of G. 2

Claim 6. Let xy ∈ E(G) and d(x) = d(y) = 3. Then both, x and y are in triangles.

Proof. Assume that x is not in a K3 . Suppose N (x) = {y, u, v}. Then uv ∈ / E(G). Let G0
be obtained from G − y − x by gluing u and v into a new vertex u ∗ v. Then |V (G0 )| < |V (G)|.
If G0 has a 3-coloring φ0 : V (G0 ) → C = {1, 2, 3}, then we extend it to a proper 3-coloring φ

16
of G as follows: define φ|V (G)−x−y−u−v = φ0 |V (G0 )−u∗v , then let φ(u) = φ(v) = φ0 (u ∗ v), choose
φ(y) ∈ C − (φ0 (N (y) − x)), and φ(x) ∈ C − {φ(y), φ(u)}.
So, χ(G0 ) ≥ 4 and G0 contains a 4-critical subgraph G00 . Let W = V (G00 ). Since G00 is smaller
than G, ρG0 (W ) ≤ 2. Since G00 is not a subgraph of G, u ∗ v ∈ W . Let W 0 = W − u ∗ v + u + v + x.
Then ρG (W 0 ) ≤ 2 + 5(2) − 3(2) = 6, since G[W 0 ] has two extra vertices and at least two extra
edges in comparison with G00 . Because y ∈ / W 0 , we have W 0 6= V (G), and therefore by Claim 3, W
induces a K3 in G. This contradicts our assumption that x is not in a K3 . 2

By Claims 5 and 6, we have

Each vertex of degree 3 has at most one neighbor of degree 3. (30)

We will now use discharging to show that |E(G)| ≥ 35 |V (G)|, which will finish the proof to Case
k = 4 of Theorem 13. Each vertex begins with charge equal to its degree. If d(v) ≥ 4, then v gives
charge 16 to each neighbor with degree 3. Note that v will be left with charge at least 65 d(v) ≥ 10
3 .
By (30), each vertex of degree 3 will end with charge at least 3 + 6 = 3 . 2
2 10

7 Triangle-free graphs, hypergraphs and unsolved problems

Kostochka and Stiebitz [37] proved that for large k and n > k, k-critical n-vertex triangle-free
graphs must have almost 2f (n, k) edges. Asymptotically (in k) this is best possible: Some simple
constructions of k-critical n-vertex graphs of arbitrary girth with average degree at most 2k − 1
one can find in [33]. For small k, Postle [48, 49] recently obtained nice results. He proved that the
asymptotical average degree for 4-critical graphs of girth 5 must be larger (not much, but larger)
than the bound in Theorem 13. In [49] he proved a similar result for triangle-free 5-critical graphs.
But these bounds most likely are not sharp, and finding exact bounds is a challenging problem.
The situation with hypergraphs with no graph edges is similar: it is proved in [37] that for large
k, k-critical n-vertex hypergraphs must have almost 2f (n, k) edges, and constructions in [33] show
that this bound for large k is asymptotically best. Again, exact bounds are not known, and values
for small k ≥ 4 are not known.
For list coloring, recently Kierstead and Rabern [32] and Rabern [51] using new ideas significantly
improved the lower bounds on f` (n, k). Still, asymptotics of f` (n, k) is not known.
Another challenge is to prove Ore’s Conjecture in full.
Many interesting unsolved problems on k-critical graphs are in [29]. In particular, there and
in [56] the following problem by Dirac and Erdős is stated:

What is the maximum number of edges h(n, k) in a k-critical n-vertex graph, when k is fixed
and n is large?
Even for k = 6, h(n, 6) is quadratic in n: for n = 4t + 2, take two disjoint cycles C1 and C2 of
length 2t + 1 and join by an edge each vertex of C1 with each vertex of C2 . It is not proved that
this construction is best possible. Moreover, Toft [29][P. 97] conjectures that it is not best possible.
He has a construction of vertex-6-critical n-vertex graphs with at least 3n2 /10 edges.
Acknowledgment. Many thanks to Anton Bernshteyn for many helpful comments.

17
References
[1] V. Aksenov, Private communication (1976).
[2] N. Alon, Degrees and choice numbers, Random Structures Algorithms 16 (2000), 364–368.
[3] N. Alon and M. Tarsi, Colorings and orientations of graphs. Combinatorica 12 (1992), 125–134.
[4] O.V. Borodin, Criterion of chromaticity of a degree prescription (in Russian), in: Abstracts of
IV All-Union Conf. on Theoretical Cybernetics (Novosibirsk) 1977, 127-128.
[5] O.V. Borodin, Problems of colouring and of covering the vertex set of a graph by induced
subgraphs (in Russian), Ph.D.Thesis, Novosibirsk State University, Novosibirsk, 1979.
[6] O.V. Borodin, Colorings of plane graphs: A survey, Discrete Math. 313 (2013), 517–539.
[7] O. V. Borodin, Z. Dvořák, A. V. Kostochka, B. Lidický, and M. Yancey, Planar 4-critical
graphs with four triangles, European J. of Combinatorics 41 (2014), 138–151.
[8] O. V. Borodin, A. V. Kostochka, B. Lidický and M. Yancey, Short proofs of coloring theorems
on planar graphs, European J. of Combinatorics 36 (2014), 314–321.
[9] R. L. Brooks, On colouring the nodes of a network, Math. Proc. Cambridge Philos. Soc. 37
(1941), 194–197.
[10] G. A. Dirac, Note on the colouring of graphs, Math. Z. 54 (1951), 347-353.
[11] G. A. Dirac, A property of 4-chromatic graphs and some remarks on critical graphs, J. London
Math. Soc. 27 (1952), 85–92.
[12] G. A. Dirac, Some theorems on abstract graphs, Proc. London Math. Soc. (3) 2 (1952), 69–81.
[13] G.A. Dirac, The colouring of maps.Nature 169 (1952). 664.
[14] G.A. Dirac, Map-colour theorems, Canadian J. Math. 4 (1952). 480–490.
[15] G.A. Dirac, The structure of k-chromatic graphs, Fund. Math. 40, (1953). 42–55.
[16] G.A. Dirac, The colouring of maps, J. London Math. Soc. 28, (1953). 476–480.
[17] G.A. Dirac, Map colour theorems related to the Heawood colour formula, J. London Math.
Soc. 31 (1956), 460–471.
[18] G.A. Dirac, Short proof of a map-colour theorem, Canad J. Math. 9 (1957), 225–226.
[19] G.A. Dirac, Map colour theorems related to the Heawood colour formula, II, J. London Math.
Soc. 32 (1957), 436–455.
[20] G.A. Dirac, A theorem of R.L. Brooks and a conjecture of H. Hadwiger, Proc. London Math.
Soc. 7 (1957) 3, 161-195.
[21] G.A. Dirac, On the structure of 5- and 6-chromatic abstract graphs, J. Reine Angew. Math.
214–215 (1964) 43–52.
[22] G.A. Dirac, The number of edges in critical graphs, J. Reine Angew. Math. 268/269 (1974),
150-164.
[23] P. Erdős, A.L. Rubin, and H. Taylor, Choosability in graphs. In Proc. West Coast Conf.
Combinatorics, Graph Theory and Computing (Humboldt State Univ., Arcata, Calif., 1979),
Congr. Numer. 26 (1980), 125–157.

18
[24] B. Farzad and M. Molloy, On the edge-density of 4-critical graphs, Combinatorica 29 (2009),
665–689.
[25] T. Gallai, Kritische Graphen I, Publ. Math. Inst. Hungar. Acad. Sci. 8 (1963), 165-192.
[26] T. Gallai, Kritische Graphen II, Publ. Math. Inst. Hungar. Acad. Sci. 8 (1963), 373-395.
[27] H. Grötzsch, Zur Theorie der diskreten Gebilde. VII. Ein Dreifarbensatz für dreikreisfreie
Netze auf der Kugel. Wiss. Z. Martin-Luther-Univ. Halle-Wittenberg. Math.-Nat. Reihe 8
(1958/1959), 109–120 (in German).
[28] G. Hajós,Über eine Konstruktion nicht-n-färbbarer Graphen, Wiss. Z. Martin-Luther-Unive.
Halle-Wittenberg Math.-Natur. Reihe 10 (1961), 116–117.
[29] T. R. Jensen and B. Toft, Graph Coloring Problems, Wiley-Interscience Series in Discrete
Mathematics and Optimization, John Wiley & Sons, New York, 1995.
[30] H. A. Kierstead, A. V. Kostochka, Ore-type versions of Brook’s theorem, Journal of Combi-
natorial Theory, Series B. 99 (2009), 298–305.
[31] H. Kierstead and L. Rabern, Personal communication.
[32] H. Kierstead and L. Rabern, Extracting list colorings from large independent sets,
http://arxiv.org/pdf/1512.08130.pdf.
[33] A. V. Kostochka and J. Nesetril, Properties of Descartes’ construction of triangle-free graphs
with high chromatic number, Combin. Prob. Comput. 8 (1999), 467-472.
[34] A.V. Kostochka, M. Stiebitz and B. Wirth, The colour theorems of Brooks and Gallai extended,
Discrete Math. 162 (1996), 299-303.
[35] A. V. Kostochka, L. Rabern, and M. Stiebitz, Graphs with chromatic number close to maxi-
mum degree, Discrete Math. 312 (2012), 1273–1281.
[36] A. V. Kostochka and M. Stiebitz, Excess in colour-critical graphs, in: Graph Theory and
Combinatorial Biology, Balatonlelle (Hungary), 1996, Bolyai Society, Mathematical Studies 7,
Budapest, 1999, 87–99.
[37] A. V. Kostochka and M. Stiebitz, On the number of edges in colour-critical graphs and hyper-
graphs, Combinatorica 20 (2000), 521–530.
[38] A. V. Kostochka and M. Stiebitz, A new lower bound on the number of edges in colour-critical
graphs and hypergraphs, J. Comb. Theory, Series B. 87 (2003), 374–402.
[39] A. V. Kostochka and M. Yancey, Ore’s Conjecture on color-critical graphs is almost true, J.
Comb. Theory, Series B. 109 (2014), 73–101.
[40] A. V. Kostochka and M. Yancey, Ore’s Conjecture for k = 4 and Grötzsch Theorem, Combi-
natorica 34 (2014), 323–329.
[41] A. V. Kostochka and M. Yancey, A Brooks-type result for sparse critical graphs, submitted,
https://arxiv.org/pdf/1408.0846.pdf.
[42] M. Krivelevich, On the minimal number of edges in color-critical graphs, Combinatorica 17
(1997), 401–426.

19
[43] M. Krivelevich, An improved bound on the minimal number of edges in color-critical graphs,
Electron. J. Combin. 5 (1998), Research Paper 4, 4 pp.
[44] H. V. Kronk and J. Mitchem, On Dirac’s generalization of Brooks’ theorem, Canad. J. Math.
24 (1972), 805-807.
[45] C.-H. Liu and L. Postle, On the Minimum Edge-Density of 4-Critical Graphs of Girth Five,
http://arxiv.org/pdf/1409.5295.pdf.
[46] O. Ore, The Four Color Problem, Academic Press, New York, 1967.
[47] L. Postle, Characterizing 4-critical graphs with Ore-degree at most Seven,
http://arxiv.org/pdf/1409.5116.pdf.
5
[48] L. Postle, The edge-density of 4-critical graphs of girth 5 is 3 + , manuscript.
[49] L. Postle, On the Minimum Number of Edges in Triangle-Free 5-Critical Graphs,
http://arxiv.org/pdf/1602.03098.pdf.
[50] L. Rabern, ∆-critical graphs with small high vertex cliques. J. Combin. Theory Ser. B 102
(2012), 126–130.
[51] L. Rabern, A better lower bound on average degree of 4-list-critical graphs,
http://arxiv.org/pdf/1602.08532.pdf.
[52] R. Steinberg, The state of the three color problem, Quo Vadis, Graph Theory?, Ann. Discrete
Math., 55 (1993), 211–248.
[53] M. Stiebitz, Proof of a conjecture of T. Gallai concerning connectivity properties of colour-
critical graphs, Combinatorica 2 (1982), 315–323.
[54] B. Toft, Color-critical graphs and hypergraphs, J. Combin. Theory 16 (1974), 145–161.
[55] B. Toft, Personal communication.
[56] Zs. Tuza, Graph coloring, in: Handbook of graph theory. J. L. Gross and J. Yellen Eds., CRC
Press, Boca Raton, FL, 2004. xiv+1167 pp.
[57] V. G. Vizing, Colouring the vertices of a graph with prescribed colours (in Russian), Metody
Diskretnogo Analiza v Teorii Kodov i Skhem No. 29 (1976), 3-10.

20