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 quantity you actually compute is the chromatic number $\chi(G)$, the smallest number of colors that works.

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.

The Definition And What $\chi(G)$ Encodes

In a proper coloring, every edge connects two differently colored vertices. That is the whole rule. The symbol $\chi(G)$ packs two claims into one number. If $\chi(G)=3$, then:

• 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.

The color names themselves 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 the chromatic number useful in scheduling, where one color often means "these items can share the same slot."

Why The Chromatic Number Is What It Is

The value of $\chi(G)$ is pinned down from two directions, and understanding both is what makes the computation reliable instead of guesswork.

From above, you find a valid coloring: producing a proper coloring with $c$ colors proves $\chi(G) \le c$. From below, you find a forced conflict: if some set of vertices is pairwise adjacent, they all need different colors, which proves $\chi(G)$ is at least that many. When the upper and lower bounds meet, you have the exact chromatic number. This is why a single drawing never settles the question on its own. It only gives an upper bound until you also prove no smaller number can work.

Worked Example: Why $C_5$ 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:

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 (the lower bound rules out $2$).

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

so

The upper and lower bounds meet at $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$.

Practice And A Way To Check Yourself

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

How to check your answer: first look for a triangle to get a lower bound. The edges $PQ$, $QR$, and... note that $PR$ together with $PQ$ and $QR$ makes $P, Q, R$ pairwise adjacent, a triangle, so $\chi(G) \ge 3$. Then try a coloring with $3$ colors and confirm no adjacent vertices match. If a valid $3$-coloring exists, the lower bound and upper bound meet, so $\chi(G) = 3$. Using more colors than necessary, say $4$, would not prove the chromatic number is $4$.

Computation Traps To Avoid

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

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

A third trap is mixing up vertex coloring and edge coloring; the rule here is about adjacent vertices, not adjacent edges.

A final trap is reporting the number of colors you happened to use instead of the minimum required. Using $4$ colors on a graph does not prove the chromatic number is $4$ unless you also rule out $3$.

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, and 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. After the practice graph above, try a larger one and see whether you can prove your coloring is minimal, not just valid.