Walk a graph's vertices in some fixed order. For each one, look at whichever of its neighbors are already colored, and assign the smallest color number none of them hold. That's the entire rule — no lookahead, no backtracking, one pass, done. It's the ninth entry filed under Greedy, and the first one over a graph rather than an interval set, a frequency table, or a capacity. Graph Coloring already covers this same question — assign colors so no edge joins two same-colored vertices — with a backtracking search that finds the true minimum, at exponential worst-case cost and no guarantee of finishing quickly. This page is the other end of that trade: always fast, one pass, but with no promise of using anywhere near the fewest colors possible.
The graph below is a crown graph: two groups of four vertices,
a1–a4 and b1–b4, with an edge between
ai and bj for every pair except where
i = j. No edge ever runs within a group, so the whole graph is two-colorable in
principle — but greedy doesn't know that, and whether it finds a 2-coloring depends entirely on
which order you feed it. Pick a vertex order and a neighbor-checking rule, then press
Step or Run.
Greedy coloring's one guarantee has nothing to do with how few colors it uses — it's a bound on
how many it could ever be forced to use. When vertex v is colored, at most
degree(v) neighbors are already colored, and each contributes at most one excluded
color. So among colors 0 through Δ (that's Δ+1
colors total, where Δ is the graph's maximum degree), at least one is never
excluded for any vertex, no matter the order. Every vertex on the demo's graph has degree
3 (each ai touches exactly the three bj with
j ≠ i, and symmetrically for each bj), so
Δ+1 = 4 — and a sweep of 5,000 random vertex orders on this exact graph, using
the correct rule, never once needed a fifth color, confirming the bound holds for every order, not
just the two offered above.
What the bound does not promise is closeness to the true minimum. This graph's real
chromatic number is 2 — group a versus group
b is itself a valid 2-coloring, since every edge runs between the groups and none
within one, confirmed here independently by a plain two-coloring breadth-first search rather than
just asserted. Feed the vertices in grouped order and greedy finds that exact
2-coloring: every a vertex gets colored before any b vertex sees a
colored neighbor at all, so all four a's take color 0, then all four b's
take color 1. Feed the identical graph in interleaved order instead and greedy
uses all 4 colors — a1=0, b1=0, a2=1,
b2=1, a3=2, b3=2, a4=3, b4=3 —
hitting the Δ+1 worst case exactly, on a graph that never needed more than 2.
Same graph, same rule, same code; only the order changed.
function greedyColor(adjacency, order) {
const n = adjacency.length;
const color = new Array(n).fill(-1);
for (const v of order) {
const excluded = new Set();
for (const u of adjacency[v]) {
if (color[u] !== -1) excluded.add(color[u]);
}
let c = 0;
while (excluded.has(c)) c++;
color[v] = c;
}
return color;
}No sorting, no priority queue, no revisiting a vertex once it's colored — the entire algorithm
is one pass over order, checking each edge once from whichever endpoint gets colored
second. That simplicity is exactly why the bound above is the only guarantee on offer: there is no
step anywhere in this loop that looks at the graph's global structure, so nothing here can notice
that groups a and b would have made a clean 2-coloring if only
they'd been visited in the right order.
Vertex order changes how many colors get used — sometimes optimally, sometimes hitting
the worst case exactly — without changing a single line of the algorithm. The demo above
makes this concrete rather than asserting it: grouped order finds the true 2-color
optimum, interleaved order forces all 4 of the colors the Δ+1 bound
allows, on the identical graph, using the identical correct rule. Unlike
Set Cover's greedy approximation, which comes with a
proven O(ln n) ceiling on how far off it can land relative to the true optimum
regardless of input, greedy coloring has no such ceiling at all — the gap between what it uses and
the true chromatic number can be made to grow without bound. Stretching this same crown-graph
construction to n vertices per group under the interleaved order forces exactly
n colors every time (checked directly for n = 2, 3, 4, 5, 8, 10, and 20,
matching Δ+1 = n exactly at every size), while the true chromatic number stays
fixed at 2 forever — a gap that widens with no ceiling as the graph grows, not a fixed worst-case
factor the way Set Cover's is.
Checking only the most recently colored neighbor, instead of every colored neighbor,
can produce an outright invalid coloring — not just a wasteful one. Switch the demo's
rule to check only the most recently colored neighbor on the unchanged
interleaved order: vertex a3's real neighbors are
b1, b2, and b4. By the time a3 is colored,
both b1 (color 0) and b2 (color 1) are already colored — but this rule
only looks at whichever of them was colored most recently, b2, and excludes only
color 1. That leaves color 0 looking free, so a3 takes it — directly colliding with
b1, which is also color 0 and genuinely adjacent. The demo's own independent
end-of-run scan, which re-examines every edge for a same-color pair rather than trusting the
coloring loop's own bookkeeping, flags this pair immediately; on this exact run it finds four such
collisions, not just one. This isn't reliably broken, either, which is what makes it a real trap
rather than an obviously-bad idea: the identical shortcut on the grouped order
produces zero collisions, because every neighbor an already-colored vertex has at that point
happens to share the same color anyway. Checked beyond these two hand-picked orders: across 5,000
random vertex orders on this graph, the shortcut produced at least one genuine collision in 1,264
of them (25.3%) — wrong often enough to matter, rare enough that a few lucky test orders could hide
it.
Time: O(V+E) — each vertex is visited once, and each edge is
examined exactly once, from whichever of its two endpoints gets colored second (that's the one
already-colored neighbor it can see at that moment). Space: O(V) for
the color array; the per-vertex exclusion set never holds more than degree(v) entries,
so O(Δ) at any one step, which is at most O(V). The broken
most-recent-neighbor variant above costs no more or less — the bug is entirely in which colors it
considers excluded, not in how much work it does.
See Choosing a Greedy Strategy for how this entry compares against the site's other nine Greedy entries — short version: this is the guide's first entry with no ratio bound at all, a step past even Set Cover's proven-but-imperfect guarantee. For the exact minimum this page's greedy rule doesn't promise, see Graph Coloring's backtracking search.