Why does a clique of mutually conflicting jobs put a floor under the number of slots a schedule needs?

## What a clique forces A **clique** is a set of vertices in which every pair is joined by an edge. Read on a conflict graph, it is a group of jobs that all clash with one another. A proper colouring must give different colours to the two ends of every edge, and inside a clique every pair is an edge, so all k members must carry k distinct colours. No colouring of the whole graph can do better on that subset, and the whole graph needs at least as many colours as any of its parts. Hence, with `ω(G)` for the size of the largest clique — the **clique number** — and `χ(G)` for the chromatic number: `ω(G) ≤ χ(G)` That inequality has a direction and it is worth saying aloud, because reversing it is the standard mistake. A clique certifies a **minimum**; it never caps the number of colours. ## Why a floor is worth having The chromatic number is defined as a minimum over all assignments, so a colouring you have in hand proves only an upper bound. Pair it with a clique and you bracket the truth: - A schedule using 9 slots proves `χ ≤ 9`. - Seven jobs that all clash prove `χ ≥ 7`. - The answer is somewhere in `7 … 9`, and if you find either an 8-job clique or an 8-slot schedule the bracket narrows. - When floor meets ceiling — a k-clique and a k-slot schedule — you have a **proof of optimality** that needs no further search. That last point is the real payoff in a design review. A clique is a short, checkable artefact: anyone can verify that the named jobs pairwise conflict. It converts "we could not do better" into "nobody can do better". ## The floor is not always reached Take five jobs arranged in a ring, each clashing only with its two ring neighbours. No three of them are mutually conflicting, so the clique number is 2. Yet two slots are impossible: alternate around the ring and, because the length is odd, the fifth job ends up adjacent to jobs in both slots at the closing edge. Three slots suffice. So `ω = 2` while `χ = 3`, and the floor is strictly below the truth. The gap can be far worse. There are graphs with **no three mutually conflicting jobs at all** whose chromatic number is arbitrarily large — the obstruction to colouring is a global structure, not a local group. That is why "find the biggest clique" is a lower-bound tactic and never a method for computing the answer. | conflict graph | clique number | fewest slots | |---|---|---| | four jobs all clashing | 4 | 4 | | ring of five jobs | 2 | 3 | | one hub job clashing with many isolated jobs | 2 | 2 | | any graph split into two clash-free families | 2 | 2 | | overlapping reservations on one timeline | busiest instant | busiest instant | ## Squeezing the true value between two bounds Combining with the greedy ceiling from the busiest vertex gives the sandwich every practitioner works inside: `ω(G) ≤ χ(G) ≤ Δ(G) + 1` Both ends can be loose at once, and improving either is real work: raising the floor means finding a larger mutually conflicting group, lowering the ceiling means finding a better assignment. Some structured families close the sandwich by themselves — conflicts derived from intervals on a line, and any graph whose jobs split into two clash-free families, always have the clique number as their exact answer. Those are the families where "count the worst mutual clash" is not just a bound but the answer, and recognising that your conflicts have that structure is worth more than any amount of colouring effort. ## Practical reading - When someone proposes a target slot count, look for a clique that already exceeds it before debating the algorithm. - When the floor and your schedule agree, stop optimising; the remaining levers are in the model, not the colouring. - When the floor sits far below your schedule, the gap is genuinely ambiguous: the truth may be near either end, and only a better colouring or a larger clique resolves which. - Never present the clique number as the answer. It is the half of the answer you can prove cheaply.