Premium
A list version of Dirac's theorem on the number of edges in colour‐critical graphs
Author(s) -
Kostochka Alexandr V.,
Stiebitz Michael
Publication year - 2002
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.998
Subject(s) - mathematics , combinatorics , dirac (video compression format) , graph , discrete mathematics , critical graph , petersen graph , line graph , graph power , physics , neutrino , nuclear physics
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