木番号

5サイクルの Thue 数は4 です。

グラフ理論の数学の分野において、グラフのThue 数は彩色指数のバリエーションであり、 Alon ら (2002)によって定義され、この数を定義するために使用される平方自由語を研究した数学者Axel Thueにちなんで命名されました。

アロンらは、グラフの非反復的な彩色を、グラフの辺に色を割り当てることと定義し、グラフの前半の辺の色と後半の辺の色が同じ順序となるような、グラフ内に長さが偶数である単純な経路が存在しないものとしている。グラフのThue数は、非反復的な彩色に必要な最小の色数である。^{[ 1 ]}

この概念のバリエーションとして、頂点彩色やグラフ上のより一般的な歩行などが、多くの研究者によって研究されてきました。^{[ 2 ]}

例

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

結果

アロンらは、ロヴァースの局所補題を用いて、任意のグラフのThue数は最大次数において最大で2乗であることを証明した。彼らは、いくつかのグラフではこの2乗依存性が必須であることを示す例を示した。さらに、4頂点以上のパスのThue数はちょうど3であること、任意の閉路のThue数は最大で4であること、そしてピーターセングラフのThue数はちょうど5であることを示している。^{[ 1 ]}

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

計算の複雑さ

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

注記

1. アロンら。 (2002)。
2. Barát & Varjú (2008) ;バラートとウッド (2005) ;ブレザールとクラヴザール (2004) ;クンゲン＆ペルスマイヤー (2008)。
3. カリー（2002年）。
4. マニン（2007） .

参考文献

• 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). 「木幅が制限されたグラフの非反復彩色」.離散数学. 308 (19): 4473– 4478. doi : 10.1016/j.disc.2007.08.043 . MR  2433774 .
• マニン、フェドール (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数関連メディア