Vertex Coloring

Vertex coloring, a type of graph coloring, involves assigning colors to the vertices of a graph such that no two adjacent vertices share the same color. This has applications in scheduling and routing problems, resource allocation, computer networking, and machine learning.

Tags: Theory

Proper Colorings

A proper coloring (or, more simply, a coloring) of a graph G, is an assignment of colors (elements of some set) to the vertices of G, one color to each vertex, such that adjacent vertices are colored differently. A coloring using k-colors is called a k-coloring. As seen below, the colors used to color a graph can be denoted both numerically (1, 2, ... , k) and visually (e.g. red, green, blue).

Figure 1. A 3-coloring of two graphs

Minimum Colorings

The chromatic number of a graph G is the minimum number of colors needed in any coloring of G, denoted by χ(G). A minimum coloring of a graph G is a k-coloring of G such that k = χ(G).

Figure 2. A minimum coloring of a bipartite graph

Bounding the Chromatic Number

For every graph G,

χ(G) ≤ ∆(G) + 1,

where ∆(G) is the maximum degree of the graph, or the largest number of neighbors of any vertex. For any connected graph that is not an odd cycle or a complete graph, however, the upper bound reduces to

χ(G) ≤ ∆(G).

This relationship is known as Brooks' theorem.

Figure 3. A vertex with the maximum color

Determining the Chromatic Number

Determining the chromatic number of a graph is extremely challenging and is known as an NP-Complete problem. Algorithms exist for coloring graphs, but they are not guaranteed to use the minimum number of colors.

Greedy Algorithm

for each v in V(G) do
    neighborColors = {color(u) | u in N(v)}
    c = 1
    while c in neighborColors do
        c = c + 1
    end while
    color(v) = c
end for