Shift graph
In graph theory, the shift graph Gn,k for n , k ∈ N , n > 2 k > 0 {\displaystyle n,k\in \mathbb {N} ,\ n>2k>0} is the graph whose vertices correspond to the ordered k {\displaystyle k} -tuples a = ( a 1 , a 2 , … , a k ) {\displaystyle a=(a_{1},a_{2},\dotsc ,a_{k})} with 1 ≤ a 1 < a 2 < ⋯ < a k ≤ n {\displaystyle 1\leq a_{1}<a_{2}<\cdots <a_{k}\leq n} and where two vertices a , b {\displaystyle a,b} are adjacent if and only if a i = b i + 1 {\displaystyle a_{i}=b_{i+1}} or a i + 1 = b i {\displaystyle a_{i+1}=b_{i}} for all 1 ≤ i ≤ k − 1 {\displaystyle 1\leq i\leq k-1} . Shift graphs are triangle-free, and for fixed k {\displaystyle k} their chromatic number tend to infinity with n {\displaystyle n} .