Graph Coloring Calculator

What Is Graph Coloring?

Graph coloring is one of the most studied problems in combinatorics and theoretical computer science. In its most common form — vertex coloring — the goal is to assign a "color" (a label from a finite set) to each vertex of a graph such that no two adjacent vertices (vertices connected by an edge) share the same color. A coloring satisfying this constraint is called a proper coloring.

Graph coloring has a rich history dating back to the famous map coloring problem: how many colors are needed to color a map so no two neighboring regions share a color? This question drove a century of mathematical research culminating in the celebrated Four Color Theorem.

Chromatic Number

The chromatic number χ(G) of a graph G is the minimum number of colors required for a proper vertex coloring. It is one of the most fundamental parameters in graph theory:

• A graph with no edges has χ = 1 (one color suffices)
• Any graph with at least one edge has χ ≥ 2
• Bipartite graphs (no odd cycles) have χ = 2
• Odd cycles C_2k+1 have χ = 3
• Complete graphs K_n have χ = n
• Trees and forests have χ = 2 (or 1 if empty)

Computing the exact chromatic number is NP-hard, but polynomial-time greedy algorithms give efficient upper bounds that are often tight in practice.

Welsh-Powell Algorithm

The Welsh-Powell algorithm (1967) is a greedy vertex coloring heuristic that improves on purely random greedy coloring by using a clever vertex ordering:

• Step 1: Sort all vertices in descending order by degree (number of neighbors)
• Step 2: For each vertex in sorted order, assign the lowest-numbered color not already used by any of its neighbors
• Step 3: The number of distinct colors used is the upper bound on χ(G)

The intuition is that high-degree vertices are hardest to color (they have many neighbors with potentially many different colors), so coloring them early gives more flexibility. Welsh-Powell runs in O((V + E) log V) time (dominated by sorting) and often achieves the chromatic number for many practical graphs.

Brooks' Theorem

A key theoretical result is Brooks' Theorem (1941): for any connected undirected graph G that is neither a complete graph nor an odd cycle, the chromatic number satisfies χ(G) ≤ Δ(G), where Δ is the maximum degree. For complete graphs K_n, χ = n = Δ + 1, and for odd cycles, χ = 3 = Δ + 1. Brooks' theorem thus gives a tight upper bound for almost all graphs.

Lower Bounds: Clique Number

The clique number ω(G) — the size of the largest complete subgraph — provides a lower bound on the chromatic number: ω(G) ≤ χ(G). This is because all vertices in a clique are mutually adjacent and thus require distinct colors. For perfect graphs (a class including bipartite graphs, chordal graphs, and interval graphs), χ(G) = ω(G) exactly.

The Four Color Theorem

The Four Color Theorem (Appel & Haken, 1976) states that every planar graph is 4-colorable — that is, χ(G) ≤ 4 for any graph that can be drawn in the plane without edge crossings. This was the first major theorem proved with significant computer assistance, verifying hundreds of reducible configurations. The result is tight: there exist planar graphs (like K₄) requiring exactly 4 colors.

Applications of Graph Coloring

• Register Allocation: In compilers, program variables that are simultaneously live (in-use) at some point conflict and must occupy different CPU registers. The register allocation problem is equivalent to coloring a conflict graph where an edge connects two variables that cannot share a register.
• Scheduling: Tasks that compete for a shared resource (a machine, a room, a time slot) conflict. Coloring assigns non-conflicting groups to the same time slot; χ colors = minimum number of time slots (or resources) needed.
• Map Coloring: Regions sharing a border must receive different colors. The dual graph (one vertex per region, edges for shared borders) must be colored; the Four Color Theorem guarantees 4 colors suffice for any planar map.
• Sudoku Solving: Each cell is a vertex; cells in the same row, column, or 3×3 box are connected. A valid Sudoku solution is a proper 9-coloring of this graph using digits 1–9.
• Wireless Frequency Assignment: Adjacent cell towers that might interfere must use different frequencies. Minimizing frequencies used is equivalent to chromatic number minimization.
• Exam Timetabling: Exams with students in common cannot be scheduled simultaneously. The conflict graph must be properly colored, with each color representing a time slot.

Bipartite Graphs and 2-Colorability

A graph is bipartite if its vertices can be split into two disjoint sets U and V such that every edge connects a vertex in U to one in V. Equivalently, a graph is bipartite if and only if it contains no odd-length cycles. Bipartite graphs have χ = 2 (or χ = 1 if there are no edges) and can be recognized in linear time using BFS.