Graph colouring

#matematik-discmath

Definition: Vertex colouring, chromatic number

A vertex colouring of a Graph is a function such that for every adjacent pair of vertices .

The chromatic number is the least integer for which there is a vertex colouring of using colours.

Equivalently, a vertex colouring is a partition of the vertices such that no two vertices in the same partition are adjacent. A greedy way to find a vertex colouring is to color the first vertex with some color, then for each non-colored vertex, color it with an already used color if possible, otherwise a new color. Note that this algorithm does not garuantee a colouring with minimal colors.

Theorem

Let be a graph with maximum degree . Then .
Furthermore, if is connected and not Regular, then .