Graph Coloring — Chromatic Number & Applications

Graph coloring usually means vertex coloring: assign a color to each vertex so that adjacent vertices do not share a color. The smallest number of colors that works is the chromatic number, written $\chi(G)$.

If you want the fast intuition, colors are just conflict-free labels. Two vertices can reuse the same color exactly when there is no edge between them.

Graph coloring definition in one minute

In a proper coloring, every edge connects two differently colored vertices. That is the whole rule.

So if $\chi(G)=3$, two facts are true at the same time:

• a proper coloring with $3$ colors exists
• no proper coloring with only $2$ colors exists

That is why the chromatic number is a minimum, not just the number of colors you happened to use in one drawing.

Unless someone says otherwise, graph coloring in an intro course means coloring the vertices of a simple undirected graph. Edge coloring is a different problem with different rules.

What the chromatic number is really measuring

The color names do not matter. You can use red, blue, and green, or labels $1$, $2$, and $3$.

What matters is the grouping. All vertices with the same color form a set with no edges inside it, so that group has no conflicts.

That viewpoint is what makes graph coloring useful in scheduling and allocation problems. One color often means "these items can share the same slot."

Worked example: why a 5-cycle needs 3 colors

Consider the cycle graph $C_5$ with edges $AB, BC, CD, DE,$ and $EA$.

Try $2$ colors first. Give $A$ color $1$ and $B$ color $2$. Then the coloring is forced around the cycle:

$$A=1,\quad B=2,\quad C=1,\quad D=2$$

Now look at $E$. It is adjacent to both $D$ and $A$, so it cannot use color $2$ because of $D$, and it cannot use color $1$ because of $A$.

So $2$ colors fail.

But $3$ colors do work. One proper coloring is

$$A=1,\quad B=2,\quad C=1,\quad D=2,\quad E=3$$

so

$$\chi(C_5)=3$$

This example is worth remembering because it shows an important pattern: for cycle graphs, an even cycle can be colored with $2$ colors, but an odd cycle needs $3$.

How to reason about graph coloring on small graphs

Two quick checks help.

First, look for a forced conflict. In the example above, alternating two colors around an odd cycle makes the last vertex clash with both available choices.

Second, look for a lower bound. If a graph contains a triangle, then those three vertices are pairwise adjacent, so they already need $3$ different colors. That does not always give the exact answer, but it proves the chromatic number is at least $3$.

Common mistakes in graph coloring problems

One common mistake is treating vertices as adjacent just because they are drawn close together. Only an actual edge creates a coloring restriction.

Another mistake is assuming every vertex needs its own color. Nonadjacent vertices can reuse a color, and efficient colorings usually reuse colors as much as possible.

Students also sometimes mix up vertex coloring and edge coloring. In this page, the rule is about adjacent vertices, not adjacent edges.

A final mistake is reporting the number of colors you happened to use instead of the minimum number required. Using $4$ colors on a graph does not prove the chromatic number is $4$.

Where graph coloring is used

A standard application is scheduling. Suppose each vertex is an exam, and an edge means two exams share students and cannot be placed at the same time. Then one color can represent one time slot.

In that model, the chromatic number tells you the fewest time slots possible. If $\chi(G)=4$, then no valid schedule with only $3$ slots exists.

The same idea appears in map coloring, where neighboring regions must differ, and in compiler design, where variables that are simultaneously needed cannot share the same register.

Try a similar graph coloring problem

Draw a graph with vertices $P,Q,R,S,T$ and edges $PQ, QR, RS, ST, TP,$ and $PR$.

Start by finding a triangle to get a lower bound. Then try to color the graph with as few colors as possible and check whether any adjacent vertices match. If you want a next step, try your own version on a larger graph and see whether you can prove your coloring is minimal, not just valid.