# Lower bound on chromatic number of a family of graphs

Let $G_n$ be a graph whose vertices are the 2 element tuples of {$1,2,3...n$}. Two vertices ($i,j$) and ($k,ℓ$) are adjacent if and only if $i<j, k<ℓ$ and $j=k$

I am trying to show that the chromatic number of $G_n$ is bounded below by $\lceil \log_2 n \rceil$

Any help which can be given on this problem would be greatly appreciated. Or even just a general approach for establishing lower bounds on chromatic numbers would be very helpful as the only general lower bounds have seen up to this point (the clique number and independent number bounds) have both had very trivial proofs.

-

If $G$ is a directed graph, the line graph $L(G)$ is the graph with vertex set $E(G)$ and edge set $$E(L(G)) = \{e, f \in E(G) \, : \, \text{the head of e is the tail of f or vice-versa} \}.$$

Hint: Show that your graph $G$ is the line graph of some directed graph $H$. Then find a way of relating proper colorings of $G$ to proper colorings of $H$.

-
This is an interesting approach which I had not even considered, I may try and rework the proof using this method –  Elliot Feb 6 '13 at 0:37

My guess is that this is a well known example (to those that know it well).

I thought quite a lot about it. I found a very satisfying solution, but don't see a systematic approach that would be useful for other problems (this may be my lack of experience in computing chromatic numbers).

You can re-formulate the problem in the way that is being suggested as @Andrew Uzzell: take edges on $\lbrace 1,\ldots,n\rbrace$ connecting pairs $(i,j)$ with $i < j$. You're then looking for an edge colouring of this graph, so that at each vertex the set of incoming colours is disjoint from the set of outgoing colours. (If not then it fails to be an edge colouring of the line graph).

Progress at this point relied on a flash of inspiration: if you try to colour using $k$ colours, where $2^k < n$, then there are two vertices that have the same `incoming colour set' (pigeonhole). You can then show this yields a contradiction.

It turns out that the lower bound is sharp: this is exactly the chromatic number of this graph (as seen by a rather beautiful colouring that I won't describe here). I suspect this is a well known example because it has very large chromatic number ($\log_2n$), while the graph itself doesn't even contain any $K_3$'s. Update: I asked a combinatorial colleague, who hadn't met this example before.

-
Yes this is a well known example. After doing some research a colleague and I were able to find a really clever and short proof which does not require any computation or even finding an actual coloring. Although I like the approach you are suggesting and it may serve as a good method for similar problems. The proof I found goes like this: Let $V_k$ = the set of vertices with $i<k$ for $1 \le i \le k-1$ –  Elliot Feb 6 '13 at 0:43
Then $V_k$ for $2\le k \le n$ forms a partition of the vertices. Fix $c$ as a proper coloring with colors from $X$ Note that the vertex $\{i,j\}$ in the set $V_i$ will be adjacent to each vertex in the set $V_j$ so that $c(V_i) \neq c(V_j)$ for $i \neq j$ so that at least one vertex in each partition set must be colored differently. Then $c(V_2), c(V_3)...C(V_n)$ forms a set of $n-1$ nonempty subsets of $X$ and are pairwise different. Through the empty set into this list as $V_0$ so that we have $n$ subsets of $X$. Since this is a subset of the Power set of $X$ we get $2^{|X|} \ge n$ –  Elliot Feb 6 '13 at 1:00