The chromatic number of a graph, written χ(G), is the smallest number of colors you need to color every vertex so that no two connected vertices share the same color. Finding it exactly is computationally hard for general graphs (it’s NP-hard), so in practice you’ll use a combination of bounds, algorithms, and shortcuts for special graph types. Here’s how to approach it systematically.
Start With What You Can Rule Out
Before running any algorithm, check whether your graph belongs to a family with a known chromatic number. These cases give you an instant answer:
- Complete graphs (K_n): Every vertex connects to every other vertex, so each one needs its own color. χ(K_n) = n.
- Bipartite graphs: Any graph whose vertices split into two groups with edges only between groups (no odd cycles) has χ = 2. Trees, even-length cycles, and grids all fall here. A graph with no edges at all has χ = 1.
- Odd cycles: A cycle with an odd number of vertices always needs exactly 3 colors, while an even cycle needs only 2.
- Planar graphs: Any graph you can draw on a flat surface without crossing edges needs at most 4 colors. This is the Four Color Theorem, proved by Appel and Haken in 1976 with the aid of a computer. Many planar graphs need fewer than 4, but you’ll never need a fifth.
Recognizing these patterns can save you all the work that follows. If your graph doesn’t fit a known family, move on to bounding the answer from above and below.
Establish a Lower Bound
A lower bound tells you the minimum number of colors you’ll definitely need. The most intuitive lower bound comes from finding a clique, which is a subset of vertices that are all connected to each other. Since every vertex in a clique must get a different color, the size of the largest clique (called the clique number, ω(G)) is always less than or equal to χ(G).
Look through your graph for triangles (cliques of size 3), then groups of 4 mutually connected vertices, and so on. If you find a clique of size 4, you know immediately that χ(G) ≥ 4. For small graphs you can do this by inspection. For larger ones, finding the maximum clique is itself a hard problem, but even spotting a modest-sized clique gives you a useful floor.
Another quick lower bound: if your graph has n vertices and m edges, the formula n / (n − 2m/n) gives a lower bound on the clique number, which in turn bounds the chromatic number from below. This is handy when the graph is too large to search for cliques by hand.
Establish an Upper Bound
An upper bound tells you the most colors you could possibly need. The simplest one: a greedy coloring algorithm will never use more than Δ(G) + 1 colors, where Δ(G) is the highest degree (number of connections) of any vertex in the graph. If your busiest vertex has 5 neighbors, greedy coloring uses at most 6 colors.
Brooks’ Theorem tightens this. It says that unless your graph is a complete graph or an odd cycle, the chromatic number is at most Δ(G), not Δ(G) + 1. So for most real graphs, the maximum degree itself is the upper bound.
If your lower and upper bounds meet, you’ve found the exact chromatic number. If they don’t, you need to narrow the gap using a coloring algorithm.
The Greedy Algorithm
Greedy coloring is the most straightforward approach. You process vertices one at a time in some chosen order, and for each vertex, you assign the smallest color number not already used by any of its already-colored neighbors. If all its neighbors’ colors are taken, you introduce a new color.
The catch is that the vertex ordering matters enormously. A bad ordering can use far more colors than necessary. In pathological cases, greedy coloring on a graph that only needs 2 colors can end up using n/2 colors if the vertices are processed in an unlucky sequence. So the algorithm is fast, but it doesn’t guarantee the optimal answer on its own. It gives you a valid coloring that serves as an upper bound, which you then try to improve.
The Welsh-Powell Algorithm
Welsh-Powell improves on plain greedy coloring by being smarter about vertex order. The steps:
First, sort all vertices by degree from highest to lowest. Vertices with the most connections get colored first, since they’re the most constrained. Then take your first color and walk through the sorted list. Assign this color to any vertex that hasn’t been colored yet and isn’t adjacent to a vertex already using that color. Once you’ve gone through the whole list, move to the next color and repeat. Continue until every vertex has a color.
By handling high-degree vertices early, Welsh-Powell tends to use fewer colors than a random greedy ordering. It’s a solid choice for hand-solving medium-sized graphs, like the ones you’d encounter in a textbook or homework problem.
The DSATUR Algorithm
DSATUR (short for “degree of saturation”) is generally the best heuristic for getting close to the true chromatic number without exhaustive search. Instead of fixing the vertex order in advance, it picks the next vertex dynamically based on how constrained it is at that moment.
The saturation degree of a vertex is the number of distinct colors already used by its neighbors. At each step, DSATUR colors the uncolored vertex with the highest saturation degree, breaking ties by choosing the vertex with the highest overall degree. This focuses attention on the most restricted parts of the graph first, which tends to produce tighter colorings.
The number of colors DSATUR uses is a valid upper bound for χ(G). For many graph types, it finds the optimal or near-optimal coloring. It can also be extended into a branch-and-bound framework that guarantees the exact chromatic number, though that takes exponential time in the worst case.
Putting It All Together by Hand
For a graph you’re solving on paper, here’s a practical workflow. First, check for special structure: is it bipartite? Planar? A cycle? Complete? If so, apply the known result. Second, find the largest clique you can spot to set your lower bound. Third, note the maximum degree and apply Brooks’ Theorem for an upper bound. Fourth, attempt a coloring using Welsh-Powell or DSATUR. If the number of colors you used matches your lower bound, that’s your chromatic number.
If there’s still a gap, say your clique gives a lower bound of 3 but your best coloring uses 4, you need to either find a larger clique or prove that no 3-coloring exists. For small graphs, you can try to construct a 3-coloring manually. Pick any vertex, assign it color 1, and propagate the constraints to its neighbors. If you reach a contradiction where some vertex has neighbors using all 3 colors, then χ(G) > 3, confirming the answer is 4.
Using Software for Larger Graphs
For graphs too large to color by hand, Python’s NetworkX library has a built-in greedy coloring function. The basic call looks like this:
d = nx.coloring.greedy_color(G, strategy=”DSATUR”)
This returns a dictionary mapping each vertex to a color number. The number of distinct values in that dictionary is your upper bound. NetworkX supports several ordering strategies, including “largest_first” (similar to Welsh-Powell), “smallest_last”, “random_sequential”, and “DSATUR”. You can try multiple strategies and take the best result.
Keep in mind that greedy_color gives you a heuristic upper bound, not necessarily the exact chromatic number. For exact computation on moderately sized graphs, you’d need specialized solvers that use branch-and-bound or integer programming. But for most practical purposes, running DSATUR and comparing the result against a clique-based lower bound will either pin down the answer or get you within one color of it.
Why Exact Solutions Are Hard
Finding the chromatic number of a general graph is NP-hard, meaning there’s no known algorithm that solves every instance quickly. Even determining whether a graph can be colored with just 3 colors is NP-complete. This is why heuristics and bounds are so central to the process. For graphs with special structure (bipartite, planar, interval graphs, chordal graphs), polynomial-time algorithms exist. But for an arbitrary graph with hundreds of vertices and no exploitable structure, you’re relying on a combination of smart heuristics and brute-force verification to close the gap between bounds.