Brooks' theorem

from Wikipedia, the free encyclopedia
Complete graphs require one more color than their maximum degree.

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