Shift graph

In graph theory, the shift graph Gn,k for

n , k ∈

n > 2 k > 0

{\displaystyle n,k\in \mathbb {N} ,\ n>2k>0}

is the graph whose vertices correspond to the ordered

and where two vertices

are adjacent if and only if

Shift graphs are triangle-free, and for fixed

their chromatic number tend to infinity with

[1] It is natural to enhance the shift graph

with the orientation

be the resulting directed shift graph.

Note that

is the directed line graph of the transitive tournament corresponding to the identity permutation.

is the directed line graph of

The shift graph

is the line-graph of the complete graph

in the following way: Consider the numbers from

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.