Introduction

Picture a map where neighboring countries must have different colors, or a school timetable where two exams a student takes can't share a slot. Both are the same puzzle in disguise: take things that are connected (they conflict) and give each a color so that no two connected things share one — using as few colors as possible.

In the language of mathematics, the things become nodes and the conflicts become edges: a graph. The smallest number of colors that works is called the chromatic number.

The rule could not be simpler. Yet, as we'll see, finding that smallest number of colors is one of the hardest problems we know — and it hides inside maps, timetables, compilers, and the wireless signal on your phone.

The Greedy Coloring

The natural strategy is greedy: go through the nodes one by one and give each the smallest-numbered color that none of its already-colored neighbors uses. If colors 1 and 2 are taken by neighbors, use color 3.

It's fast and it always produces a valid coloring — no two neighbors will ever clash. For many graphs it even finds the true minimum.

But greedy has a hidden weakness: the result depends entirely on the order in which you visit the nodes. A lucky order uses few colors; an unlucky one can use far more than necessary, even on the very same graph.

Color a Real Map

Forget abstract dots for a moment and color an actual map. The rule is the one every atlas follows: regions that share a border must get different colors, and we want to use as few colors as we can. (Regions and "shares a border" are exactly the nodes and edges from before — a map is a graph.)

The map below is flat, and a famous result — the Four Color Theorem — promises that any flat map can be colored with at most 4 colors. This particular map is built to need all four: no matter how you try, three colors will always leave two neighbors clashing.

Try it: pick a color from the palette, then click a region to paint it — keep going until no two bordering regions clash. Then press Auto-color to watch the greedy algorithm fill it in. Greedy is fast and always produces a valid map — but the order in which it colors regions can push it to use more colors than strictly necessary, and finding the guaranteed minimum is the hard part.

<p class="hint">Pick a color from the palette, then click a region to paint it. The rule: <b>regions that share a border must have different colors</b>. Try to color the whole map — using as few colors as you can. Or press <b>Auto-color</b> to let the greedy algorithm do it.</p>
<div class="palette" id="palette" role="toolbar" aria-label="Colors">
  <button class="swatch" data-color="1" style="--c:#e63946" title="Red"></button>
  <button class="swatch" data-color="2" style="--c:#2a9d8f" title="Green"></button>
  <button class="swatch" data-color="3" style="--c:#457b9d" title="Blue"></button>
  <button class="swatch" data-color="4" style="--c:#e9c46a" title="Yellow"></button>
  <button class="swatch erase" data-color="0" title="Erase">✕</button>
</div>
<svg id="map" viewBox="0 0 360 300" role="img" aria-label="Map to color">
  <defs>
    <pattern id="clash" patternUnits="userSpaceOnUse" width="10" height="10" patternTransform="rotate(45)">
      <rect width="10" height="10" fill="#fff"></rect>
      <line x1="0" y1="0" x2="0" y2="10" stroke="#e63946" stroke-width="6"></line>
    </pattern>
  </defs>
  <g id="regions" stroke="#fff" stroke-width="3"
     font-family="system-ui, sans-serif" font-size="15" font-weight="700" text-anchor="middle">
    <g class="region" data-id="A"><rect x="0"   y="0"   width="180" height="90"></rect><text x="90"  y="50">A</text></g>
    <g class="region" data-id="B"><rect x="180" y="0"   width="180" height="90"></rect><text x="270" y="50">B</text></g>
    <g class="region" data-id="C"><rect x="0"   y="90"  width="120" height="100"></rect><text x="60"  y="145">C</text></g>
    <g class="region" data-id="D"><rect x="120" y="90"  width="120" height="100"></rect><text x="180" y="145">D</text></g>
    <g class="region" data-id="E"><rect x="240" y="90"  width="120" height="100"></rect><text x="300" y="145">E</text></g>
    <g class="region" data-id="F"><rect x="0"   y="190" width="360" height="110"></rect><text x="180" y="250">F</text></g>
  </g>
</svg>
<div class="bar">
  <button id="auto" type="button">Auto-color (greedy)</button>
  <button id="reset" type="button" class="ghost">Reset</button>
</div>
<p id="status" class="status"></p>

* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; }
.hint { font-size: .9rem; color: #444; margin: 0 0 .5rem; line-height: 1.4; }
.palette { display: flex; gap: .5rem; margin: 0 0 .6rem; align-items: center; }
.swatch { width: 38px; height: 38px; border-radius: 8px; border: 2px solid #ccc; background: var(--c, #fff); cursor: pointer; padding: 0; transition: transform .08s; }
.swatch:hover { transform: translateY(-2px); }
.swatch.erase { background: #fff; color: #888; font: 700 16px system-ui; }
.swatch.sel { border-color: #111; box-shadow: 0 0 0 3px rgba(17,17,17,.18); transform: translateY(-2px); }
svg { width: 100%; max-width: 360px; height: auto; display: block; }
.region rect { cursor: pointer; transition: fill .12s; }
.region text { pointer-events: none; fill: #fff; paint-order: stroke; stroke: rgba(0,0,0,.35); stroke-width: 3px; }
.bar { display: flex; gap: .5rem; margin: .5rem 0; flex-wrap: wrap; }
button#auto, button#reset { font: 600 14px system-ui, sans-serif; padding: .45rem .9rem; border: 1px solid #457b9d; background: #457b9d; color: #fff; border-radius: 8px; cursor: pointer; }
button#reset { background: #fff; color: #457b9d; }
.status { font-size: .95rem; font-weight: 600; min-height: 1.2em; margin: .3rem 0 0; line-height: 1.4; }
.status.ok { color: #0a7d33; }
.status.bad { color: #c0392b; }

const fmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
// A flat "map" of 6 regions. Two regions are neighbors when they share a
// real border. This map needs exactly 4 colors — the most the Four Color
// Theorem ever requires. Pick a palette color, then click a region to paint it.
const PALETTE = ['#e9ecef', '#e63946', '#2a9d8f', '#457b9d', '#e9c46a']; // 0 = uncolored
const NAMES = ['uncolored', 'red', 'green', 'blue', 'yellow'];
const regions = ['A', 'B', 'C', 'D', 'E', 'F'];
const adj = {
  A: ['B', 'C', 'D'],
  B: ['A', 'D', 'E'],
  C: ['A', 'D', 'F'],
  D: ['A', 'B', 'C', 'E', 'F'],
  E: ['B', 'D', 'F'],
  F: ['C', 'D', 'E'],
};
const color = {};
regions.forEach(r => color[r] = 0);
let active = 1; // currently selected palette color

const rectOf = id => document.querySelector(`.region[data-id="${id}"] rect`);

function conflicts() {
  let n = 0; const bad = new Set();
  for (const r of regions)
    for (const nb of adj[r])
      if (color[r] !== 0 && color[r] === color[nb]) { n++; bad.add(r); bad.add(nb); }
  return { count: n / 2, bad };
}

function render() {
  const { count, bad } = conflicts();
  for (const r of regions)
    rectOf(r).setAttribute('fill', bad.has(r) ? 'url(#clash)' : PALETTE[color[r]]);
  const used = new Set(regions.map(r => color[r]).filter(c => c !== 0)).size;
  const allColored = regions.every(r => color[r] !== 0);
  const st = document.getElementById('status');
  st.className = 'status';
  if (count > 0) {
    st.textContent = fmt('%count% bordering pair(s) clash (striped) — paint them different colors.', { count: count });
    st.classList.add('bad');
  } else if (!allColored) {
    st.textContent = `No clashes so far — keep painting until every region has a color.`;
  } else {
    st.textContent = fmt('Valid! You colored the map with %used% color(s). A flat map never needs more than 4 — and this one needs all 4.', { used: used });
    st.classList.add(used <= 4 ? 'ok' : 'bad');
  }
}

function selectColor(c) {
  active = c;
  document.querySelectorAll('.swatch').forEach(s =>
    s.classList.toggle('sel', Number(s.dataset.color) === active));
}

function autoColor() {
  regions.forEach(r => color[r] = 0);
  for (const r of regions) { // greedy in A..F order
    const taken = new Set(adj[r].map(nb => color[nb]).filter(c => c !== 0));
    let c = 1; while (taken.has(c)) c++;
    color[r] = c;
  }
  render();
  const used = new Set(regions.map(r => color[r])).size;
  console.log(fmt('Greedy colored the map with %used% colors: %map%', { used: used, map: regions.map(r => `${r}=${NAMES[color[r]]}`).join(', ') }));
}

document.querySelectorAll('.swatch').forEach(s =>
  s.addEventListener('click', () => selectColor(Number(s.dataset.color))));
document.querySelectorAll('.region').forEach(g =>
  g.addEventListener('click', () => { color[g.dataset.id] = active; render(); }));
document.getElementById('auto').addEventListener('click', autoColor);
document.getElementById('reset').addEventListener('click', () => { regions.forEach(r => color[r] = 0); render(); });

selectColor(1);
render();
Result
Console

The Real Complexity

How hard is graph coloring, really?

  • Checking a coloring is trivial: just scan every edge and confirm its two ends differ.
  • Finding the minimum number of colors (the chromatic number) is NP-hard. Even the yes/no question "can this graph be colored with just 3 colors?" is NP-complete — as hard as any problem in NP.
  • Greedy runs in seconds but gives no guarantee of optimality; its quality depends on the node order.
  • A beautiful special case: the Four Color Theorem says any flat map needs at most 4 colors. But that's a guarantee only for planar graphs — in general graphs there's no such friendly bound.

Graph coloring is a textbook example of a problem that's easy to verify but hard to solve — exactly the gap at the heart of the P vs NP question.

Where It Matters

Whenever things compete for a limited set of "slots" and some pairs can't share, you're coloring a graph:

  • Wireless spectrum (4G/5G, Wi-Fi): nearby antennas must use different frequencies to avoid interference — colors are frequencies.
  • Exam and class timetables: two exams sharing a student can't be at the same time — colors are time slots.
  • Compiler register allocation: variables alive at the same moment can't share a CPU register — colors are registers.
  • Sudoku and map coloring: classic puzzles that are coloring problems in disguise.
  • Scheduling and conflict resolution: meetings, machines, sports fixtures — anywhere "these two can't overlap" appears.

In all of them, the same trade-off returns: greedy and clever heuristics are fast and usually good enough, while the provably optimal answer stays out of reach at scale.

Conclusion

Graph coloring starts with a rule a child understands — neighbors must look different — and ends at the frontier of computer science. Greedy coloring is fast and always valid, but the number of colors it uses depends on luck and order. Finding the true minimum is NP-hard, and even asking for "just 3 colors" is NP-complete.

That's the recurring lesson of this site in miniature: verifying an answer can be effortless while finding the best answer is intractable. The next time your phone holds a clean signal in a crowded place, remember there's a coloring problem being quietly, cleverly approximated behind the scenes.

Share this article

Pick a channel — or use your device's native share sheet.

Comments

Loading comments...

https://www.kipuhub.com/en/article/graph-coloring/Content licensed under CC BY-NC 4.0.