About: Shift graph
In graph theory, the shift graph Gn,k 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 .
