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.
 A: 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.
A: If $G$ is a directed graph, the line digraph $L(G)$ is the digraph with vertex set $E(G)$ and edge set
$$E(L(G)) = \{ef \in E(G) \, : \, \text{the head of $e$ is the tail of $f$} \}.$$
Hint: Show that your graph $G$ is the line digraph of some directed graph $H$.  Then find a way of relating proper colorings of $G$ to proper colorings of $H$.
