Graph Coloring Calculator

Find the chromatic number and a valid vertex coloring for any undirected graph. Enter edges or an adjacency list, and get the minimum number of colors, a color assignment, animated DSATUR step-by-step solution, and an interactive SVG graph visualization.

⚡ Try an example:

4-cycle C₄ Triangle K₃ Complete K₅ Pentagon C₅ Wheel W₆ Bipartite K₃,₃ Adjacency sample Exam scheduling

Input format

⬌ Edge list

⧇ Adjacency list

Graph data

Edge format: A-B or A B, separated by commas or newlines. Max 60 vertices and 600 edges.

Adjacency format: A: B, C, D — one vertex per line, followed by its neighbors.

Algorithm

Auto picks exact backtracking for small graphs and DSATUR for larger ones.

Embed Graph Coloring Calculator Widget

About Graph Coloring Calculator

The Graph Coloring Calculator computes the chromatic number χ(G) and a valid vertex coloring for any undirected graph. Enter your graph as an edge list or adjacency list and the tool returns the minimum number of colors needed so that no two adjacent vertices share a color, together with an interactive SVG visualization, an animated DSATUR trace, and a color-by-color breakdown of which vertices receive which color.

What is graph coloring?

A proper vertex coloring of a graph G = (V, E) assigns a color to each vertex so that every edge has endpoints of different colors. The chromatic number, written χ(G), is the smallest number of colors for which such a coloring exists. Computing χ(G) is NP-hard in general, but the problem has a beautiful mathematical theory and many practical applications: exam scheduling, radio frequency assignment, register allocation in compilers, and the famous four color theorem for planar maps.

Chromatic number definition

χ(G) = min { k : G admits a proper k-coloring }

Key theorems and bounds

Trivial bounds: 1 ≤ χ(G) ≤ |V| for any graph.
Clique lower bound: χ(G) ≥ ω(G), where ω(G) is the size of the largest clique.
Bipartite characterization: χ(G) ≤ 2 if and only if G has no odd cycle (König).
Brooks' theorem: χ(G) ≤ Δ(G), unless G is a complete graph or an odd cycle, in which case χ(G) = Δ(G) + 1. Here Δ(G) is the maximum degree.
Four color theorem: Every planar graph is 4-colorable.
Greedy upper bound: Any greedy algorithm uses at most Δ(G) + 1 colors.

Algorithms used by this calculator

DSATUR (Degree of Saturation)

Introduced by Daniel Brélaz in 1979, DSATUR is one of the strongest practical heuristics for graph coloring. It repeatedly picks the uncolored vertex whose neighbors already use the most distinct colors (its saturation), breaking ties by vertex degree, and assigns it the smallest color not used by its neighbors. DSATUR is provably optimal on bipartite graphs and on many structured graph families, and produces high-quality colorings in milliseconds on graphs with hundreds of vertices.

Welsh-Powell

The Welsh-Powell algorithm sorts vertices in decreasing order of degree and then colors them greedily. It runs in O(|V|²) time and guarantees at most Δ(G) + 1 colors. It is extremely fast and often a good first approximation, although it can be beaten by DSATUR on graphs with varying local structure.

Greedy (input order)

The simplest algorithm: walk through vertices in input order and give each one the smallest color not used by an already-colored neighbor. The output is sensitive to the input ordering, but a random ordering gives a baseline you can compare the smarter heuristics against.

Exact backtracking

For small graphs (up to about 18 vertices) the calculator can find the true chromatic number by trying k = 2, 3, 4, ... and attempting to k-color the graph with depth-first backtracking. The search orders vertices by decreasing degree and prunes when no color is available. When the exact algorithm succeeds, the result is labeled "Exact".

Input formats

Edge list

Write each edge as two vertex labels separated by a hyphen, space, or arrow. Separate edges with commas or newlines. Vertex labels can be letters, digits, or underscores. Example:

A-B, B-C, C-D, D-A
A-C

Adjacency list

Write each vertex, a colon, and the comma-separated list of its neighbors. Example:

A: B, C, D
B: A, D
C: A
D: A, B

Self-loops are rejected because a vertex cannot be given a color different from itself. Duplicate edges are silently deduplicated, and the graph is treated as undirected.

How to use this calculator

Pick a format: Toggle between edge list and adjacency list with the radio buttons.
Enter the graph: Paste your data or click one of the quick examples (triangle, complete K₅, Petersen-like wheel, bipartite K₃,₃, exam scheduling).
Choose an algorithm: Leave Auto for the best default, or force Welsh-Powell, greedy, DSATUR, or exact backtracking.
Click "Color the Graph": The chromatic number, a color-by-color list, an interactive SVG with draggable nodes, and an animated step-by-step trace appear below.
Explore: Press Play to watch the algorithm color vertices one at a time, drag nodes to rearrange the layout, and use Back / Next to step through the trace manually.

Practical applications of graph coloring

Exam scheduling

Let each exam be a vertex and draw an edge between exams that share at least one student. A proper coloring with k colors gives a schedule with k time slots such that no student has a conflict. The chromatic number is the minimum number of slots.

Radio frequency assignment

Transmitters within interference range of each other must broadcast on different frequencies. The chromatic number of the interference graph is the minimum number of frequencies needed.

Register allocation

In compilers, live ranges of variables are vertices; two live ranges overlap in time means there is an edge between them. A k-coloring assigns variables to k CPU registers without collisions.

Map coloring

Countries that share a border must receive different colors. The four color theorem (Appel-Haken, 1976) proves that four colors always suffice for any planar map.

Sudoku and constraint puzzles

A completed Sudoku is a 9-coloring of a graph whose vertices are the 81 cells and whose edges connect cells in the same row, column, or 3×3 box. Graph coloring is the mathematical core of many constraint satisfaction puzzles.

Interesting special cases

Complete graph K_n: χ(K_n) = n. Every pair of vertices is adjacent, so all colors must be distinct.
Cycle C_n: χ(C_n) = 2 if n is even, 3 if n is odd.
Tree: Any tree with ≥ 2 vertices has χ = 2 (trees are bipartite).
Bipartite graph: χ = 2 if the graph has at least one edge.
Petersen graph: A famous 3-regular graph with χ = 3.
Wheel W_n: A hub vertex joined to an n-cycle. χ = 3 if n is even, 4 if n is odd.

Frequently asked questions

What is the chromatic number of a graph?

The chromatic number χ(G) is the smallest number of colors needed to color the vertices of a graph so that no two adjacent vertices share a color. Bipartite graphs have chromatic number at most 2; any graph containing a triangle has chromatic number at least 3; and by Brooks' theorem the chromatic number never exceeds the maximum degree, except for complete graphs and odd cycles.

What algorithm does this calculator use?

For small graphs the calculator runs an exact backtracking search to find the true chromatic number. For larger graphs it uses the DSATUR heuristic, which repeatedly colors the uncolored vertex with the most already-colored neighbors. You can also force Welsh-Powell or plain greedy from the Algorithm dropdown.

How should I input my graph?

Use the edge list mode to type one edge per line such as A-B, or comma-separated like A-B, B-C, C-A. Use the adjacency list mode to write each vertex followed by a colon and its neighbors, such as A: B, C. Self-loops are rejected because a vertex cannot be colored differently from itself.

Why does DSATUR not always find the true chromatic number?

Graph coloring is NP-hard, so no known fast algorithm always finds the minimum number of colors. DSATUR is an excellent practical heuristic and often matches the true chromatic number, but on adversarial graphs it can use more colors than necessary. The calculator reports both the colors used and a lower bound from the largest clique found, so you can judge how tight the answer is.

What is a real world use of graph coloring?

Graph coloring models exam scheduling (each exam is a vertex, conflicts are edges, colors are time slots), radio frequency assignment (vertices are transmitters, edges are interference), register allocation in compilers, map coloring, sudoku solving, and job-to-machine assignment under conflict constraints.

Is the chromatic number always equal to the largest clique?

No. The clique number ω(G) is always a lower bound for the chromatic number χ(G), and they are equal for perfect graphs such as bipartite graphs, trees, interval graphs, and chordal graphs. For general graphs χ(G) can be strictly larger than ω(G); the classic example is the Mycielski graphs, which are triangle-free but need arbitrarily many colors.

What is the biggest graph this calculator can handle?

The calculator supports up to 60 vertices and 600 edges. For the exact algorithm, graphs with more than about 18 vertices may fall back to DSATUR because backtracking becomes too slow. For practical use this covers most classroom examples, exam scheduling problems, and small-to-medium applications.

Graph Coloring Calculator

About Graph Coloring Calculator

What is graph coloring?

Key theorems and bounds

Algorithms used by this calculator

DSATUR (Degree of Saturation)

Welsh-Powell

Greedy (input order)

Exact backtracking

Input formats

Edge list

Adjacency list

How to use this calculator

Practical applications of graph coloring

Exam scheduling

Radio frequency assignment

Register allocation

Map coloring

Sudoku and constraint puzzles

Interesting special cases

Frequently asked questions

What is the chromatic number of a graph?

What algorithm does this calculator use?

How should I input my graph?

Why does DSATUR not always find the true chromatic number?

What is a real world use of graph coloring?

Is the chromatic number always equal to the largest clique?

What is the biggest graph this calculator can handle?

Further Reading

Advanced Math Operations:

Top & Updated: