The colour theorems of Brooks and Gallai extended

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)| ≥ d_G(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.