Several colours on every vertex

A radio network assigns frequencies to transmitters, and transmitters close enough to interfere must use different ones. That is graph colouring. Now suppose each transmitter needs three frequencies rather than one, and interfering transmitters must have no frequency in common. That is colouring with several colours on every vertex — an $m$-fold colouring — and the question is the same as before: how few colours in total will do?

For most graphs the answer is not simply $m$ times the one-colour answer, and the Kneser graphs are where the difference is clearest. The vertices are the $k$-element subsets of $\{1, \dots, n\}$, joined when disjoint. The colours a circle forces showed that one colour a vertex needs exactly $n - 2k + 2$ colours, a theorem of Lovász whose proof went through antipodal points on a sphere. With several colours a vertex, the answer is conjectured and not known.

The case with an obvious answer #

When $m = k$, every $k$-set can simply be coloured by its own elements. Two disjoint sets then share no colour, because they share no element, and $n$ colours suffice.

No fewer than $n$ will do, and the reason is a count. A colour class — the set of vertices carrying one particular colour — must contain no two disjoint sets: it is an intersecting family. The largest family that always meets has $\binom{n-1}{k-1}$ members, the Erdős–Ko–Rado bound, achieved by all the sets through one point. There are $\binom nk$ vertices each needing $m$ colours, so at least

$$\frac{m \binom nk}{\binom{n-1}{k-1}} = \frac{mn}{k}$$

colours are needed. At $m = k$ that is exactly $n$, and the own-elements colouring meets it.

That bound is the fractional chromatic number times $m$. Allow each vertex to be split among colours in fractions summing to one, and the fewest colours in total is $n/k$ — a linear program whose dual is the count of the largest intersecting family. Every $m$-fold colouring is a fractional colouring scaled by $m$, so $mn/k$ is always a lower bound, and for $m = 1$ it is badly wrong: $n/k$ against Lovász’s $n - 2k + 2$.

There is a precise sense in which the fractional number is where the $m$-fold numbers are heading. For any graph, the fewest colours for an $m$-fold colouring, divided by $m$, tends to the fractional chromatic number as $m$ grows: with many colours a vertex, the rounding that separates whole colourings from fractional ones becomes a smaller and smaller share of the total. So the one-colour problem and the fractional problem are the two ends of a single sequence, and the $m$-fold numbers are the steps between them. For Kneser graphs the two ends are far apart — $n - 2k + 2$ against $n/k$ — and the question is how the sequence gets from one to the other.

Stahl’s formula #

Saul Stahl studied these colourings in 1976 and wrote down a formula that interpolates between the two cases understood. Write $m = qk - r$ with $0 \le r < k$. Then the conjecture is that exactly

$$qn - 2r$$

colours are needed. At $m = 1$, $q = 1$ and $r = k - 1$, and the formula gives $n - 2k + 2$, Lovász’s number. At $m = k$ it gives $n$. Past $m = k$ it repeats with period $k$: every $k$ extra colours a vertex costs exactly $n$ extra colours in total.

Half the formula is a theorem. Stahl showed that $qn - 2r$ colours always suffice. Two constructions give it. First, adding $k$ colours to every vertex never costs more than $n$: keep an existing colouring and give each set its own $k$ elements from a fresh palette of $n$. Second, for $m < k$, Stahl found a map from the $k$-sets of $n$ points to the $(k-1)$-sets of $n - 2$ points that keeps disjoint sets disjoint; applying it $r$ times lands in the $m$-sets of $n - 2r$ points, which can be coloured by their own elements with $n - 2r$ colours. Together they give $qn - 2r$.

The other half — that no colouring does better — is the conjecture. It is known for several families of cases, including the one-colour case by Lovász’s theorem, and it is open in general.

A threefold colouring the count does not predict #

On the Petersen graph, three colours a vertex need eight colours. That is $q = 2$, $r = 1$ in Stahl’s formula, $2 \cdot 5 - 2 = 8$, and it is also what counting gives: thirty slots, four per colour, so at least $7.5$, rounded to eight. Here the count happens to be enough.

Move to six points. The pairs from $\{1, \dots, 6\}$ form a Kneser graph with fifteen vertices, and three colours a vertex need, by counting, $3 \cdot 6/2 = 9$ colours. Stahl’s formula says $2 \cdot 6 - 2 = 10$. The count and the conjecture now disagree, and a search is needed to decide.

For pairs, the colour classes are easy to describe. A family of pairs in which every two meet is either a star — pairs through a common point — or a triangle — the three pairs inside one triple. The figures check this by enumerating every family of pairs from five points. So a colouring with $c$ colours is a list of $c$ stars and triangles, with every pair appearing in at least $m$ of them.

Why nine is impossible can be seen without the search. Fifteen pairs, each needing three colours, make forty-five slots. A star covers five pairs and a triangle three, so nine classes cover at most forty-five, and only if all nine are stars and no pair is covered more than three times. Write $x_i$ for the number of stars centred at point $i$. The pair $\{i, j\}$ is covered by the stars at $i$ and at $j$, so $x_i + x_j = 3$ for every pair. With three points $i, j, l$, adding $x_i + x_j$ and $x_i + x_l$ and subtracting $x_j + x_l$ gives $2x_i = 3$, which no whole number satisfies. Nine colours cannot work, and ten, as drawn, can.

The argument is a parity obstruction dressed as arithmetic: stars cover pairs in a way that treats every point alike, and an odd demand cannot be split evenly between two ends. It is the reason odd $m$ is where the formula and the count part company for pairs.

Every case the search can reach #

The same search runs on every Kneser graph of pairs from five to eight points, with one to five colours a vertex. For each, it tries every collection of stars and triangles one colour short of the answer and shows none covers every pair enough times; then it produces a colouring at the answer, which the figure checks edge by edge. In every cell the answer is Stahl’s formula.

The table’s pattern is the formula’s. Even $m$ lands exactly on the counting bound, because even $m$ is a multiple of $k = 2$ and the own-elements construction is exact there. Odd $m$ lands above it by $\lfloor n/2 \rfloor - 2$ colours, which is zero for five points and grows with $n$. The eight shaded cells are the ones in which counting fails and something about the structure of the graph has to be used.

Drawn against $m$, each series is a staircase with two step sizes. Going from odd $m$ to even adds two colours; going from even to odd adds $n - 2$. In the formula’s terms, the first step keeps $q$ and drops the remainder $r$ from one to nought, which gives back the two colours the remainder cost; the second raises $q$ by one, adding $n$, and brings the remainder back, taking two away. The staircase is the formula read one step at a time, and the search found it independently in every row.

The graphs where counting is always enough #

The formula has a quiet consequence for the odd graphs, the Kneser graphs on the $k$-sets of $2k + 1$ points, of which the Petersen graph is the first. There the excess over counting is $\lfloor r(2k+1)/k \rfloor - 2r = \lfloor 2r + r/k \rfloor - 2r$, and since $r < k$ that is nought. So if Stahl is right, the odd graphs need exactly as many colours as counting says for every number of colours a vertex — including one, where counting gives $\lceil (2k+1)/k \rceil = 3$ and Lovász’s theorem gives $3$ as well.

That makes the odd graphs the opposite of what the one-colour story made them look like. There they were the graphs with no short odd cycles that still needed three colours, a surprise for any argument based on local structure. Here they are the graphs on which the crudest global argument — how many vertices can share a colour — is always exact. Both are true, and they are compatible: the odd graphs are hard for local reasoning and easy for counting, while the Kneser graphs on many more points than $2k$ are the ones where counting falls furthest behind.

The Petersen rows of the table show it: pairs from five points meet the counting bound at every $m$ searched, and the other rows fall behind it at every odd $m$.

What the search can and cannot say #

Every case in the table has $k = 2$, and that is not an accident of patience. For pairs the colour classes are stars and triangles, a short list, and the search is a small covering problem. For triples the intersecting families are far more varied — stars, Fano planes, families built around a fixed triple, and thousands more — and even seven points produce over six thousand maximal ones, enough to make the covering search slow at every interesting $m$. The cases where Stahl’s conjecture is genuinely open are out of its reach.

So the table is a check on the formula, not evidence about the open cases. It shows the formula is the right shape, that the search and the formula were not both mistaken in the same way, and where exactly the count falls short. It says nothing about $k = 5$ or $n = 40$.

The final picture shows the size of what a proof would have to supply. At $m = 1$ the excess over counting is $n - 2k + 2 - \lceil n/k \rceil$, and Lovász’s proof supplies it by finding a point on a sphere that no colouring can avoid — a Borsuk–Ulam argument, the same one that halves two shapes with one line. For larger $m$ the excess is $\lfloor rn/k \rfloor - 2r$, it too grows with $n$, and whatever proves it will have to do more than count how large a colour class can be.

Why topology reaches one colour and not three #

Lovász’s argument, and Bárány’s simpler version of it, turn a colouring into a covering of a sphere. Each colour corresponds to an open set of directions; if there are too few colours, two antipodal directions land in the same set, and the two $k$-sets they pick out are disjoint and share a colour. The argument works because a single colour on a vertex is a single open set, and Borsuk–Ulam speaks about covers of the sphere by open sets.

With $m$ colours on every vertex, a vertex belongs to $m$ classes at once, and the covering it induces on the sphere is covered $m$ times. The Borsuk–Ulam theorem has no direct statement about multiple covers of that kind, and the cases of the conjecture that have been proved were not reached by any single lemma about the sphere that yields $qn - 2r$. Finding such a lemma, or some other reason, is essentially what the conjecture asks.

The contrast with the cuts that share a necklace is instructive. There, more thieves meant a stronger version of Borsuk–Ulam, for a larger symmetry group, and the answer came out with it. Here, more colours a vertex does not correspond to any known symmetry of the problem, and that is roughly why the one-colour case fell in 1978 while the general case, stated two years earlier, has not.

What the pictures cannot show #

The colourings drawn are one each, found by search. Many other colourings achieve the same number; the figures show that the number is achievable and — by the failed search one colour lower — that it is the least. They say nothing about how many optimal colourings there are or what they have in common.

The search is trusted because it is checked from both ends. Before it relies on stars and triangles being the only colour classes, it enumerates every family of pairs from five points and confirms each intersecting one sits inside a star or a triangle. After it finds a covering, it turns the covering into an actual colouring — each pair keeping only its first $m$ classes — and checks every pair of disjoint pairs for a shared colour. A proof by exhaustion, like the four colour theorem’s, is only as good as the claim that the list searched was the whole list, and that claim is the one tested here.

The six-point argument is the only proof drawn. The parity argument for nine colours fits in a paragraph; the other shaded cells of the table are settled by search, which is proof of a kind but not an explanation. Why every odd $m$ pays exactly $n/2 - 2$ extra colours for pairs is visible in the numbers and argued only for the smallest case.

Stahl’s upper-bound map is described, not drawn. That there is a disjointness-preserving map from the $k$-sets of $n$ points to the $(k-1)$-sets of $n - 2$ is a construction the text relies on; the figures verify only the colourings the search found.

Still open: the lower bound for every k #

Stahl’s formula is an upper bound for every $n$, $k$ and $m$, and a proved equality in the one-colour case, in the $m = k$ case, and in further families. In general it is an open problem, and the obstruction is the one described above: counting is too weak once $m$ is not a multiple of $k$, and the topological method that settles $m = 1$ has not been made to reach several colours at once.

There is one route that has worked before. Lovász’s theorem was proved topologically in 1978, and in 2004 Matoušek found a purely combinatorial proof of it, by running the labelling lemma about opposite edges on a cleverly chosen triangulation and reading the conclusion off as a statement about colourings. The topology was still there in spirit, but it had been compiled down into a finite parity count. A proof of Stahl’s lower bound might come the same way — a combinatorial lemma with an $m$-fold conclusion — or it might need a genuinely new topological statement first. Neither exists yet.

The table here says that for pairs the formula is right wherever it can be checked. A proof for $k = 3$ at all $n$ and $m$, or a single counterexample anywhere, would change what is known more than any amount of further searching on pairs.

Two answers that were each half the story #

The counting bound treats colour classes as interchangeable containers of limited size, and for the own-elements colouring it is exact. Lovász’s theorem treats the whole colouring as a map to a sphere and finds an obstruction no counting can see. Stahl’s formula says the truth for $m$ colours a vertex is a mixture: the counting answer for every complete block of $k$ colours, and a topological correction for the remainder $r$ — two colours lost per unit of remainder, exactly as in Lovász’s case.

Seen that way, the six-point parity argument is a small instance of the correction: one unit of remainder, two colours beyond the count, and a reason that fits in a paragraph because pairs are simple enough for it.

The formula is a claim that the two kinds of reasoning combine additively. For pairs, and in every case the search reaches, they do. Whether they always do is the question, and it is the same question the sphere answered for one colour and has not yet answered for more.