Brooks' Theorem

The chromatic number of a graph is at most the maximum vertex degree Delta, unless the graph is complete or an odd cycle, in which case Delta+1 colors are required.

See also

Chromatic Number, Vizing's Theorem

Explore with Wolfram|Alpha


Brooks, R. L. "On Coloring the Nodes of a Network." Proc. Cambridge Philos. Soc. 37, 194-197, 1941.Lovász, L. "Three Short Proofs in Graph Theory." J. Combin. Th. Ser. B 19, 111-113, 1975.Skiena, S. Implementing Discrete Mathematics: Combinatorics and Graph Theory with Mathematica. Reading, MA: Addison-Wesley, p. 215, 1990.

Referenced on Wolfram|Alpha

Brooks' Theorem

Cite this as:

Weisstein, Eric W. "Brooks' Theorem." From MathWorld--A Wolfram Web Resource.

Subject classifications