Shift Graph

In graph theory, the shift graph for $n,k \in \mathbb,\ n > 2k > 0$ is the graph whose vertices correspond to the ordered $k$-tuples $a = (a_1, a_2, \dotsc, a_k)$ with $1 \leq a_1 < a_2 < \cdots < a_k \leq n$ and where two vertices $a, b$ are adjacent if and only if $a_i = b_$ or $a_ = b_i$ for all $1 \leq i \leq k-1$. Shift graphs are triangle-free, and for fixed $k$ their chromatic number tend to infinity with $n$. It is natural to enhance the shift graph $G_$ with the orientation $a \to b$ if $a_=b_i$ for all $1\leq i\leq k-1$. Let $\overrightarrow_$ be the resulting directed shift graph.
Note that $\overrightarrow_$ is the directed line graph of the transitive tournament corresponding to the identity permutation. Moreover, $\overrightarrow_$ is the directed line graph of $\overrightarrow_$ for all $k \geq 2$.

Further facts about shift graphs

*Odd cycles of $G_$ have length at least $2k+1$, in particular $G_$ is triangle free.
*For fixed $k \geq 2$ the asymptotic behaviour of the chromatic number of $G_$ is given by $\chi(G_) = (1 + o(1))\log\log\cdots\log n$ where the logarithm function is iterated $$ times.
*Further connections to the chromatic theory of graphs and digraphs have been established in.
*Shift graphs, in particular $G_$ also play a central role in the context of order dimension of interval orders.

Representation of shift graphs

The shift graph $G_$ is the line-graph of the complete graph $K_n$ in the following way: Consider the numbers from $1$ to $n$ ordered on the line and draw line segments between every pair of numbers. Every line segment corresponds to the $2$-tuple of its first and last number which are exactly the vertices of $G_$. Two such segments are connected if the starting point of one line segment is the end point of the other.

References

{{DEFAULTSORT:Shift Graphs
Graph coloring