二クリークフリーグラフ

数学の一分野であるグラフ理論において、 $t$ -双クリークフリー グラフとは、サブグラフとして $K t, t$ ( $2t$ 個の頂点を持つ完全二部グラフ)を持たないグラフのことである。グラフ族が双クリークフリーであるとは、族内のグラフがすべて $t -双クリークフリーとなるような数$ $t$ が存在する場合である。双クリークフリーグラフ族は、最も一般的なタイプのスパースグラフ族の 1 つを形成する。これらは離散幾何学における接続問題で発生し、パラメータ化された複雑性でも使用されている。

プロパティ

希薄性

Kővári–Sós–Turán の定理によれば、すべての $n$ 頂点 $t$ 二部クリークフリーグラフは $O (n 2 - 1/ t)の辺を持ち、これは$ 稠密なグラフが持つ辺よりも大幅に少ない。^[1]逆に、グラフ族が禁制サブグラフによって定義されるか、サブグラフを取る操作に関して閉じられており、任意の大きさの稠密グラフを含まない場合、何らかの $tに対して$ $t 二$ 部クリークフリーでなければならない。そうでなければ、大きな稠密な完全二部グラフが含まれることになる。

下限として、エルデシュ、ハジナル、ムーン（1964）は、 $t-$ 二分枝のない極大二部グラフ（ $t-$ 二分枝を作らずに辺を追加することができないグラフ）はすべて、少なくとも $（ t -1）（ n + m - t + 1）$ の辺を持つと予想した。ここで $n$ と $m$ は、二分グラフの各辺の頂点の数である。^[2]

他の種類のスパースグラフファミリーとの関係

$退化度d$ のグラフは必然的に $(d + 1)$ 双クリークフリーである。さらに、グラフのどのどこにも稠密でない族も双クリークフリーである。より一般的には、族内のどのグラフの 1 浅いマイナーでもない $n頂点グラフが存在する場合、族は$ $n$ 双クリークフリーでなければならない。なぜなら、すべての $n頂点グラフは$ $K n, n$ の 1 浅いマイナーだからである。このように、双クリークフリーのグラフ族は、最も一般的な 2 つの疎グラフのクラスを統合する。^[3]

アプリケーション

離散幾何学

離散幾何学では、多くの種類の接続グラフは必然的に双クリークフリーである。簡単な例として、ユークリッド平面上の有限の点と線の集合間の接続グラフは、必然的に $K 2,2$ サブグラフを持たない。^[4]

パラメータ化された複雑さ

双クリークフリーグラフは、パラメータ化された複雑性において、入力パラメータ値が適度に小さいスパースグラフに対して効率的なアルゴリズムを開発するために使用されてきた。特に、 $t$ 双クリークフリーグラフ上でサイズ $kの$ 支配集合を見つけることは、 $k$ $+$ $t$ でパラメータ化された場合には固定パラメータで処理可能であるが、 $k$ のみをパラメータとして使用した場合には不可能であるという強い証拠がある。同様の結果は、支配集合問題の多くのバリエーションに当てはまる。^[3]また、同じパラメータ化で、支配特性を維持しながら、頂点の挿入と削除の連鎖によって、最大で $k$ のサイズの支配集合を別の支配集合に変換できるかどうかをテストすることもできる。^[5]

参考文献

^ クシュヴァーリ、T.; T. ソス、V . ; Turán、P. (1954)、「K. Zarankiewicz の問題について」(PDF)、Colloquium Math。、3 : 50–57、MR 0065617この研究は、バイクリークのない二部グラフの辺の数に関するものですが、確率的方法の標準的な応用により、同じ制限が任意のグラフにも適用されます。
^ Erdős, P. ; Hajnal, A. ; Moon, JW (1964)、「グラフ理論の問題」(PDF)、The American Mathematical Monthly、71 : 1107–1110、doi :10.2307/2311408、MR 0170339。
^ ab Telle, Jan Arne; Villanger, Yngve (2012)、「Biclique-free グラフにおける支配のための FPT アルゴリズム」、Epstein, Leah、Ferragina, Paolo (編)、Algorithms – ESA 2012: 20th Annual European Symposium、スロベニア、リュブリャナ、2012 年 9 月 10 ～ 12 日、Proceedings、Lecture Notes in Computer Science、vol. 7501、Springer、pp. 802 ～ 812、doi :10.1007/978-3-642-33090-2_69。
^ Kaplan, Haim; Matoušek, Jiří ; Sharir, Micha (2012)、「Guth–Katz 多項式分割法による離散幾何学における古典定理の簡単な証明」、Discrete and Computational Geometry、48 (3): 499–517、arXiv : 1102.5391、doi :10.1007/s00454-012-9443-3、MR 2957631特に補題3.1と補題に続く注釈を参照。
^ Lokshtanov, Daniel; Mouawad, Amer E.; Panolan, Fahad; Ramanujan, MS; Saurabh, Saket (2015)、「Reconfiguration on sparse graphs」、Dehne, Frank; Sack, Jörg-Rüdiger ; Stege, Ulrike (編)、Algorithms and Data Structures: 14th International Symposium、WADS 2015、Victoria, BC, Canada、2015 年 8 月 5 ～ 7 日、議事録(PDF)、Lecture Notes in Computer Science、vol. 9214、Springer、pp. 506–517、arXiv : 1502.04803、doi :10.1007/978-3-319-21840-3_42、2017-11-13にオリジナル（PDF）からアーカイブ、 2017-05-24に取得。

[1] クシュヴァーリ、T.; T. ソス、V . ; Turán、P. (1954)、「K. Zarankiewicz の問題について」(PDF)、Colloquium Math。、3 : 50–57、MR 0065617この研究は、バイクリークのない二部グラフの辺の数に関するものですが、確率的方法の標準的な応用により、同じ制限が任意のグラフにも適用されます。

[2] Erdős, P. ; Hajnal, A. ; Moon, JW (1964)、「グラフ理論の問題」(PDF)、The American Mathematical Monthly、71 : 1107–1110、doi :10.2307/2311408、MR 0170339。

[tv12-3] Telle, Jan Arne; Villanger, Yngve (2012)、「Biclique-free グラフにおける支配のための FPT アルゴリズム」、Epstein, Leah、Ferragina, Paolo (編)、Algorithms – ESA 2012: 20th Annual European Symposium、スロベニア、リュブリャナ、2012 年 9 月 10 ～ 12 日、Proceedings、Lecture Notes in Computer Science、vol. 7501、Springer、pp. 802 ～ 812、doi :10.1007/978-3-642-33090-2_69。

[4] Kaplan, Haim; Matoušek, Jiří ; Sharir, Micha (2012)、「Guth–Katz 多項式分割法による離散幾何学における古典定理の簡単な証明」、Discrete and Computational Geometry、48 (3): 499–517、arXiv : 1102.5391、doi :10.1007/s00454-012-9443-3、MR 2957631特に補題3.1と補題に続く注釈を参照。

[5] Lokshtanov, Daniel; Mouawad, Amer E.; Panolan, Fahad; Ramanujan, MS; Saurabh, Saket (2015)、「Reconfiguration on sparse graphs」、Dehne, Frank; Sack, Jörg-Rüdiger ; Stege, Ulrike (編)、Algorithms and Data Structures: 14th International Symposium、WADS 2015、Victoria, BC, Canada、2015 年 8 月 5 ～ 7 日、議事録(PDF)、Lecture Notes in Computer Science、vol. 9214、Springer、pp. 506–517、arXiv : 1502.04803、doi :10.1007/978-3-319-21840-3_42、2017-11-13にオリジナル（PDF）からアーカイブ、 2017-05-24に取得。