Chromatic Number, Relation to Max Degree

Question

The chromatic number of G is denoted as χ(G) and is defined as the smallest number of colors needed to color the graph so that no two adjacent nodes receive the same color. Using a greedy coloring algorithm prove that the χ(G) ≤ ∆(G)+1, where ∆(G) is the largest degree in the graph.

Answer 1

Use mathematical induction for fully connected graphs. There are at least two colors for one edge and at least three for triangles. And so on.

Answer 2

Let the vertices of a graph G be v 1 , v 2 , ..., v n and the maximum degree of G be ∆ .
For i = 1, 2, ..., n we color v i with the smallest number that is available, i.e., the number that has not been used on the vertices in {v 1 , v 2 , ..., v i−1 } that are adjacent to v i .
Since there are at most ∆ vertices that are adjacent to v i , this algorithm will not use more than ∆ + 1 colors. Therefore, we have χ(G) ≤ ∆(G)+1 .