## Abstract

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.

Original language | English (US) |
---|---|

Pages (from-to) | 299-303 |

Number of pages | 5 |

Journal | Discrete Mathematics |

Volume | 162 |

Issue number | 1-3 |

DOIs | |

State | Published - Dec 25 1996 |

Externally published | Yes |

## ASJC Scopus subject areas

- Theoretical Computer Science
- Discrete Mathematics and Combinatorics