skip to content

Why can a greedy colouring of a conflict graph never need more than the maximum degree plus one colours?

level: middleimportance: should knowfreq 45%

answer

  1. count what is blocked
  2. only coloured neighbours block
  3. at most degree colours blocked
  4. smallest free colour always exists
  5. ceiling is maximum degree plus one

basics

~20 s

Greedy gives each vertex the smallest colour none of its already-coloured neighbours holds. A vertex has at most maximum-degree neighbours, so at most that many colours are blocked, and one of the first maximum-degree-plus-one colours is always free.

solid answer

~40 s

Walk the vertices in any order and hand each one the lowest-numbered colour that no already-coloured neighbour is using. When you reach a vertex of degree d, at most d colours are blocked, because only neighbours can block and each blocks one. So among the colours `1 … d+1` at least one is free, and since `d` is at most the graph's maximum degree, no vertex ever reaches past maximum degree plus one. That gives a ceiling on the chromatic number, not its value: the ceiling is reached only by graphs where every pair conflicts and by odd rings. A star is the extreme opposite — the centre's degree may be huge while two slots suffice.

code

pseudocode · 9 lines
pseudocode
for each vertex v in chosen_order:
    used = empty set
    for each neighbour u of v:
        if colour[u] is assigned:
            add colour[u] to used
    c = 1
    while c is in used:
        c = c + 1
    colour[v] = c

go deeper

for a junior

Remember the rule and the ceiling: take the smallest colour no coloured neighbour has, and you never pass the busiest vertex's degree plus one.

for a middle

Derive the bound out loud from blocked colours, and show with one example that the ceiling can sit far above the true minimum.

for a senior

Demonstrate that you treat a greedy result as an upper bound in production: pair it with a lower-bound argument before declaring a slot count final.

for a principal

Weigh the ordering heuristic against its payoff. Chasing a better order is recurring engineering cost; decide when a proven-close-enough colouring ends the discussion.

## The procedure Greedy colouring fixes an order of the vertices and never revisits a decision. For each vertex in turn it collects the colours already assigned to that vertex's neighbours, then assigns the smallest colour not in that set. Nothing is backtracked and nothing is looked ahead to; uncoloured neighbours have no say. ## Why the ceiling holds The argument is a counting argument, one vertex at a time. 1. Let the vertex being coloured have degree `d`, meaning it has `d` neighbours in total. 2. Only a neighbour can block a colour, and each blocked colour needs at least one neighbour holding it, so **at most `d` colours are blocked** — fewer if some neighbours are still uncoloured or share a colour. 3. Among the `d + 1` colours `1 … d+1`, at most `d` are blocked, so at least one is free, and greedy takes the smallest free one. 4. Every vertex has `d ≤ Δ`, where `Δ` is the graph's **maximum degree**, so no vertex is ever forced past colour `Δ + 1`. That yields `χ(G) ≤ Δ + 1` for every graph, because greedy produces a valid colouring and the chromatic number is the minimum over valid colourings. Note what the bound is *not*: it is not a claim that greedy is optimal, and it is not a claim that `Δ + 1` colours are ever needed. ## How loose the ceiling can be | conflict graph | maximum degree | ceiling | fewest slots | |---|---|---|---| | every pair conflicts, n jobs | n − 1 | n | n | | ring of odd length | 2 | 3 | 3 | | ring of even length | 2 | 3 | 2 | | one job clashing with 50 others that never clash | 50 | 51 | 2 | The last row is the point: a single hub vertex drags `Δ` to 50 while the graph is still two-colourable. The ceiling is set by the busiest vertex, and the truth is set by the whole structure. ## Order decides what greedy actually gets The bound holds for *every* order, but the result does not. Take six jobs in two families, `a1 a2 a3` and `b1 b2 b3`, where `ai` conflicts with `bj` whenever `i ≠ j`, and no two members of a family ever conflict. Two slots suffice: put all the `a` jobs in slot 1 and all the `b` jobs in slot 2, and every conflicting pair is split. Now run greedy in the order `a1, b1, a2, b2, a3, b3`: - `a1` takes colour 1. `b1` is not adjacent to `a1`, so it also takes colour 1. - `a2` is adjacent to `b1` (colour 1), so it takes colour 2. `b2` is adjacent to `a1` (colour 1), so it takes colour 2. - `a3` is adjacent to `b1` and `b2` (colours 1 and 2), so it takes colour 3, and `b3` likewise. Three colours for a two-colourable graph, and the same construction with n families costs n colours instead of two. Two consequences follow: - **A greedy result is an upper bound only.** It proves the chromatic number is at most what it produced. - **Some order always achieves the optimum.** List the vertices of an optimal colouring class by class and greedy reproduces that count. The catch is that you need the optimal colouring to build the order, which is why practical orderings — busiest vertex first, or the vertex whose neighbours already show the most distinct colours — are heuristics with no guarantee attached. ## The refinement worth naming **Brooks' theorem** sharpens the ceiling by exactly one for almost everything: if a connected graph is neither a complete graph nor an odd ring, then `χ(G) ≤ Δ`. The two exceptions are precisely the cases where the extra colour is unavoidable — n mutually conflicting jobs need `n = Δ + 1` slots, and an odd ring needs `3 = Δ + 1`. Brooks does not say greedy will find that colouring; it says one exists. ## What to carry into an interview - Quote the bound as `Δ + 1` and be ready to derive it in one sentence about blocked colours. - Say immediately that it is a ceiling, and that the gap to the truth can be arbitrarily large. - Separate the two questions the material invites: *how many colours might greedy use* (up to `Δ + 1`, order-dependent) and *how many are needed* (the chromatic number, order-independent).

  • Can greedy use far more colours than the graph actually needs?
    Yes, and the gap is unbounded. A two-colourable graph can be ordered so greedy opens a new colour every second vertex, because it never revisits an assignment. An order achieving the optimum always exists — list an optimal colouring's classes one after another — but you would need that colouring to construct the order.
  • When can the ceiling be tightened below maximum degree plus one?
    Brooks' theorem: for a connected graph that is neither a complete graph nor an odd-length ring, the maximum degree alone suffices. Those two families are the exact exceptions, since n mutually conflicting jobs need n slots and an odd ring needs three, each one more than the maximum degree.
  • Does a low maximum degree guarantee a low slot count?
    Yes, in that direction only: the ceiling really is maximum degree plus one, so a graph where nobody clashes with more than three others never needs more than four slots. The reverse fails — a high maximum degree implies nothing, since one hub job can raise the maximum arbitrarily while two slots still suffice.

Seating arrivals one at a time: each person takes the first table with nobody they must avoid. The rule never opens more tables than one person's avoid-list plus one, but a bad arrival order still opens far more tables than the room ever needed.

saying these in an interview costs you the question

  • Claims greedy always finds the fewest possible colours
  • States the bound as the maximum degree, dropping the plus one
  • Believes the vertex order cannot change greedy's colour count
  • Treats maximum degree plus one as the answer rather than a ceiling
  • Believes ordering by degree first guarantees the minimum
  • Thinks uncoloured neighbours block colours during the pass