Proper-color condition
color(u) ≠ color(v)
for every edge {u,v}.
Graph Coloring Calculator — Find Chromatic Number and Coloring
Enter an undirected graph
Separate labels with commas, semicolons, or lines. List isolated vertices here.
Private by design: parsing, search, coloring, and export happen on this device. Input is not uploaded, stored, or placed in the page URL.
Calculate a graph to display its coloring.
| Vertex | Color class | Degree |
|---|---|---|
| No calculation yet. | ||
Advertisement
What graph coloring and chromatic number mean
A proper vertex coloring assigns a color to every vertex so that adjacent vertices have different colors. The chromatic number, written χ(G), is the smallest number of colors for which a proper coloring exists.
Lower bound
ω(G) ≤ χ(G)
Every vertex in a clique needs a different color.
Upper bound
χ(G) ≤ colors in any valid coloring
A valid coloring proves that no more than that many colors are needed.
The calculator first creates a valid coloring to establish an upper bound and finds a clique to establish a lower bound. Its exact search then tries to improve the coloring. When the bounds meet—or every smaller possibility has been ruled out—the displayed value is proved to be χ(G).
Common graph coloring examples
No edges
A nonempty graph with no edges has chromatic number 1 because every vertex may share the same color.
Paths and even cycles
A path with at least one edge and every even cycle have chromatic number 2: alternate between two colors.
Odd cycles
An odd cycle such as the sample C₅ cannot be 2-colored, but it can be 3-colored, so χ(C₅) = 3.
Complete graphs
Every pair in Kₙ is adjacent, so every vertex needs its own color and χ(Kₙ) = n.
Input rules, exact method, and limits
Enter one edge per line as left,right. Whitespace around labels is ignored, labels are case-sensitive, and endpoints are automatically added as vertices. List isolated vertices separately. Repeated edges—including reversed duplicates—are merged. Self-loops are rejected because no proper coloring of a looped vertex exists.
The search uses degree-of-saturation ordering (DSATUR): it next colors the uncolored vertex adjacent to the largest number of different colors, breaking ties by degree. A greedy DSATUR coloring supplies the first upper bound, a valid clique supplies a lower bound, and branch-and-bound search proves whether fewer colors are possible. The saturation strategy is based on Daniel Brélaz’s original 1979 algorithm in Communications of the ACM.
Finding a chromatic number is computationally hard in general. To keep the page responsive, the calculator accepts up to 60 vertices and 2,000 unique edges and searches for up to 6 seconds in a background worker. If time expires, it reports a rigorous range such as 3 ≤ χ(G) ≤ 4 plus a valid coloring using the upper-bound number of colors. It never labels that range as an exact chromatic number.
Definitions and the clique lower bound follow OpenStax, Contemporary Mathematics, Section 12.4. The source also notes that a greedy coloring is not by itself proof of a minimum; this calculator adds exact branch-and-bound verification.
Calculation note: empty-edge, path, even-cycle, odd-cycle, complete-graph, disconnected, duplicate-edge, self-loop, invalid-input, and bounded-search cases checked by the Starlight Tools editorial team. Last reviewed: .
Graph coloring calculator FAQ
What is the chromatic number of a graph?
It is the fewest colors needed to color all vertices so that the two endpoints of every edge have different colors.
Does the calculator always find an exact answer?
It reports an exact chromatic number when the search finishes within 6 seconds. If a difficult instance reaches the limit, it reports a proven lower-to-upper range and a valid coloring, clearly marked “not yet proved exact.”
How do I enter isolated vertices?
List them in the Vertices field. Edge endpoints are added automatically, but vertices with no incident edges cannot be inferred from the edge list.
Can I enter directed or weighted edges?
This calculator colors simple undirected graphs. Direction and edge weight do not change the endpoint conflict in standard vertex coloring, so enter each adjacent pair once as A,B.
Why are self-loops rejected?
A self-loop would require a vertex’s color to differ from itself, so no proper vertex coloring exists. Parallel and reversed duplicate edges are harmless and are merged.
Can the minimum coloring be different from the one shown?
Yes. A graph may have many minimum colorings, and renaming the colors always gives an equivalent coloring. The tool displays one valid solution.
Does the calculator save my graph?
No. Input parsing, the background coloring search, visualization, copying, and CSV creation all happen locally in your browser.