Brook's theorem
The paper gives an overview on Brook's theorem, which relates the chromatic number to the maximum degree of a graph.NEWLINENEWLINEAt first, known proofs of the theorem are presented and then developments of the subject are shown. So, critical graphs and bounds of the chromatic number in terms of the clique number and the maximum degree are introduced and explained through known results. Other concepts, such as the list-chromatic number and the equitable chromatic number, arose around the problem of colouring a graph. In this context, this paper is an interesting survey, providing an introduction to the problems that have been studied and to the main unsolved conjectures that arose in these years.NEWLINENEWLINEFor the entire collection see [Zbl 1317.05004].
- Brook Taylor and the method of increments
- Partitioning sparse graphs into an independent set and a forest of bounded degree
- A Brooks type theorem for the maximum local edge connectivity
- On the connection between chromatic number, maximal clique and minimal degree of a graph
- Variable degeneracy: Extensions of Brooks' and Gallai's theorems
- The minimum number of edges in 4-critical digraphs of given order
- Brooks' Theorem and Beyond
- A Brooks-type theorem for the bichromatic number
- scientific article; zbMATH DE number 125481 (Why is no real title available?)
- scientific article; zbMATH DE number 7641240 (Why is no real title available?)
- Brooks' Theorem
- Brooks' theorem in graph streams: a single-pass semi-streaming algorithm for \(\Delta\)-coloring
This page was built for publication: Brook's theorem
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2822589)
