Chromatic Number Estimator
Estimate the chromatic number of a graph using Brook's theorem and greedy coloring bounds.
About this calculator
This calculator estimates bounds on a graph's chromatic number — the fewest colors needed to color every vertex so that no two directly connected vertices share a color — from three summary numbers alone: how many vertices the graph has, how many edges connect them, and the highest degree any single vertex reaches. It never receives the actual list of which vertices connect to which; every bound here is derived purely from those three counts, not from a real graph structure. The upper bound is the classic plus-one rule: no graph needs more colors than one more than its highest vertex degree.
Brook's bound narrows that by checking whether the edge count matches exactly what a complete graph on that many vertices would have; if it does, the calculator assumes every vertex is mutually connected and returns the vertex count itself, and otherwise falls back to the maximum degree. The greedy estimate simplifies down to the average degree plus one, rounded up and capped at the maximum-degree-plus-one upper bound — a widely used heuristic, not a guarantee — so growing the edge count while holding vertices fixed pushes the estimate up, while growing the vertex count with edges fixed pushes it back down, since both changes move the same underlying ratio of edges to vertices in opposite directions. This page does not verify: it cannot distinguish an actual complete graph from any other graph shape that happens to share the identical edge count, since it never sees real vertex-to-vertex connections, and it performs no check that the three numbers you enter even describe a graph that could exist — a maximum degree larger than vertices minus one, for instance, is accepted without complaint.
Inputs
Results
Greedy Coloring Estimate
4
Brook's Bound
4
How to Use This Calculator
- Enter the number of Vertices and Edges in your graph.
- Input the Maximum Degree of any vertex.
- Review the Upper Bound (Max Degree + 1) from Vizing's theorem and the Brooks Bound for non-complete, non-odd-cycle graphs.
- Check the Greedy Coloring Estimate — this is a practical upper bound for sparse graphs.
- Use these bounds to determine the minimum colors needed before running an exact coloring algorithm.
How the result changes with Vertices
| Vertices | Greedy Coloring Estimate | Brook's Bound |
|---|---|---|
| 4 | 5 | 4 |
| 6 | 5 | 4 |
| 12 | 3 | 4 |
| 20 | 3 | 4 |
What each input means
- Vertices
- Number of vertices in the graph
- Edges
- Number of edges in the graph
- Max Degree (Δ)
- Maximum vertex degree in the graph
How this is calculated
Worked example, using the default values
- Identify Input ParametersVertices = 8, Edges = 12, Max Degree (Δ) = 4 = 3 input(s) provided
- Calculate Greedy Coloring EstimateGreedy Coloring Estimate = min(greedyEstimate4 = 4
- Calculate Brook's BoundBrook's Bound4 = 4
- Calculate Upper BoundUpper Bound5 = 5
Engine last updated . Checked against 2 independently-derived tests — how we verify calculators. Built by Paul Gunder, a software engineer, not a licensed financial, medical, or legal professional.
Frequently Asked Questions
What does the greedy coloring estimate actually calculate?
It reduces to a simple formula: the average vertex degree — twice the edge count divided by the vertex count — plus one, rounded up to the next whole number, then capped at the maximum-degree-plus-one upper bound shown alongside it. Average-degree-plus-one is only a heuristic estimate, not a guaranteed bound — a graph can have a low average degree yet still need far more colors (a dense cluster plus many isolated vertices, for example). The bound that is actually guaranteed to hold for every graph is maximum-degree-plus-one, which is why the estimate is capped there; the true chromatic number can still be lower than either figure.
How does the calculator decide whether Brook's bound uses the vertex count or the max degree?
It checks a single condition: does the edge count exactly equal the number of edges a complete graph with that many vertices would have? If so, it assumes the graph is complete and every vertex needs its own color, returning the vertex count. Otherwise it falls back to the maximum degree, which is Brook's theorem's guarantee for a connected graph that is neither complete nor an odd cycle.
Why do vertices and edges seem to push the greedy estimate in opposite directions?
The greedy estimate depends on vertices and edges only through their ratio — edges divided by vertices, doubled, to get the average degree. Increasing the edge count while holding vertices steady raises that ratio and pushes the estimate up; increasing the vertex count while holding edges steady lowers the same ratio and pushes the estimate down. They sit on two sides of the identical fraction.
Can this calculator tell me the exact chromatic number of my graph?
No. It only reports bounds — an upper bound, Brook's bound, and a greedy heuristic estimate — none of which is guaranteed to equal the true minimum number of colors needed. Finding the exact chromatic number generally requires an algorithm that examines the graph's actual vertex-to-vertex connections, which this calculator never receives, only aggregate counts.
Related Calculators
The questions that sit next to this one — chosen by subject, including calculators filed under a different category.
Graph Theory Calculator
Analyze graph properties including degree, density, connectivity, and Eulerian path possibility.
Discrete MathematicsPermutations & Combinations Calculator
Calculate permutations and combinations with or without repetition for any n and r values.
Discrete MathematicsBinomial Coefficient Calculator
Calculate nCr and nPr values with Pascal's triangle row visualization.
More in Math & Statistics.