Graph Coloring

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 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.

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">{{hint}}</p>
<div class="palette" id="palette" role="toolbar" aria-label="{{aria_colors}}">
  <button class="swatch" data-color="1" style="--c:#e63946" title="{{title_red}}"></button>
  <button class="swatch" data-color="2" style="--c:#2a9d8f" title="{{title_green}}"></button>
  <button class="swatch" data-color="3" style="--c:#457b9d" title="{{title_blue}}"></button>
  <button class="swatch" data-color="4" style="--c:#e9c46a" title="{{title_yellow}}"></button>
  <button class="swatch erase" data-color="0" title="{{title_erase}}">✕</button>
</div>
<svg id="map" viewBox="0 0 360 300" role="img" aria-label="{{aria_map}}">
  <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">{{btn_auto}}</button>
  <button id="reset" type="button" class="ghost">{{btn_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; }

// Code not found

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.

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.

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.