Shift graph

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