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 .[1] 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

edit
  • 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.[1]
  • Further connections to the chromatic theory of graphs and digraphs have been established in.[2]
  • Shift graphs, in particular   also play a central role in the context of order dimension of interval orders.[3]

Representation of shift graphs

edit
 
The line representation of a shift graph.

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.

Note: This seems false, since   and   will be non-adjacent. Someone should check this.

References

edit
  1. ^ a b Erdős, P.; Hajnal, A. (1968), "On chromatic number of infinite graphs", Theory of Graphs (Proc. Colloq., Tihany, 1966) (PDF), New York: Academic Press, pp. 83–98, MR 0263693
  2. ^ Simonyi, Gábor; Tardos, Gábor (2011). "On directed local chromatic number, shift graphs, and Borsuk-like graphs". Journal of Graph Theory. 66: 65–82. arXiv:0906.2897. doi:10.1002/jgt.20494. S2CID 14215886.
  3. ^ Füredi, Z.; Hajnal, P.; Rödl, V.; Trotter, W. T. (1991). "Interval Orders and Shift Graphs". Sets, Graphs and Numbers. 60. Proc. Colloq. Math. Soc. Janos Bolyai: 297–313.