Graph Coloring Calculator

Enter Graph Data

Use simple vertex labels without spaces. Edge lines can look like A-B, A B, or A,B.

Graph Name

Auto Vertex Count

Auto Vertex Prefix

Solver Mode

Ordering Method

Auto Exact Limit

Vertex Labels

Edges

Precolored Vertices

Example Data Table

Example Graph	Vertices	Edges	Expected Coloring Insight
Cycle C5	A, B, C, D, E	A-B, B-C, C-D, D-E, E-A	Odd cycles need three colors.
Complete Graph K4	A, B, C, D	A-B, A-C, A-D, B-C, B-D, C-D	Every vertex needs a unique color.
Bipartite Ladder	U1, U2, U3, V1, V2, V3	U1-V1, U2-V2, U3-V3, U1-U2, U2-U3, V1-V2, V2-V3	Two colors are sufficient.

Formula Used

Proper coloring rule: For every edge (u, v), the calculator enforces c(u) ≠ c(v).

Chromatic number: χ(G) = min k such that the graph has a valid coloring with k colors.

Density: 2m / (n(n-1)), where n is the number of vertices and m is the number of edges.

Average degree: 2m / n.

Bounds: The page reports a lower bound using clique size and fixed colors, and an upper bound from greedy or DSATUR coloring.

Heuristic methods: Welsh-Powell and DSATUR quickly generate valid colorings, while exact mode uses branch-and-bound on small graphs.

How to Use This Calculator

Enter custom vertex labels, or generate them from a count and prefix.
Add one edge per line using two existing vertices.
Optionally lock selected vertices to fixed colors with entries like A=1.
Choose auto, exact, or greedy solving, then set the ordering rule.
Click Calculate Coloring to show the result above the form.
Review bounds, diagnostics, color classes, and the adjacency matrix.
Use the CSV and PDF buttons to export the current report.

FAQs

1. What does this calculator solve?

It assigns colors to vertices so adjacent vertices never share one. It also reports bounds, density, components, and exportable vertex results.

2. What is the chromatic number?

The chromatic number is the smallest number of colors needed for a proper coloring of the graph.

3. When should I use exact mode?

Use exact mode for smaller graphs when you need the proven minimum color count, not only a valid heuristic coloring.

4. Why can greedy mode use extra colors?

Greedy coloring depends on vertex order. A different order can change the result, so greedy output is an upper bound, not always optimal.

5. What do precolored vertices do?

They lock chosen vertices to fixed colors. This is useful for scheduling, map updates, seeded partitions, and constraint-based coloring experiments.

6. What graphs are invalid here?

Self-loops are invalid because a vertex adjacent to itself can never satisfy proper coloring rules.

7. Why does the page show lower and upper bounds?

Bounds help you judge solution quality. Matching bounds often signal that the reported color count is already optimal.

8. What does the Plotly graph show?

It compares vertex degree with assigned color index, helping you see how structure and solver choices influence the final coloring.