Tensions in Practice: Immediate assignment in tension with palette economy¶
Fixed conflict path · greedy label assignment
Four items conflict along the path A—B—C—D. A greedy rule assigns the smallest positive label not used by an already assigned neighbor. Visiting A, D, B, C uses three labels; visiting A, B, C, D uses two. Both assignments honor every conflict. The first result proves that three suffice, not that three are required.
Assign without revisiting earlier choices
Process items in the supplied order with a simple one-pass rule.
Use fewer distinct labels
Exploit the conflict structure to avoid consuming an unnecessary resource label.
Why these aims pull against each other
A locally available choice depends on earlier assignments. A valid greedy coloring is an upper bound on the required palette, and ordering can change that bound without changing the conflicts.
Choose an arrangement to see what changes and what remains difficult.
Finite illustrative comparisons. Labels carry the meaning; color does not establish a preference or measured effect.
What this choice protects
What it costs
When it fits
Compare the arrangements
Use order A, D, B, C
A and D first receive label 1. B then receives 2, forcing C to use 3 because its neighbors already carry 1 and 2.
| Visit step | Label | Must differ from | |
|---|---|---|---|
| A | 1 | 1 | B |
| B | 3 | 2 | A and C |
| C | 4 | 3 | B and D |
| D | 2 | 1 | C |
- What it protects
- No preliminary reordering or revision of the assigned items is required.
- What it costs
- Three labels are consumed even though this fixed graph permits two.
- When it fits
- Fits an imposed arrival/processing order or a setting where an extra available label costs less than planning or revisiting assignments.
Illustration note: All conflicts are shown in the fixed table. The example does not claim that every given order wastes a label.
Use order A, B, C, D
Traverse the known path so labels alternate 1, 2, 1, 2. Any edge requires at least two labels, and this assignment achieves that bound.
| Visit step | Label | Must differ from | |
|---|---|---|---|
| A | 1 | 1 | B |
| B | 2 | 2 | A and C |
| C | 3 | 1 | B and D |
| D | 4 | 2 | C |
- What it protects
- Two labels suffice for this exact graph.
- What it costs
- The order requires the relevant conflict structure before assignment and may be unavailable under irreversible online arrivals.
- When it fits
- Fits a known stable path or other structure whose useful ordering can be found and applied cheaply.
Illustration note: This is an exact finite path example, not a claim that finding an optimal order is easy for general graphs.
What this illustration does—and does not—establish
Graph Coloring: Greedy Heuristic versus Optimal Coloring supplies the gap between a greedy upper bound and the minimum. The finite assignments can be checked against every listed conflict.
- Labels encode pairwise separation only; the example does not include unequal room sizes, task durations or preferences.
- The same graph and greedy rule are retained across arrangements. Only the visit order changes.
- One of the edges proves that one label is impossible here; the explicit two-label assignment proves two are sufficient.
Source entries
Graph Coloring
Graph Coloring: Greedy Heuristic versus Optimal Coloring supplies the conflict examined here.
Greedy Heuristic versus Optimal Coloring
The failure mode is reading the greedy result as the chromatic number — provisioning to the heuristic's label count, which may overshoot — or trusting greedy on a dense graph where the gap between its answer and the optimum is large.
Structural Tensions
Greedy coloring with smart ordering gives a fast upper bound and usually suffices on sparse graphs, but it can use far more labels than necessary on dense or adversarially-ordered ones.