Mathematics
Chromatic Number and Clique Number
Quick fact
There are graphs that contain no triangle (no clique of size 3) yet require over 1,000 colors to properly color! Such triangle-free graphs with arbitrarily large chromatic number were first constructed by Mycielski in 1955, showing the clique number alone cannot bound the coloring requirement.
Why this is interesting
You've probably seen puzzles about coloring maps so neighboring countries get different colors. But what if we color graphs instead? The minimum number of colors needed is called the chromatic number—and the biggest cluster of all-connected vertices, the clique number, seems to set a floor. Yet sometimes the floor is far from the truth.
Read the full explanation
Understanding Chromatic Number and Clique Number
Imagine a graph as a collection of circles (vertices) connected by lines (edges). A proper coloring assigns a color to each vertex so that any two vertices joined by an edge receive different colors. The chromatic number, χ(G), is the fewest colors needed for a particular graph. A clique is a group of vertices that are all mutually connected—a complete subgraph. For example, a triangle is a clique of size 3. Since every vertex in a clique must receive a distinct color (they all touch each other), the clique number ω(G)—the size of the largest clique—is an obvious lower bound: you need at least ω(G) colors. So χ(G) ≥ ω(G). For many familiar graphs, like complete graphs or cycles, equality holds. But the surprising truth is that this bound can be extremely weak: there are graphs where ω(G)=2 (no triangles) yet χ(G) is enormous. This gap reveals that chromatic number is governed by more than just large cliques.
A deeper explanation
When building a coloring greedily (assigning colors one by one), you never need more than Δ(G)+1 colors, where Δ is the maximum degree—every vertex sees at most Δ neighbors, so one free color always exists. Yet this trivial upper bound rarely equals the true χ(G). The lower bound from cliques is similarly weak: a graph can be triangle-free while still demanding an arbitrarily high number of colors. The reason is that coloring is a global constraint problem; the interactions among vertices spread across the whole graph create demands that local density (cliques) cannot capture. Graphs of both high and low chromatic number exist with the same clique number, so ω(G) alone gives no upper bound. In fact, for graphs where χ(G)=ω(G) for every induced subgraph, we call them perfect graphs; examples include bipartite graphs and interval graphs. But even for perfect graphs, the equality does not make finding χ easy. Determining the chromatic number of a general graph is NP-hard—no known algorithm runs in polynomial time. This fundamental gap between local density and global coloring is what makes the study of chromatic and clique numbers rich, both structurally and algorithmically.