The colour theorems of Brooks and Gallai extended

A. V. Kostochka, M. Stiebitz, B. Wirth

Research output: Contribution to journalArticlepeer-review


One of the basic results in graph colouring is Brooks' theorem [4] 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, Gallai [6] characterized the subgraphs of k-colour-critical graphs induced by the set of all vertices of degree k - 1. The choosability version of Brooks' theorem was proved, independently, by Vizing [9] and by Erdös et al. [5]. As Thomassen pointed out in his talk at the Graph Theory Conference held at Oberwolfach, July 1994, one can also prove a choosability version of Gallai's result. All these theorems can be easily derived from a result of Borodin [2,3] and Erdös et al. [5] which enables a characterization of connected graphs G admitting a color scheme L such that |L(x)| ≥ dG(x) for all x ∈ V(G) and there is no L-colouring of G. In this note, we use a reduction idea in order to give a new short proof of this result and to extend it to hypergraphs.

Original languageEnglish (US)
Pages (from-to)299-303
Number of pages5
JournalDiscrete Mathematics
Issue number1-3
StatePublished - Dec 25 1996
Externally publishedYes

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Discrete Mathematics and Combinatorics


Dive into the research topics of 'The colour theorems of Brooks and Gallai extended'. Together they form a unique fingerprint.

Cite this