シフトグラフ

グラフ理論では、シフトグラフG _n、kは${\displaystyle n,k\in \mathbb {N} ,\ n>2k>0}$は、頂点が順序付けられたものに対応するグラフです。${\displaystyle k}$-タプル${\displaystyle a=(a_{1},a_{2},\dotsc ,a_{k})}$と${\displaystyle 1\leq a_{1}<a_{2}<\cdots <a_{k}\leq n}$そして2つの頂点${\displaystyle a,b}$隣接しているのは、${\displaystyle a_{i}=b_{i+1}}$または${\displaystyle a_{i+1}=b_{i}}$すべての人々のために${\displaystyle 1\leq i\leq k-1}$シフトグラフは三角形を含まず、固定の場合${\displaystyle k}$それらの彩色数は無限大に近づく${\displaystyle n}$[ ^{1 ]}シフトグラフを強化することは自然なことで^ある${\displaystyle G_{n,k}}$方向${\displaystyle a\to b}$もし${\displaystyle a_{i+1}=b_{i}}$すべての人々のために${\displaystyle 1\leq i\leq k-1}$。 させて${\displaystyle {\overrightarrow {G}}_{n,k}}$結果として得られる有向シフトグラフを とする。${\displaystyle {\overrightarrow {G}}_{n,2}}$は恒等置換に対応する推移的トーナメントの有向線グラフである。さらに、${\displaystyle {\overrightarrow {G}}_{n,k+1}}$は有向線グラフです${\displaystyle {\overrightarrow {G}}_{n,k}}$すべての人々のために${\displaystyle k\geq 2}$。

• 奇妙な周期${\displaystyle G_{n,k}}$長さが少なくとも${\displaystyle 2k+1}$、 特に${\displaystyle G_{n,2}}$三角形を含まない。
• 固定の場合${\displaystyle k\geq 2}$彩色数の漸近挙動${\displaystyle G_{n,k}}$は${\displaystyle \chi (G_{n,k})=(1+o(1))\log \log \cdots \log n}$対数関数が反復される${\displaystyle {\displaystyle k-1}}$回。^{[ 1 ]}
• グラフと有向グラフの彩色理論とのさらなる関連性は、^{[ 2 ]で確立されている。}
• シフトグラフ、特に${\displaystyle G_{n,3}}$また、区間順序の順序次元の文脈において中心的な役割を果たす。^{[ 3 ]}

シフトグラフ${\displaystyle G_{n,2}}$完全なグラフの線グラフです${\displaystyle K_{n}}$次のように考えてください。${\displaystyle 1}$に${\displaystyle n}$線上に並べ、すべての数字のペアの間に線分を描きます。すべての線分は、${\displaystyle 2}$-その最初の数と最後の数のタプルは、まさに頂点です${\displaystyle G_{n,2}}$2つの線分は、一方の線分の始点が他方の線分の終点である場合に接続されている。