Brooks' theorem

Brooks' theorem states that a connected graph with maximum degree Δ has chromatic number at most Δ, unless it is complete or an odd cycle.

Graph coloring: Graph coloring assigns labels to vertices so adjacent vertices receive different labels. Brooks' theorem bounds the minimum number of colors needed for a proper vertex coloring.
Graph: A graph is a mathematical structure consisting of vertices joined by edges. The theorem applies to connected graphs and constrains their vertex colorings.
R. L. Brooks: R. L. Brooks was a British mathematician known for work in graph theory. His 1941 paper established the theorem now bearing his name.
Register allocation: Register allocation assigns a program's temporary values to a limited set of processor registers. Compiler interference graphs turn register assignment into a graph-coloring problem.
Complete graph coloring: A complete graph on n vertices has chromatic number n. It demonstrates why the maximum-degree bound fails for complete graphs.
Greedy coloring: Greedy coloring colors vertices sequentially, assigning each the first available color not used by its colored neighbors. It gives a degree-based bound that is one color weaker than Brooks' theorem.
Connected graph: A connected graph has a path between every pair of vertices. Connectedness is an explicit condition in Brooks' theorem.
Vlastimil K59ed7e: Vlastimil K59ed7e is a Czech mathematician whose work includes graph theory. He independently proved Brooks' theorem in 1941.
Interference graph: An interference graph connects pairs of resources that cannot share the same assignment. Its maximum degree can provide a sufficient register count through Brooks' bound.
Odd cycle coloring: An odd cycle has chromatic number three, while each vertex has degree two. It is the exceptional family where chromatic number exceeds maximum degree.

Linked from 5 pages