On Dirac's Generalization of Brooks' Theorem

Kronk, Hudson V. ; Mitchem, John

Canadian journal of mathematics, Tome 24 (1972) no. 5, pp. 805-807

Résumé

It is easy to verify that any connected graph G with maximum degree s has chromatic number χ(G) ≦ 1 + s. In [1], R. L. Brooks proved that χ(G) ≦ s, unless s = 2 and G is an odd cycle or s > 2 and G is the complete graph Ks+1. This was the first significant theorem connecting the structure of a graph with its chromatic number. For s ≦ 4, Brooks' theorem says that every connected s-chromatic graph other than Ks contains a vertex of degree > s — 1. An equivalent formulation can be given in terms of s-critical graphs. A graph G is said to be s-critical if χ(G) = s, but every proper subgraph has chromatic number less than s. Each scritical graph has minimum degree ≦ s — 1. We can now restate Brooks' theorem: if an s-critical graph, s ≦ 4, is not Ks and has p vertices and q edges, then 2q ≦ (s — l)p + 1. Dirac [2] significantly generalized the theorem of Brooks by showing that 2q ≦ (s — 1)£ + s — 3 and that this result is best possible.

Détail

DOI : 10.4153/CJM-1972-078-3

Bibliographie

[1] 1. Brooks, R. L., On coloring the nodes of a network, Proc. Cambridge Philos. Soc. 37 (1941), 194–197. Google Scholar

[2] 2. Dirac, G. A., A theorem of R. L. Brooks and a conjecture of H. Hadwiger, Proc. London Math. Soc. 7 (1957), 161–195. Google Scholar

[3] 3. Dirac, G. A., Short proof of a map-colour theorem, Can. J. Math. 9 (1957), 225–226. Google Scholar

[4] 4. Melnikov, L. S. and Vizing, V. G., New proof of Brooks’ theorem, J. Combinatorial Theory 7 (1969), 289–290. Google Scholar