A list version of Dirac's theorem on the number of edges in colour-critical graphs
✍ Scribed by Alexandr V. Kostochka; Michael Stiebitz
- Publisher
- John Wiley and Sons
- Year
- 2002
- Tongue
- English
- Weight
- 110 KB
- Volume
- 39
- Category
- Article
- ISSN
- 0364-9024
- DOI
- 10.1002/jgt.998
No coin nor oath required. For personal study only.
✦ Synopsis
Abstract
One of the basic results in graph colouring is Brooks' theorem [R. L. Brooks, Proc Cambridge Phil Soc 37 (1941) 194–197], which asserts that the chromatic number of every connected graph, that is not a complete graph or an odd cycle, does not exceed its maximum degree. As an extension of this result, Dirac [G. A. Dirac, Proc London Math Soc 7(3) (1957) 161–195] proved that every k‐colour‐critical graph (k ≥ 4) on n ≥ k + 2 vertices has at least ½((k − 1) n + k − 3) edges. The aim of this paper is to prove a list version of Dirac's result and to extend it to hypergraphs. © 2002 Wiley Periodicals, Inc. J Graph Theory 39: 165–177, 2002; DOI 10.1002/jgt.998