Chromatic Number Calculator
Example Data Table
| Graph | Vertices | Edges | Chromatic Number | Reason |
|---|---|---|---|---|
| Triangle K3 | 3 | 3 | 3 | Every pair of vertices is adjacent. |
| Cycle C5 | 5 | 5 | 3 | Odd cycles cannot be colored with two colors. |
| Complete Bipartite K3,3 | 6 | 9 | 2 | All bipartite graphs are two-colorable. |
| Wheel W6 | 6 | 10 | 4 | The hub plus an odd rim requires four colors. |
Formula Used
The chromatic number of a graph, written as χ(G), is the smallest integer k for which the vertices can be colored with k colors while every adjacent pair receives different colors.
Core definition: χ(G) = min{k : there exists a coloring c(v) ∈ {1, 2, ..., k} and c(u) ≠ c(v) for every edge uv}.
Lower bounds: χ(G) ≥ ω(G), where ω(G) is the clique number, and χ(G) ≥ 1 for any non-empty graph.
Upper bounds: χ(G) ≤ Δ(G) + 1, where Δ(G) is the maximum vertex degree. The page also computes a DSATUR heuristic coloring to establish an initial upper bound before exact search.
Method: This calculator validates the graph, computes structural bounds, then runs a DSATUR-style branch-and-bound search. When the search finishes within the chosen limit, the displayed chromatic number is exact.
How to Use This Calculator
- Enter a graph name so exported files have a clear title.
- Choose either Edge list or Adjacency matrix input mode.
- Optionally enter vertex labels. If you leave them blank, the page infers or generates labels automatically.
- Paste the graph edges or matrix values. Keep the graph simple, undirected, and loop-free.
- Set a search time limit. Higher limits help with harder graphs.
- Press Calculate Chromatic Number to show the result below the header and above the form.
- Review the summary metrics, color assignments, bounds, and interpretation table.
- Use the CSV or PDF buttons to export the result for reports, coursework, or audits.
Frequently Asked Questions
1. What does the chromatic number represent?
It is the smallest number of colors needed to color all vertices so that adjacent vertices never share the same color.
2. Does this page support directed graphs?
No. The calculator assumes a simple undirected graph. Directed inputs should be converted to undirected adjacency before analysis.
3. Why can large graphs take longer?
Exact graph coloring is computationally hard. Search time rises quickly as vertices and constraints increase, especially near dense or highly irregular structures.
4. What is the meaning of the lower bound?
The lower bound shows the minimum plausible chromatic number implied by structure, especially clique size. The exact answer can never be smaller.
5. What is the meaning of the upper bound?
The upper bound comes from a valid coloring found by the heuristic search. The exact chromatic number can never exceed that value.
6. Can isolated vertices change the answer?
Usually no. Isolated vertices can share any color already in use, so they rarely increase the chromatic number.
7. Why does a bipartite graph often return 2?
Every non-empty bipartite graph is two-colorable because its vertices can be divided into two independent sets with no internal edges.
8. When should I raise the search time limit?
Increase the limit when bounds do not match, graphs are dense, or the page reports only a best upper bound instead of an exact result.