番号

グラフ理論の数学分野では、グラフのチュー数は彩色指数の一種であり、 Alon ら (2002)によって定義され、この数を定義するために使用される平方フリーワードを研究した数学者Axel Thueにちなんで名付けられました。

アロンらは、グラフの非反復彩色を、グラフのエッジに色を割り当てることで、パスの前半のエッジの色と後半のエッジの色が同じシーケンスを形成するような偶数長の単純パスがグラフ内に存在しないように定義している。グラフのチュー数は、非反復彩色に必要な最小色の数である。^{[ 1 ]}

頂点彩色やグラフ上のより一般的なウォークを含むこの概念のバリエーションは、複数の著者によって研究されてきた。^{[ 2 ]}

五角形、つまりサイクルを考えてみましょう。${\displaystyle C_{5}}$5つの頂点からなる図形。辺を2色で着色すると、隣接する2つの辺が同じ色になる。${\displaystyle x}$2つの辺によって形成される経路は、繰り返し同じ色のシーケンスを持つ。${\displaystyle xx}$辺が3色で着色されている場合、3色のうち1色は1回だけ使用され、残りの2色で形成される4辺のパスは、2つの連続する辺を持つか、または繰り返し色のシーケンスを形成します。${\displaystyle xyxy}$しかし、4色を使用し、隣接しない2つの辺で1色を繰り返すことで、すべての繰り返しを回避できます。したがって、Thue数は${\displaystyle C_{5}}$4です。^{[ 1 ]}

アロンらはロヴァースの局所補題を用いて、任意のグラフのチュー数は最大次数に関してせいぜい2次であることを証明し、いくつかのグラフではこの2次依存性が必要であることを示す例を提示している。さらに、4つ以上の頂点を持つパスのチュー数はちょうど3であり、任意のサイクルのチュー数はせいぜい4であり、ピーターセングラフのチュー数はちょうど5であることを示している。^{[ 1 ]}

サイクル${\displaystyle C_{5}}$、 ${\displaystyle C_{7}}$、 ${\displaystyle C_{9}}$、 ${\displaystyle C_{10}}$、 ${\displaystyle C_{14}}$、 そして ${\displaystyle C_{17}}$チュー番号は4である。^{[ 1 ]}アロンらの予想を解決し、カーリーは他のすべてのサイクルがチュー番号3であることを示した。^{[ 3 ]}

彩色に繰り返しパスがあるかどうかをテストすることはNPに属するので、彩色が繰り返しでないかどうかをテストすることはco-NPに属し、Maninはそれがco-NP完全であることを示した。そのような彩色を見つける問題は、$\displaystyle \Sigma _{2}^{P}}$多項式階層において、そして再びマニンは、このレベルではそれが完全であることを示した。^{[ 4 ]}

• Alon, Noga ; Grytczuk, Jaroslaw; Hałuszczak, Mariusz; Riordan, Oliver (2002). "グラフの非反復彩色" (PDF) . Random Structures & Algorithms . 21 ( 3– 4): 336– 346. doi : 10.1002/rsa.10057 . MR 1945373 . S2CID 5724512 .  
• バラート、ヤーノス。ヴァルジュ、PP (2008)。「グラフの四角形のないエッジの色付けについて」。アルスコンビナトリア。87 : 377–383。MR 2414029。​​ 
• Barát, János; Wood, David (2005). "非反復グラフ彩色に関する注記". Electronic Journal of Combinatorics . 15 (1). R99. arXiv : math.CO/0509608 . Bibcode : 2005math......9608B . MR 2426162 . 
• ブレシャール、ボシュチャン。クラヴジャール、サンディ (2004)。 「グラフの四角い色付け」。アルス・コンビン。70 : 3–13 . MR 2023057。 
• Currie, James D. (2002). " n ≥ 18の場合、長さnの 3 進円形平方フリー語が存在する"   . Electronic Journal of Combinatorics . 9 (1). N10. doi : 10.37236/1671 . MR 1936865 . 
• Kündgen, André; Pelsmajer, Michael J. (2008). "木幅が制限されたグラフの非反復彩色". Discrete Mathematics . 308 (19): 4473–4478 . doi : 10.1016/j.disc.2007.08.043 . MR 2433774 . 
• Manin, Fedor (2007). "グラフの非反復エッジ彩色の複雑性". arXiv : 0709.4497 [ cs.CC ].
• シェーファー、マーカス；ウマンス、クリストファー（2005）。「多項式時間階層における完全性：概要」。

• Grytczuk, Jarosław (2007). "グラフの非反復彩色—概説" . International Journal of Mathematics and Mathematical Sciences . 2007 . Art. ID 74639. doi : 10.1155/2007/74639 . MR 2272338 . 

• ウィキメディア・コモンズにあるThue番号に関連するメディア