Name
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 |
Year | DOI | Venue |
|---|---|---|
2002 | 10.1002/jgt.v39:3 | Journal of Graph Theory |
Keywords | Field | DocType |
list colourings,critical graphs | Discrete mathematics,Combinatorics,Graph power,Cubic graph,Cycle graph,Toroidal graph,Brooks' theorem,Graph minor,Petersen graph,Extremal graph theory,Mathematics | Journal |
Volume | Issue | ISSN |
39 | 3 | 0364-9024 |
Citations | PageRank | References |
9 | 0.83 | 4 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Alexandr V. Kostochka | 1 | 682 | 89.87 |
| Michael Stiebitz | 2 | 207 | 30.08 |