The colour theorems of Brooks and Gallai extended

✍ Scribed by A.V. Kostochka; M. Stiebitz; B. Wirth

• Publisher: Elsevier Science
• Year: 1996
• Tongue: English
• Weight: 283 KB
• Volume: 162
• Category: Article
• ISSN: 0012-365X
• DOI: 10.1016/0012-365x(95)00294-7

✦ Synopsis

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 ErdiSs 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 Erd6s et al. [-5] which enables a characterization of connected graphs G admitting a color scheme L such that IL(x)l ~> d~(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.