What does the chromatic number of a conflict graph tell a scheduler that joins clashing jobs by an edge?
answer
- count slots, not jobs
- edges mean cannot share
- minimum over every valid assignment
- each colour class runs together
- graph property, not a run's output
basics
~20 sThe chromatic number is the fewest colours that label every vertex so no edge has one colour at both ends. On a conflict graph it is the minimum number of time slots any valid schedule can use.
solid answer
~40 sModel each job as a vertex and each pair that cannot run together as an edge. A slot assignment is a colouring, and it is valid exactly when no edge is monochromatic. The chromatic number is the smallest number of colours for which such an assignment exists, so it is the fewest slots the schedule can possibly take — a floor that holds no matter how clever the scheduler is. Each colour class is an independent set, meaning every job wearing that colour can run together, so a k-colouring is the same object as a partition of the work into k conflict-free batches. It is a property of the graph, not the output of a run: a heuristic that used nine slots has proven only that the chromatic number is at most nine.
go deeper
Recall the shape: jobs are vertices, a conflict is an edge, a slot is a colour, and the chromatic number is how few slots are enough.
Explain that it is a minimum over all valid assignments, that each colour class is a conflict-free batch, and that one greedy run only produces an upper bound.
Show you use it as a floor when negotiating a schedule: prove a count is unreachable before the team spends a sprint chasing it, and audit precautionary edges that inflate it.
Frame it as the constraint model's price. Every edge someone adds defensively can only raise the round count, so who is allowed to declare a conflict is a design decision, not a detail.
## The model behind the question Start from the schedule rather than the graph. You have a set of jobs, and a rule says certain pairs may not run at the same time — they need the same exclusive resource, the same lock, the same operator. Draw one vertex per job and one edge per conflicting pair. That object is the **conflict graph**. Handing each job a time slot is exactly labelling each vertex, and the schedule is valid precisely when no edge carries the same label at both ends. Such a label is called a **colour**, and a labelling with that property is a **proper colouring**. ## What the number actually says The **chromatic number** of a graph `G`, written `χ(G)`, is the smallest number of colours admitting a proper colouring. Three words in that sentence carry the meaning: - **Smallest** — it is a minimum over every conceivable assignment, not the count one procedure happened to reach. A run that finished with nine colours has established `χ(G) ≤ 9` and nothing else. - **Exists** — the minimum is taken over assignments that are valid, so the number is well defined for any graph and depends on nothing but the graph. - **Proper** — only *adjacent* vertices must differ. Non-adjacent jobs may share a colour, and usually must, or the count would collapse to the number of jobs. The set of vertices carrying one colour is a **colour class**, and by definition no two of its members are adjacent: it is an **independent set**. So a proper colouring with k colours and a partition of the jobs into k conflict-free batches are the same object seen from two sides. That is why the count, and not the identity of the colours, is what matters — permuting the colour names gives another optimal colouring, never a better one. ## Reading it as a schedule | conflict graph | fewest slots | why | |---|---|---| | no conflicts at all | 1 | one batch runs the whole set | | every pair conflicts (n jobs) | n | no two jobs may ever share | | conflicts form a tree with an edge | 2 | alternate slots by depth parity | | conflicts form an even-length ring | 2 | alternation closes cleanly | | conflicts form an odd-length ring | 3 | alternation clashes at the closing edge | | conflicts drawable in the plane without crossings | at most 4 | the four-colour theorem | The practical readings that follow are worth stating plainly: - The chromatic number is the number of **rounds**, not the number of jobs and not the number of conflicts. - Every colour class is a batch that may be dispatched **concurrently**, so an optimal colouring is also a maximal-parallelism plan under those constraints. - Because it is a minimum, it is a **lower bound on every scheduler**: if it is 9, no ordering, no heuristic and no amount of tuning produces an 8-slot schedule. - Adding an edge can only hold the number steady or raise it; deleting one can only hold it steady or lower it. That monotonicity is what makes the modelling decisions below expensive. ## What it does not tell you - **Not which jobs pair up.** A graph usually has many optimal colourings, and the chromatic number picks none of them. Secondary goals — balancing batch sizes, keeping related work together — are decided after the count, not by it. - **Not the elapsed time.** Colouring assumes one uniform slot per colour. If jobs have different durations, the wall-clock length of the plan is a different optimisation, and the colour count only bounds how many rounds there are. - **Not capacity.** Plain colouring lets a colour class be arbitrarily large. If a slot can hold at most m jobs, you are asking a different question with an extra constraint bolted on. - **Not an algorithm.** The definition is a minimisation over all assignments, which is why a single greedy pass never establishes the value — it only produces an upper bound. ## Where teams go wrong with it The most expensive mistake is upstream of the mathematics: drawing an edge for *should not* rather than *cannot*. Every precautionary edge can only push the number up, and unlike a scheduling bug it pushes silently — the schedule still works, it just costs more rounds than the real constraints require. When a colour count looks too high, audit the edges before you audit the colouring. The second common mistake is reporting the output of one heuristic as the chromatic number; that number is a ceiling, and the gap between it and the truth is exactly what a better ordering, or a proof that none exists, is worth.
- Does the chromatic number tell you how long the schedule takes when jobs have different durations?No. Colouring counts rounds and silently assumes one uniform slot per colour. With unequal durations the elapsed time of a round is set by its longest job, so a plan with the fewest colours can still be slower than one with more. The colour count bounds the number of rounds; total elapsed time is a separate optimisation.
- What does the four-colour theorem guarantee, and why does it rarely help a scheduler?It says any graph that can be drawn in the plane with no crossing edges can be properly coloured with four colours. Conflict graphs from scheduling are usually not drawable that way — five jobs that all clash with one another already cannot be — so the bound simply does not apply. It is a fact about planar structure, not a general ceiling on slots.
- Two teams colour the same conflict graph and get 7 and 9 slots. What has each proved?Each has proved an upper bound: the chromatic number is at most 7, and therefore also at most 9. Neither has proved anything about the minimum. To claim 7 is optimal you need a separate argument from below, such as seven jobs that all conflict with one another.
saying these in an interview costs you the question
- Reports whatever count one heuristic produced as the chromatic number
- Thinks every job needs its own colour unless the jobs are identical
- Says it counts conflicting pairs or conflicting jobs rather than slots
- Assumes four colours are always enough for any conflict graph
- Believes non-adjacent jobs are also required to get different colours