Graph Coloring and Chromatic Number

Graph coloring is the backbone of register allocation in compilers: variables that are simultaneously live are joined by an edge in an interference graph, and assigning them to a fixed number of CPU registers without conflict is exactly a proper coloring problem, where $\chi(G)$ tells you the minimum register count needed. In scheduling and timetabling, exams, jobs, or radio frequencies that cannot coexist (share a room, a time slot, or overlapping spectrum) are modeled as conflict graphs, and a proper $k$-coloring gives a valid assignment to $k$ resources — this underlies frequency assignment in cellular networks and university exam scheduling systems. In complexity theory, deciding whether $\chi(G) \le k$ for general $k \ge 3$ is one of Karp's original NP-complete problems, making chromatic number a central benchmark for hardness and for approximation algorithms; even for $k = 3$ the problem is NP-complete, while $k=2$ is solvable in polynomial time precisely because of the Bipartite Characterization Theorem proved above. In statistics and probability, random graph colorings and the threshold behavior of $\chi(G_{n,p})$ for Erdős–Rényi random graphs are a major topic in probabilistic combinatorics. In algebra and topology, the chromatic polynomial and its connections to the two-coloring problem extend to Tutte polynomials and knot invariants, and the coloring of graphs embedded on surfaces connects directly to Planar Graphs and Euler's Formula and ultimately to the Four Color Theorem itself.

Ask the tutor: How do the clique-number and degree bounds on $\chi(G)$ get sharpened further, and what makes planar graphs special enough to always be $4$-colorable?

Think of coloring as a conflict-resolution process. Each edge is a "these two must differ" constraint, and a proper coloring is a labeling that satisfies every constraint simultaneously. The chromatic number is not about how many colors you are allowed to use — you may always use extra colors you never need — it is about the minimum palette that makes the constraints satisfiable. A useful equivalent formulation: a proper $k$-coloring of $G$ is exactly a partition of $V$ into $k$ (possibly empty) independent sets, the color classes, since $c^{-1}(i)$ must be a set of pairwise non-adjacent vertices for every color $i$. So $\chi(G)$ is the minimum number of independent sets needed to cover all of $V$. This reframes coloring as a covering/partitioning problem, which is the bridge to bounds involving clique number and independence number developed further in Bounds on the Chromatic Number. Two forces push $\chi(G)$ in opposite directions. A clique of size $r$ (every pair of its vertices adjacent, as discussed under Subgraphs and Special Graph Families) forces all $r$ vertices to receive distinct colors, since every pair conflicts — this drives $\chi(G)$ up. On the other hand, if the graph has enough symmetry or sparsity — most simply, if it is bipartite — two colors already suffice, driving $\chi(G)$ down. The first figure below shows a 5-cycle, which contains no triangle (clique number $2$) yet still needs $3$ colors, because an odd cycle can never be properly $2$-colored. The second figure shows the greedy coloring process on a small graph, illustrating why vertex order affects how many colors greedy actually uses, even though the true chromatic number is fixed.

Example 1: The Petersen-like wheel graph $W_5$. Let $W_5$ be the wheel graph formed by a $5$-cycle $v_1v_2v_3v_4v_5v_1$ (the rim) plus a hub vertex $h$ adjacent to all five rim vertices. This graph has $6$ vertices and $10$ edges ($5$ rim edges, $5$ spokes). Lower bound. The hub $h$ together with any two adjacent rim vertices, say $v_1, v_2$, forms a triangle $h, v_1, v_2$ (since $h$ is adjacent to both, and $v_1v_2$ is a rim edge). So $\omega(W_5) \ge 3$. Also $W_5$ contains the $5$-cycle on the rim, an odd cycle, so by the Bipartite Characterization Theorem, $\chi(W_5) \ge 3$ is confirmed independently; we push further using the hub. Suppose toward contradiction that $\chi(W_5) = 3$ using colors $\{1,2,3\}$. Since $h$ is adjacent to every rim vertex, no rim vertex may share $h$'s color; so all five rim vertices are colored using only the remaining two colors. But the rim is the odd cycle $C_5$, and by the Bipartite Characterization Theorem $C_5$ itself requires $3$ colors — it cannot be properly $2$-colored. This contradicts using only $2$ colors on the rim. Hence $\chi(W_5) \ge 4$. Upper bound. Color the rim vertices $v_1,\dots,v_5$ using colors $1,2,1,2,3$ in cyclic order (checking: $v_1v_2 = 1,2$ differ; $v_2v_3=2,1$ differ; $v_3v_4=1,2$ differ; $v_4v_5=2,3$ differ; $v_5v_1=3,1$ differ — all rim edges are properly colored). Color the hub $h$ with color $4$, distinct from all rim colors $\{1,2,3\}$, so every spoke $hv_i$ is properly colored. This uses $4$ colors and is proper on all $10$ edges, so $\chi(W_5) \le 4$. Combining, $\chi(W_5) = 4$. Note $\Delta(W_5) = 5$ (the hub's degree), so the greedy bound only guarantees $\chi(W_5) \le 6$; the true value $4$ shows the greedy bound can be far from tight, while the direct clique/odd-cycle argument pins the exact value.

Example 2: A bipartite-looking graph that is not bipartite. Consider the graph $H$ on vertex set $\{a,b,c,d,e\}$ with edges

This is the $5$-cycle $a$–$b$–$c$–$d$–$e$–$a$ with one extra chord $ac$ added. It has $5$ vertices and $6$ edges. Checking for odd cycles. The outer boundary $a,b,c,d,e,a$ is a $5$-cycle (odd length $5$). By the Bipartite Characterization Theorem, the presence of this odd cycle already forces $\chi(H) \ge 3$; equivalently $H$ cannot be bipartite despite superficially resembling one before the chord is noticed. Finding the clique number. The chord $ac$ together with edge $ab$ and $bc$ forms a triangle $a,b,c$ (since $ab, bc, ac$ are all edges). So $\omega(H) \ge 3$, giving an independent confirmation $\chi(H) \ge 3$ via the Corollary above. Is there a clique of size $4$? A $4$-clique would need $6$ edges among $4$ vertices, but $H$ has only $6$ edges total spread over $5$ vertices, and one can check directly no vertex of $H$ has degree $3$ except $a$ and $c$ (each has degree $3$: $a$ is adjacent to $b,e,c$; $c$ is adjacent to $b,d,a$), so no $4$ vertices are pairwise all mutually adjacent. Hence $\omega(H) = 3$. Constructing a proper $3$-coloring. Try $c(a) = 1$, $c(b) = 2$, $c(c) = 3$ (forced pairwise distinct by the triangle), then $c(d)$ must differ from $c(c)=3$ (edge $cd$), so let $c(d) = 1$; and $c(e)$ must differ from $c(d) = 1$ (edge $de$) and from $c(a) = 1$ (edge $ea$) — both constraints agree, so let $c(e) = 2$. Check all $6$ edges: $ab: 1,2$; $bc: 2,3$; $cd: 3,1$; $de: 1,2$; $ea: 2,1$; $ac: 1,3$ — every edge has distinct endpoint colors. This is a valid proper $3$-coloring. Combining the lower bound $\chi(H)\ge 3$ (from either the odd cycle or the triangle) with this explicit $3$-coloring, we conclude $\chi(H) = 3$.

It is a classical fact (due to Mycielski's construction, foreshadowing deeper bounds in Bounds on the Chromatic Number) that there exist triangle-free graphs with $\chi(G)$ as large as desired — so the gap between $\omega(G)$ and $\chi(G)$ in the Corollary above can be made arbitrarily wide, not merely nonzero.