Shift graph
In graph theory, the shift graph  for  is the graph whose vertices correspond to the ordered -tuples  with  and where two vertices  are adjacent if and only if  or  for all . Shift graphs are triangle-free, and for fixed  their chromatic number tend to infinity with . It is natural to enhance the shift graph  with the orientation  if  for all . Let  be the resulting directed shift graph.
Note that  is the directed line graph of the transitive tournament corresponding to the identity permutation. Moreover,  is the directed line graph of  for all .

Further facts about shift graphs
Odd cycles of  have length at least , in particular  is triangle free.
For fixed  the asymptotic behaviour of the chromatic number of  is given by  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  also play a central role in the context of order dimension of interval orders.

Representation of shift graphs

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

References

Graph coloring