三角形のないグラフ

数学のグラフ理論の分野では、三角形のないグラフは、3 つの頂点が三角形の辺を形成しない無向グラフです。三角形のないグラフは、クリーク数が ≤ 2 のグラフ、内周が ≥ 4 のグラフ、誘導された 3 サイクル のないグラフ、または局所的に独立したグラフとして同等に定義できます。

トゥランの定理によれば、辺数が最大となるn頂点の三角形のないグラフは、二分の各辺の頂点数が可能な限り等しくなる 完全な二部グラフです。

三角形の発見または検出の問題は、グラフに三角形がないかどうかを判断する問題です。グラフに三角形が含まれている場合、グラフ内で三角形を形成する 3 つの頂点を出力するアルゴリズムが必要になることがよくあります。

エッジを持つグラフが三角形なしかどうかを、 がサブ多項式因数を隠している場合に、時間 でテストできます。ここでは高速行列乗算の指数 です。^[1]これから、三角形の検出は時間 で解決できることがわかります。別のアプローチは、 A ³のトレースを探すことです。ここで、A はグラフの隣接行列です。グラフが三角形なしの場合に限り、トレースはゼロになります。密なグラフの場合、この単純なアルゴリズムを使用する方が効率的です。このアルゴリズムでも行列乗算に依存しており、時間の計算量が まで削減されます。ここで、は頂点の数です。 ${\displaystyle m}$${\displaystyle {\tilde {O}}{\bigl (}m^{2\omega /(\omega +1)}{\bigr )}}$${\displaystyle {\tilde {O}}}$${\displaystyle \omega }$ ${\displaystyle \omega <2.372}$${\displaystyle O(m^{1.407})}$${\displaystyle O(n^{\omega })}$${\displaystyle n}$

たとえ時間を伴う行列乗算アルゴリズムが発見されたとしても、これらのアプローチから期待できる最良の時間境界はまたは です。細粒度の複雑性において、疎三角形仮説は、どのようなアルゴリズム手法が使用されても、任意の に対して という形式の時間境界は不可能であると主張する、証明されていない計算困難性の仮定です。この仮説と、対応する密三角形仮説( という形式の時間境界は不可能であるという仮説) は、組合せ最適化と計算幾何学における他のいくつかの計算問題に対する下限を暗示しています。^[2]${\displaystyle O(n^{2})}$${\displaystyle O(m^{4/3})}$${\displaystyle O(n^{2})}$${\displaystyle O(m^{4/3-\delta })}$${\displaystyle \delta >0}$${\displaystyle O(n^{\omega -\delta })}$

Imrich、Klavžar、Mulder (1999) が示したように、三角形のないグラフの認識は、複雑さの点で中央値グラフの認識と同等です。ただし、中央値グラフの認識の現在の最良のアルゴリズムでは、三角形の検出をサブルーチンとして使用しており、その逆は当てはまりません。

グラフの隣接行列を格納するオラクルにクエリを実行する場合の、問題の決定木複雑度またはクエリ複雑度は Θ( n 2 ) である。しかし、量子アルゴリズムの^場合、最もよく知られている下限値はΩ( n )であるが、最もよく知られているアルゴリズムはO ( n ^5/4 )である。^[3]

n頂点の三角形のないグラフにおける独立した頂点集合（ここで、床関数）は簡単に見つけることができます。つまり、少なくとも 個の隣接頂点を持つ頂点が存在するか（この場合、それらの隣接頂点は独立集合です）、すべての頂点の隣接頂点数が厳密に 個未満であるか（この場合、任意の最大独立集合は少なくとも個の頂点を持たなければなりません）のいずれかです。^[4]この境界はわずかに厳しくすることができます。つまり、すべての三角形のないグラフには独立した頂点集合が存在し、一部の三角形のないグラフでは、すべての独立集合に頂点があります。^[5]すべての独立集合が小さい三角形のないグラフを生成する 1 つの方法は、三角形のないプロセスです^[6]。三角形のないプロセスでは、三角形を完成しないランダムに選択された辺を繰り返し追加することで、最大の三角形のないグラフを生成します。このプロセスでは、高い確率で、独立数 のグラフが生成されます。同じ特性を持つ通常のグラフを見つけることも可能です。 ^[7]${\displaystyle \lfloor {\sqrt {n}}\rfloor }$${\displaystyle \lfloor \cdot \rfloor }$${\displaystyle \lfloor {\sqrt {n}}\rfloor }$${\displaystyle \lfloor {\sqrt {n}}\rfloor }$${\displaystyle \lfloor {\sqrt {n}}\rfloor }$${\displaystyle \Omega ({\sqrt {n\log n}})}$${\displaystyle O({\sqrt {n\log n}})}$${\displaystyle O({\sqrt {n\log n}})}$

これらの結果は、次の形式のラムゼー数R(3, t )の漸近境界を与えるものとして解釈することもできます。頂点上の完全グラフの辺が赤と青に色付けされている場合、赤いグラフには三角形が含まれているか、三角形がない場合は、青いグラフの同じサイズのクリークに対応するサイズtの独立セットが存在する必要があります。 ${\displaystyle \Theta ({\tfrac {t^{2}}{\log t}})}$${\displaystyle \Omega ({\tfrac {t^{2}}{\log t}})}$

三角形のないグラフに関する研究の多くは、グラフの色付けに焦点を当てています。すべての2部グラフ（つまり、2色に色付け可能なグラフ）は三角形がなく、グロッツシュの定理によれば、三角形のない平面グラフはすべて3色に色付けできます。^[8]ただし、非平面の三角形のないグラフでは、3色よりもはるかに多くの色が必要になる場合があります。

任意の高い彩色数を持つ三角形のないグラフの最初の構成は、 Tutte （ Blanche Descartes ^[9]として執筆）によるものです。この構成は、例えば単一の頂点を持つグラフから始まり、次のように帰納的に構成されました。 が頂点を持つとします。次に、頂点の集合を取り、サイズ のの各部分集合に対して、の互いに素なコピーを追加し、それを で結合します。鳩の巣原理から、 は彩色可能ではないことが帰納的にわかります。なぜなら、 k 色しか使用できない場合、集合の少なくとも 1 つは単色で彩色する必要があるからです。Mycielski (1955) は、別の三角形のないグラフから新しい三角形のないグラフを形成するための、現在ではMycielskianと呼ばれる構成を定義しました。グラフの彩色数がkの場合、その Mycielskian の彩色数はk  + 1 です。そのため、この構成を使用して、非平面の三角形のないグラフを彩色するには、任意の数の色が必要になる可能性があることを示すことができます。特に、ミシェルスキの構成を繰り返し適用して形成される11頂点グラフであるグロッチュグラフは、4色未満で着色することができない三角形のないグラフであり、この特性を持つ最小のグラフである。 ^{[10]ギンベル＆トーマスセン（2000）とニリ（2000）は、任意の}m辺三角形のないグラフを 着色するために必要な色の数は${\displaystyle G_{1}}$${\displaystyle G_{k+1}}$${\displaystyle G_{k}}$${\displaystyle G_{k}}$${\displaystyle n}$${\displaystyle Y}$${\displaystyle k(n-1)+1}$${\displaystyle X}$${\displaystyle Y}$${\displaystyle n}$${\displaystyle G_{k}}$${\displaystyle X}$${\displaystyle G_{k+1}}$${\displaystyle k}$${\displaystyle X}$

${\displaystyle O\left({\frac {m^{1/3}}{(\log m)^{2/3}}}\right)}$

そして、この境界に比例する彩色数を持つ三角形のないグラフが存在する。

三角形のないグラフにおける最小次数と色付けを関連付ける結果もいくつかあります。Andrásfai、Erdős、Sós (1974) は、各頂点が 2 n /5を超える隣接頂点を持つn頂点三角形のないグラフは、必ず二部グラフであることを証明しました。これは、このタイプの考えられる最良の結果です。5 閉路には 3 つの色が必要ですが、頂点ごとにちょうど 2 n /5 の隣接頂点を持つからです。この結果に触発されて、Erdős と Simonovits (1973) は、各頂点が少なくともn /3 の隣接頂点を持つn頂点三角形のないグラフは、3 色だけで色付けできると予想しました。しかし、Häggkvist (1981) は、Grötzsch グラフの各頂点を慎重に選ばれたサイズの独立集合に置き換える反例を見つけることで、この予想を反証しました。 Jin (1995) は、各頂点が 10 n /29 を超える隣接頂点を持つn頂点三角形なしグラフは、必ず 3 色彩色可能であることを示した。これは、このタイプの最良の結果である。なぜなら、Häggkvist のグラフは 4 色を必要とし、頂点ごとにちょうど 10 n /29 の隣接頂点を持つからである。最後に、Brandt と Thomassé (2006) は、各頂点がn /3を超える隣接頂点を持つn頂点三角形なしグラフは、必ず 4 色彩色可能であることを証明した。Hajnal ^{[11] は、}任意の大きな彩色数と、 ε > 0 の任意の場合の 最小次数 (1/3 − ε) nを持つ三角形なしグラフの例を見つけたため、このタイプの追加の結果は不可能である。

• アンドラーシュファイグラフ、直径2の三角形のない循環グラフの族
• ヘンソングラフ、すべての有限三角形なしグラフを誘導部分グラフとして含む無限三角形なしグラフ
• シフトグラフ、任意の高い彩色数を持つ三角形のないグラフの族
• クネザーグラフは 三角形を持たず、彩色数を持つ。${\displaystyle KG_{3k-1,k}}$${\displaystyle k+1}$
• 単色三角形問題、与えられたグラフの辺を2つの三角形のないグラフに分割する問題
• ルザ・セメレディ問題、すべての辺がちょうど1つの三角形に属するグラフ

• 「Graphclass: triangle-free」、グラフクラスとその包含に関する情報システム