◀ ▲ ▶Branches / Graph-theory / Theorem: Brooks' Theorem

This theorem is a stronger result about an upper bound for the chromatic number due to Rowland Leonard Brooks (1916 – 1993).

Theorem: Brooks' Theorem

Let $G$ be a connected simple graph with the maximum vertex degree $d.$ If $G$ is neither a cycle with an odd number of vertices, nor a complete graph, then the chromatic number of $G$ obeys the following inequality: $$\chi(G)\le d.$$

Table of Contents

Proofs: 1

Thank you to the contributors under CC BY-SA 4.0!

Github:

References

Bibliography

1. Aldous Joan M., Wilson Robin J.: "Graphs and Applications - An Introductory Approach", Springer, 2000