The chromatic number of a graph is at most the maximum vertex degree 
, unless the graph is complete
or an odd cycle, in which case 
colors are required.
Brooks' Theorem
See also
Chromatic Number, Vizing's TheoremExplore with Wolfram|Alpha
References
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' TheoremCite this as:
Weisstein, Eric W. "Brooks' Theorem." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/BrooksTheorem.html