An improved bound on the minimal number of edges in

color-critical graphs

Michael Krivelevich ^{∗} School of Mathematics, Institute for Advanced Study, Princeton, NJ 08540, USA. AMS Subject Classification: 05C15, 05C35. Submitted: June 26, 1997. Accepted: November 24, 1997.

Abstract

It is proven that for k ≥ 4 and n > k every k-color-critical graph on n vertices has at least (\frac{k−1}{2} + \frac{k−3}{2(k^{2}−2k−1)}) n edges, thus improving a result of Gallai from 1963.

A graph G is k-color-critical (or simply k-critical) if χ(G) = k but χ(G′) < k for every proper subgraph G′ of G, where χ(G) denotes the chromatic number of G. (See, e.g., [2] for a detailed account of graph coloring problems). Consider the following problem: given k and n, what is the minimal number of edges in a k-critical graph on n vertices? It is easy to see that every vertex of a k-critical graph G has degree at least k − 1, implying |E(G)| ≥ \frac{k−1}{2}|V (G)|. Gallai [1] improved this trivial bound to |E(G)| ≥ (\frac{k−1}{2} + \frac{k−3}{2(k^{2}−3)}) |V (G)| for every k-critical graph G (where k ≥ 4), which is not a clique K_{k} on k vertices. In this note we strengthen Gallai’s result by showing

Theorem 1 Suppose k ≥ 4, and let G = (V, E) be a k-critical graph on more than k vertices. Then

|E(G)| ≥ (\frac{k − 1}{2} + \frac{k − 3}{2(k^{2} − 2k − 1)}) |V (G)| .

∗e-mail: mkrivel@math.ias.edu

the electronic journal of combinatorics 1 (1998), #R4 2 In the first non-trivial case k = 4 we get |E(G)| ≥ \frac{11}{7}|V (G)|, compared to the estimate |E(G)| ≥ \frac{20}{13}|V (G)| of Gallai.

Let us introduce some definitions and notation (we follow the terminology of [4]). If G = (V, E) is a k-critical graph, then the low-vertex subgraph of G, denoted by L(G), is the subgraph of G, induced by all vertices of degree k − 1. The high-vertex subgraph of G, which we denote by H(G), is the subgraph of G induced by all vertices of degree at least k in G. Brooks’ theorem implies that if k ≥ 4 and G ≠ K_{k}, then H(G) ≠ ∅. A maximal by inclusion connected subgraph B of a graph G such that every two edges of B are contained in a cycle of G is called a block of G. A connected graph all of whose blocks are either complete graphs or odd cycles is called a Gallai tree, a Gallai forest is a graph all of whose connected components are Gallai trees. A k-Gallai forest (tree) is a Gallai forest (tree), in which all vertices have degree at most k − 1.

Our proof utilizes results of Gallai [1] and Stiebitz [5], describing the structure of colorcritical graphs. Gallai proved the following fundamental result.

Lemma 1 ([1], Satz E.1) If G is a k-critical graph then its low-vertex subgraph L(G) is a k-Gallai forest (possibly empty).

Using induction on the number of vertices, it follows from the above statement that

Lemma 2 ([1], Lemma 4.5) Let k ≥ 4. Let G = (V, E) ≠ K_{k} be a k-Gallai forest. Then

|E(G)| ≤ (\frac{k − 2}{2} + \frac{1}{k − 1}) |V (G)| − 1 .  (1)

The second ingredient of our proof is the following result of Stiebitz.

Lemma 3 ([5]) Let G be a k-critical graph containing at least one vertex of degree k − 1. Then the number of connected components of its high-vertex subgraph H(G) does not exceed the number of connected components of its low-vertex subgraph L(G).

Proof of Theorem 1. Let L(G) and H(G) be the low-vertex and the high-vertex subgraphs of G, respectively. Denote n_{L} = |V (L(G))|, n_{H} = |V (H(G))|, n = |V (G)| = n_{L} + n_{H}. By Brooks’ theorem n_{H} > 0. Also, if V (L(G)) = ∅, we are done, therefore we may assume that n_{L} > 0.

Let r be the number of connected components of H(G), then trivially

|E(H(G))| ≥ n_{H} − r .  (2)

Also, by Lemma 3, the number of connected components of L(G) is at least r. Now the crucial observation is that each connected component of L(G) is itself a k-Gallai tree, therefore the estimate (1) is valid for it too. We infer that

|E(L(G))| ≤ (\frac{k − 2}{2} + \frac{1}{k − 1}) n_{L} − r .  (3)

Indeed, if G_{1} = (V_{1}, E_{1}), …, G_{r′} = (V_{r′}, E_{r′}) are the connected components of L(G′), where r′ ≥ r, then by Lemma 1

|E_{i}| ≤ (\frac{k − 2}{2} + \frac{1}{k − 1}) |V_{i}| − 1 , i = 1, …, r′ .

Summing the above inequalities over 1 ≤ i ≤ r′, we get (3).

Using (2) and (3), the number of edges of G can be bounded from below as follows:

|E(G)| = ∑_{v∈V (L(G))} d(v) − |E(L(G))| + |E(H(G))|
≥ (k − 1)n_{L} − (\frac{k − 2}{2} + \frac{1}{k − 1}) n_{L} + r + n_{H} − r
= n + \frac{k^{2} − 3k}{2(k − 1)} n_{L} .  (4)

On the other hand, it follows from the definition of L(G) and H(G) that

|E(G)| = \frac{1}{2} ∑_{v∈V (G)} d(v) = \frac{1}{2} ( ∑_{v∈V (L(G))} d(v) + ∑_{v∈V (H(G))} d(v))
≥ \frac{1}{2}((k − 1)n_{L} + kn_{H}) = \frac{k}{2}n − \frac{1}{2}n_{L} .  (5)

Multiplying (5) by (k^{2} − 3k)/(k − 1) and summing with (4) we get

(1 + \frac{k^{2} − 3k}{k − 1} ) |E(G)| ≥ (1 + \frac{k}{2} \frac{k^{2} − 3k}{k − 1} ) n ,

or

|E(G)| ≥ (\frac{k − 1}{2} + \frac{k − 3}{2(k^{2} − 2k − 1)}) n ,

as claimed. □

A more detailed treatment of the problem, containing lower and upper bounds on the minimal number of edges in a k-critical graph on n vertices with additional restrictions imposed, and some applications of these bounds to Ramsey-type problems and problems on random graphs, will appear in a forthcoming paper [3].

References

[1] T. Gallai, Kritische Graphen I, Publ. Math. Inst. Hungar. Acad. Sci. 8 (1963), 265–292.

[2] T. R. Jensen and B. Toft, Graph coloring problems, Wiley, New York, 1995.

[3] M. Krivelevich, On the minimal number of edges in color-critical graphs, Combinatorica, to appear.

[4] H. Sachs and M. Stiebitz, Colour-critical graphs with vertices of low valency, Annals of Discrete Math. 41 (1989), 371–396.

[5] M. Stiebitz, Proof of a conjecture of T. Gallai concerning connectivity properties of colour-critical graphs, Combinatorica 2 (1982), 315–323.