Graph Coloring Visualization

Graph coloring

A proper coloring of an undirected graph gives every vertex a color so that the two ends of every edge get different colors. Colors are just labels, so we number them 1, 2, 3, …. A graph that has a proper coloring with at most k colors is k-colorable, and the smallest such k is the graph's chromatic number, written χ(G).

Some quick facts help with intuition. A graph with no edges has χ = 1. A graph with at least one edge and no cycle of odd length (a bipartite graph, such as any tree or an even cycle) has χ = 2. An odd cycle, such as a triangle, needs 3. The complete graph K_n, where every pair of the n vertices is joined, needs n. More generally, if k vertices are all joined to each other (a clique), the graph needs at least k colors, but it may need more.

The idea behind every method on this page is the same: color the vertices one at a time and never give a vertex a color that one of its already-colored neighbors has. The methods differ in which order they take the vertices and in whether they are allowed to go back and change an earlier choice.

Where coloring is used

Coloring shows up whenever things that conflict must be kept apart, and the colors are the resources they compete for:

• Exam and timetable scheduling: each exam is a vertex, an edge joins two exams that share a student, and each color is a time slot. A proper coloring is a timetable in which no student has two exams at once; χ is the fewest slots needed.
• Register allocation: a compiler builds an interference graph whose vertices are the program's variables, joining two that are alive at the same time. Colors are CPU registers; a variable that cannot be colored is "spilled" to memory.
• Map coloring: countries are vertices and countries that share a border are joined. The graph of a map drawn in the plane is planar, and the four color theorem (Appel and Haken, 1976) says every planar graph is 4-colorable.
• Frequency assignment: radio transmitters that are close enough to interfere are joined, and colors are frequencies. Sudoku is also a coloring puzzle: each cell is a vertex, cells in the same row, column or box are joined, and the colors are 1 to 9.

Greedy coloring

Greedy coloring takes the vertices in a fixed order and gives each one the smallest color that none of its already-colored neighbors uses. It never changes a color once it is given. Step by step:

1. Choose an order of the vertices (on this page, Greedy uses 0, 1, 2, …).
2. Take the next vertex v in the order. Collect the colors of its neighbors that already have one. Neighbors with no color yet are ignored: they will look at v when their own turn comes.
3. Give v the smallest color c ≥ 1 that is not in that set.
4. Repeat until every vertex has a color.

greedyColoring(G, order):
    for each vertex v:  color[v] = 0          // 0 = no color yet
    for each vertex v in order:
        used = empty set
        for each neighbor u of v:
            if color[u] != 0:  add color[u] to used
        c = 1
        while c is in used:  c = c + 1
        color[v] = c
    return color

Why at most Δ + 1 colors. Let Δ be the largest degree in the graph. When greedy reaches a vertex v of degree d, at most d of its neighbors have a color, so at most d of the d + 1 colors 1, 2, …, d + 1 are taken, and one of them is free. So every vertex gets a color at most d + 1 ≤ Δ + 1, whatever the order. The result is always proper, because each vertex avoids the colors of the neighbors colored before it, and every edge has one end that was colored after the other.

A worked example

We use one small graph for all three algorithms. It has 6 vertices and 7 edges:

edges:  0–1   0–2   1–2   1–4   2–4   3–4   3–5

vertex   neighbors   degree
  0      1, 2          2
  1      0, 2, 4       3
  2      0, 1, 4       3
  3      4, 5          2
  4      1, 2, 3       3
  5      3             1

Vertices 0, 1 and 2 form a triangle, so at least 3 colors are needed, and 3 are enough (see the backtracking trace below), so χ = 3.

Greedy in the order 0, 1, 2, 3, 4, 5:

vertex  colored neighbors (their colors)   colors taken   chosen
  0     none                               { }            1
  1     0 (1)                              {1}            2
  2     0 (1), 1 (2)                       {1, 2}         3
  3     none  (4 and 5 have no color yet)  { }            1
  4     1 (2), 2 (3), 3 (1)                {1, 2, 3}      4   ← a fourth color
  5     3 (1)                              {1}            2

Greedy uses 4 colors although 3 are enough. The trouble is vertex 3: it was colored 1 before its neighbor 4, and vertex 4 then saw all of 1, 2 and 3 among its neighbors. Nothing was wrong with any single step; the order was simply unlucky. This is why greedy is only a heuristic. (For every graph some order makes greedy optimal: list the vertices of an optimal coloring class by class. But finding such an order is as hard as the coloring problem itself.)

Welsh-Powell: largest degree first

Welsh and Powell (1967) proposed a better order: sort the vertices by degree, largest first, and color greedily in that order. Vertices with many neighbors are the hardest to fit in, so they choose while most colors are still free, and vertices with few neighbors, which can always squeeze in, come last. This page breaks ties between equal degrees by the smaller vertex number.

welshPowell(G):
    order = vertices sorted by degree, largest first
            (ties: smaller vertex number first)
    return greedyColoring(G, order)

Welsh and Powell described the method one color at a time: walk down the sorted list and give color 1 to every uncolored vertex that is not next to a vertex already colored 1; then walk down it again with color 2, and so on until every vertex is colored. That gives exactly the same coloring as greedy with the sorted order. (A vertex v gets color c in the walk for c exactly when c is the smallest color that no neighbor earlier in the list has.)

On the example: the degrees give the order 1, 2, 4 (degree 3), then 0, 3 (degree 2), then 5 (degree 1).

vertex  colored neighbors (their colors)   colors taken   chosen
  1     none                               { }            1
  2     1 (1)                              {1}            2
  4     1 (1), 2 (2)                       {1, 2}         3
  0     1 (1), 2 (2)                       {1, 2}         3
  3     4 (3)   (5 has no color yet)       {3}            1
  5     3 (1)                              {1}            2

Three colors, the optimum: the color classes are {1, 3}, {2, 5} and {0, 4}. Vertex 4, which caused the trouble before, now chooses before its low-degree neighbor 3.

Welsh-Powell is still a heuristic. Sorting guarantees a slightly better bound, since the i-th vertex of the list (degree d_i) has at most i − 1 earlier neighbors and so gets a color at most min(i, d_i + 1), but it can still use more colors than needed. When all degrees are equal it is just greedy in number order: on the 6-cycle with edges 0–3, 3–4, 4–1, 1–2, 2–5, 5–0 (every degree is 2, and χ = 2 because the cycle is even) it colors 0, 1 → 1, then 2, 3 → 2, then 4, 5 → 3, so it uses 3 colors.

Backtracking with m colors

The greedy methods are fast but cannot tell whether a better coloring exists. To answer the m-coloring question, "can this graph be colored with at most m colors?", backtracking searches through the possible colorings, but abandons a partial coloring as soon as it breaks the rule:

1. Take the vertices in a fixed order. For the next vertex v, try colors 1, 2, …, m in turn.
2. A color c is allowed if no already-colored neighbor of v has c. If it is allowed, give it to v and go on to the next vertex; if not (a conflict), try the next color.
3. If every vertex gets a color, stop: the graph is m-colorable.
4. If no color is allowed for v (a dead end), backtrack: go back to the previous vertex, remove its color, and let it try its next color.
5. If the first vertex runs out of colors, every possibility has failed: the graph is not m-colorable.

colorFrom(k):                        // order[0 .. k-1] already have colors
    if k == n:  return true          // every vertex has a color
    v = order[k]
    for c = 1 to m:
        if no neighbor of v has color c:
            color[v] = c             // try it
            if colorFrom(k + 1):  return true
            color[v] = 0             // undo, then try the next color
    return false                     // dead end: the caller backtracks

isColorable(G, m):
    for each vertex v:  color[v] = 0
    return colorFrom(0)

On the example with m = 3, in the order 0, 1, 2, 3, 4, 5 (✗ = conflict, ✓ = allowed):

 1. vertex 0: color 1 ✓
 2. vertex 1: color 1 ✗ (neighbor 0 has 1)    color 2 ✓
 3. vertex 2: color 1 ✗ (0)    color 2 ✗ (1)    color 3 ✓
 4. vertex 3: color 1 ✓        (its neighbors 4 and 5 have no color yet)
 5. vertex 4: color 1 ✗ (3)    color 2 ✗ (1)    color 3 ✗ (2)
              dead end → backtrack: uncolor 3, try its next color
 6. vertex 3: color 2 ✓
 7. vertex 4: color 1 ✓        (neighbors 1, 2, 3 have 2, 3, 2)
 8. vertex 5: color 1 ✓        (neighbor 3 has 2)
 result: 0→1, 1→2, 2→3, 3→2, 4→1, 5→1     13 tries, 1 backtrack

Backtracking repaired exactly the choice that made greedy use a fourth color: once vertex 4 was stuck, it undid vertex 3's color 1 and tried 2 instead.

With m = 2 the search fails. Vertex 0 gets 1, vertex 1 gets 2, and vertex 2 conflicts with both, a dead end. Vertex 1 has no third color to try, so the search backs up to vertex 0 and gives it 2; then vertex 1 gets 1 and vertex 2 is stuck again. Vertex 1's only other color, 2, conflicts with vertex 0, and vertex 0 has no color left, so the answer is "not 2-colorable" (after 10 tries and 5 dead ends). Of course: the triangle 0, 1, 2 needs 3 colors.

Why backtracking is correct. It only ever gives a vertex a color that none of its colored neighbors has, and every edge is checked when its later endpoint is colored, so a coloring it returns is proper. In the other direction, it gives up on a partial coloring only when it contains a conflict, and a partial coloring with a conflict can never be completed into a proper one. Every other assignment of colors 1 to m is explored, so if a proper m-coloring exists the search reaches it (or another one first). Hence it answers "yes" exactly when the graph is m-colorable.

How this page keeps the search short. Two standard improvements, both still exact:

• Order: start at a vertex of largest degree, then always take the vertex with the most neighbors already in the order (ties: larger degree, then smaller number). Each new vertex is then constrained by many colored neighbors, so a bad choice leads to a conflict right away instead of many levels later.
• Symmetry: colors are interchangeable. If colors 1 to j are in use, the next vertex tries colors 1 to j + 1 only, because a coloring that uses j + 2 first is the same as one that uses j + 1 with two colors renamed. (So the first vertex only tries color 1.) Any proper coloring can be renamed so that colors are first used in the order 1, 2, 3, …, so no solution is lost.

Even so, a too-small m on the large graph can take hundreds of tries, so the animation stops after 250 tries and reports what a full search (not animated) found.

Running time

• Greedy: with adjacency lists, vertex v looks at its deg(v) neighbors, and the smallest free color is at most deg(v) + 1, so a boolean array of that size finds it in O(deg(v) + 1) time. Summing over all vertices, and since the degrees add up to 2m for m edges, greedy takes O(n + m) time. With an adjacency matrix, as drawn on this page, each vertex scans a whole row, so it takes O(n²).
• Welsh-Powell: sorting by degree takes O(n log n) (or O(n) with counting sort, since degrees are below n), then greedy takes O(n + m), so O(n log n + m) in all. The one-color-at-a-time version walks the list once per color, so it takes O(k(n + m)) for k colors.
• Backtracking: the search tree has one level per vertex and up to m branches per node, so it can have about mⁿ leaves, and each try checks up to deg(v) neighbors. The worst case is O(mⁿ · n): exponential. The pruning and the tricks above usually cut this down enormously, but no ordering avoids exponential time on every graph.

Why no fast exact method is known. Two colors are easy: color any vertex 1, its neighbors 2, their neighbors 1, and so on with a breadth-first search; this fails (some edge ends up with the same color at both ends) exactly when the graph has an odd cycle. It takes O(n + m) time. But for every fixed m ≥ 3, m-coloring is NP-complete. It is in NP, because a proposed coloring can be checked edge by edge in O(n + m) time. It is NP-hard for m = 3 by a reduction from 3-SAT (Karp, 1972; Garey, Johnson and Stockmeyer, 1976): a triangle of "True", "False" and "Base" vertices fixes three colors, each variable becomes two joined vertices x and ¬x that are both joined to Base (so one is colored True and the other False), and each clause becomes a small gadget that can be 3-colored only if at least one of its literals is True. For m > 3, add m − 3 new vertices joined to each other and to every original vertex: the new graph is m-colorable exactly when the original is 3-colorable. So a polynomial-time algorithm for any m ≥ 3 would give one for 3-SAT, and so for every problem in NP. Computing χ is therefore NP-hard, and it is even NP-hard to approximate χ within any constant factor.

Common mistakes and edge cases

• Counting uncolored neighbors. Greedy looks only at the neighbors of v that already have a color. Avoiding the colors of all colored vertices instead gives every vertex a new color, and forgetting that an uncolored neighbor does not block anything leads to the same waste.
• Forgetting to undo. In backtracking, a vertex's color must be removed when the search backs up past it; a stale color would block its neighbors from colors that are actually free and could make the search wrongly answer "no".
• Trusting the count. The number of colors greedy or Welsh-Powell uses is only an upper bound on χ. Δ + 1 is also just an upper bound: by Brooks' theorem a connected graph needs at most Δ colors unless it is a complete graph or an odd cycle.
• "No triangle, so 3 colors are enough" is false: there are triangle-free graphs that need any number of colors (Mycielski's construction), and a large clique is only a lower bound.
• Isolated vertices have no neighbors, so they always get color 1. A graph with no edges at all has χ = 1.
• Complete graphs K_n need n colors, and every order gives exactly n: here the Δ + 1 = n bound is reached.
• Bipartite graphs are exactly the 2-colorable graphs (for example trees, grids and even cycles). Check them with BFS in linear time, not with greedy: greedy may use 3 or more colors on a bipartite graph, as the 6-cycle above shows.
• Disconnected graphs can be colored one component at a time; χ is the largest χ of a component. A self-loop (an edge from a vertex to itself) makes a proper coloring impossible.

Variants

• DSatur (Brélaz, 1979) chooses the order as it goes: the next vertex is the uncolored one whose neighbors already use the most different colors (its saturation), with ties broken by degree. It usually beats Welsh-Powell, colors bipartite graphs with 2 colors, and is also a good vertex order for exact backtracking.
• Smallest-last order (Matula and Beck): repeatedly remove a vertex of smallest degree, then color in reverse removal order. Greedy then needs at most the graph's degeneracy + 1 colors, for example at most 6 on any planar graph.
• Edge coloring colors the edges instead, so that edges sharing an endpoint differ (e.g. scheduling matches so no team plays twice in a round). By Vizing's theorem a simple graph needs either Δ or Δ + 1 edge colors. It is the same as vertex coloring of the line graph, whose vertices are the original edges.
• Other variants include list coloring (each vertex has its own list of allowed colors) and weighted coloring, where some conflicts are allowed at a cost.

In the animation

The table lists each vertex's degree and color, and the Colors column beside it is the palette, with the vertex order below it. For the greedy methods, the edges from the current vertex to its colored neighbors are highlighted and each color is marked "used by" those neighbors or "free". For backtracking, the tried color is painted on the vertex; a conflicting edge turns red, and the counters show the tries and backtracks so far. When the search ends, the narration compares the result with the graph's chromatic number, computed by a full (not animated) search.

New Graph draws a fresh random graph each time, and draws again until it is connected. On the Small and Large graphs only vertices that sit near each other can be joined, so no two edges cross. Such a graph is planar, so it never needs more than 4 colors, and most need 3. The Random Graph puts 18 vertices on a circle and joins any two of them with probability 0.3, leaving out pairs two places apart (that edge would run through the vertex between them). Edges cross there, and graphs needing 4 or (rarely) 5 colors come up, so greedy goes wrong more often.

References

Graph coloring

Greedy coloring