Determine the Chromatic Number of the Complement of the Line Graph of the Complete Graph

Question

The question I have is essentially what is written in the title:

Determine the chromatic number of the complement of the line graph of $K_n$.

For some context, I am trying to solve this problem to prepare for a graph theory exam and have been unable to make much, if any, progress. I also know that this problem should have a solution using only basic graph theory. I know that what falls under "basic graph theory" is relative, but specifically, I mean any knowledge that could be obtained in a one-semester introductory course in graph theory at an upper-level undergraduate or early graduate level. Any help would be greatly appreciated.

Answer 1

It helps to restate the problem in a way that doesn't involve the words "complement of the line graph of the complete graph", because who knows what that graph looks like.

If we're coloring the vertices of the complement of the line graph of the complete graph, then that's the same thing as coloring the vertices of the line graph - taking the complement doesn't change the vertex set. (It does change what we want from the coloring, but we'll get to that later.) The vertices of the line graph of $K_n$ are the edges of $K_n$. So, we want an edge-coloring of $K_n$ that has some properties.

Which properties? Well, we want a proper coloring of the complement of the line graph of the complete graph. That means that two vertices of the line graph that are not adjacent should get different colors. Vertices of the line graph are adjacent if and only if the corresponding edges of $K_n$ share a vertex. So we want to color such that edges that don't share vertices get different colors.

This gives us the following restatement of the problem:

Color the edges of $K_n$ with as few colors as possible, such that any two edges with no vertices in common receive different colors.

(At this point, I encourage you to stop and think about the problem some more, now that you have a version of the question that's easier to think about.)

---

Consider a single color class in such a coloring: the set of all edges of some color. This forms a subgraph of $K_n$ in which any two edges share an endpoint, and there are only two possibilities for such a subgraph:

• A star - take any number of edges out of the same vertex.
• A triangle - take any $3$-cycle.

In particular, we just need one color when $n=3$. For $n>3$, there is a coloring with $n-2$ colors: take $n-3$ stars centered at $n-3$ different vertices, and a triangle through the remaining $3$ vertices.

To show that $n-2$ is the best possible, induct on $n$. When $n=3$, using only one color is optimal, so the base case holds. When $n>3$, we consider two cases:

1. Every color class is a triangle. In that case, we need at least $\binom n2 / 3 = \frac{n(n-1)}{6}$ colors, and $\frac{n(n-1)}{6} \ge n-2$ for $n\ge 4$.
2. At least one color class is a star centered at some vertex $v$. In that case, recolor to put all edges out of $v$ in that color class; this still satisfies all of our conditions, and uses the same number of colors. But now, the edges of $K_n - v$ can't use that color, and they need $n-3$ colors by the inductive hypothesis; therefore, we need at least $n-2$ colors total.

In both cases, we use at least $n-2$ colors, and we also know of a coloring that uses exactly that many, so this proves that $\chi(\overline{L(K_n)}) = n-2$.