In graph theory, the '''shift graph''' {{math|''G''<sub>''n'',''k''</sub>}} for <math> n,k \in \mathbb{N},\ n > 2k > 0 </math> is the graph whose vertices correspond to the ordered <math>k</math>-tuples <math> a = (a_1, a_2, \dotsc, a_k)</math> with <math>1 \leq a_1 < a_2 < \cdots < a_k \leq n </math> and where two vertices <math> a, b </math> are adjacent if and only if <math>a_i = b_{i+1}</math> or <math>a_{i+1} = b_i</math> for all <math> 1 \leq i \leq k-1 </math>. Shift graphs are triangle-free, and for fixed <math>k</math> their chromatic number tend to infinity with <math>n</math>.<ref name="infinite_graphs">{{citation | last1 = Erdős | first1 = P. | author1-link = Paul Erdős | last2 = Hajnal | first2 = A. | author2-link = András Hajnal | contribution = On chromatic number of infinite graphs | location = New York | mr = 0263693 | pages = 83–98 | publisher = Academic Press | title = Theory of Graphs (Proc. Colloq., Tihany, 1966) | url = http://www.renyi.hu/~p_erdos/1968-04.pdf | year = 1968}}</ref> It is natural to enhance the shift graph <math>G_{n,k}</math> with the orientation <math>a \to b</math> if <math>a_{i+1}=b_i</math> for all <math>1\leq i\leq k-1</math>. Let <math>\overrightarrow{G}_{n,k}</math> be the resulting directed shift graph. Note that <math>\overrightarrow{G}_{n,2}</math> is the directed line graph of the transitive tournament corresponding to the identity permutation. Moreover, <math>\overrightarrow{G}_{n,k+1}</math> is the directed line graph of <math>\overrightarrow{G}_{n,k}</math> for all <math>k \geq 2</math>.
==Further facts about shift graphs== *Odd cycles of <math>G_{n,k}</math> have length at least <math>2k+1</math>, in particular <math>G_{n,2}</math> is triangle free. *For fixed <math>k \geq 2</math> the asymptotic behaviour of the chromatic number of <math>G_{n,k}</math> is given by <math>\chi(G_{n,k}) = (1 + o(1))\log\log\cdots\log n </math> where the logarithm function is iterated <math>{\displaystyle k-1}</math> times.<ref name="infinite_graphs" /> *Further connections to the chromatic theory of graphs and digraphs have been established in.<ref>{{cite journal | last1=Simonyi | first1=Gábor | last2=Tardos | first2=Gábor | authorlink2=Gábor Tardos | year=2011 | title=On directed local chromatic number, shift graphs, and Borsuk-like graphs | journal=Journal of Graph Theory | volume = 66 | pages=65–82 | doi=10.1002/jgt.20494 | arxiv=0906.2897| s2cid=14215886 }}</ref> *Shift graphs, in particular <math>G_{n,3}</math> also play a central role in the context of order dimension of interval orders.<ref name="interval_orders">{{cite journal | last1=Füredi | first1=Z. | authorlink1=Zoltán Füredi | last2=Hajnal | first2=P. | last3=Rödl | first3=V. | authorlink3=Vojtěch Rödl | last4=Trotter | first4=W. T. | authorlink4=William T. Trotter | date=1991 | title=Interval Orders and Shift Graphs | journal=Sets, Graphs and Numbers | publisher=Proc. Colloq. Math. Soc. Janos Bolyai | volume=60 | pages=297–313}}</ref>
==Representation of shift graphs==
thumb|The line representation of a shift graph. The shift graph <math>G_{n,2}</math> is the line-graph of the complete graph <math>K_n</math> in the following way: Consider the numbers from <math>1</math> to <math>n</math> ordered on the line and draw line segments between every pair of numbers. Every line segment corresponds to the <math>2</math>-tuple of its first and last number which are exactly the vertices of <math>G_{n,2}</math>. Two such segments are connected if the starting point of one line segment is the end point of the other.
==References== {{Reflist}}
{{DEFAULTSORT:Shift Graphs}} Category:Graph coloring