Brooks' theorem
The set of Brooks is a ceiling on the number of colors , which are needed to all nodes of a graph coloring so that no two adjacent nodes have the same color.
statement
The vertex color number of a connected graph that is neither complete nor a circle of odd length is at most as high as the maximum degree of the graph.
Addition: If the graph is complete or a circle of odd length, you need a maximum degree + 1 colors.
literature
- Reinhard Diestel: graph theory. 3. Edition. Springer-Verlag, Heidelberg 2006, ISBN 3-540-21391-0 , p. 125.
Web links
- Eric W. Weisstein : Brooks' Theorem . In: MathWorld (English).