シャイネルマンの予想

数学において、現在では定理となっているシャイネルマンの予想は、すべての平面グラフは平面内の線分の集合の交差グラフであると述べている。この予想は、すべての平面グラフは平面内の単純曲線の集合の交差グラフとして表すことができるという以前の結果 (Ehrlich、Even、Tarjan 1976) を受けて、ERシャイネルマンが博士論文 (1984) で定式化した。これはジェレミー・シャロパンとダニエル・ゴンサルベス (2009) によって証明された。

たとえば、下の左側に示すグラフG は、下の右側に示す線分の集合の交差グラフとして表すことができます。ここで、Gの頂点は直線の線分で表され、Gの辺は交差点で表されます。

 

Scheinerman はまた、3 方向のみの線分で 3色グラフを表すのに十分であると推測し、West (1991) は同様にすべての平面グラフを 4 方向で表すことができると推測しました。グラフがk方向のみの線分で表され、2 つの線分が同じ線に属さない場合、グラフは各方向に 1 色ずつ、 k色で色付けできます。したがって、すべての平面グラフをこのように 4 方向のみで表すことができる場合、4 色定理が成り立ちます。Gonçalves (2020) は、一部の平面グラフはその方法では表すことができないことを証明しました。

Hartman、Newman & Ziv (1991) および de Fraysseix、Ossona de Mendez & Pach (1991) は、あらゆる二部平面グラフは水平および垂直の線分の交差グラフとして表せることを証明した。この結果については、Czyzowicz、Kranakis & Urrutia (1998) も参照。De Castro ら (2002) は、あらゆる三角形のない平面グラフは、3 方向のみを持つ線分の交差グラフとして表せることを証明した。この結果は、三角形のない平面グラフは 3 色で色付けできるというGrötzsch の定理(Grötzsch 1959) を意味している。de Fraysseix および Ossona de Mendez (2005) は、平面グラフG を4 色に色付けでき、分離サイクルが 4 色すべてを使用しない場合、G は線分の交差グラフとして表現できることを証明した。

Chalopin、Gonçalves & Ochem (2007) は、平面グラフが 1-STRING に属することを証明した。1-STRINGとは、平面上の単純曲線の交差グラフのクラスであり、曲線同士は 1 組あたり最大で 1 つの交差点で交差する。このクラスは、Scheinerman の予想に現れる線分の交差グラフと、Ehrlich らの結果からの制限のない単純曲線の交差グラフの中間である。これは、曲線が接線で交差することを許した場合に同じ結果を示す円充填定理の一般化と見ることもできる。Chalopin & Gonçalves (2009) による予想の証明は、この結果の改良に基づいていた。

• De Castro, N.; Cobos, FJ; Dana, JC; Márquez, A. (2002)、「三角形のない平面グラフをセグメント交差グラフとして」(PDF)、Journal of Graph Algorithms and Applications、6 (1): 7–26、doi : 10.7155/jgaa.00043、MR  1898201。
• Chalopin, J.; Gonçalves, D. (2009)、「すべての平面グラフは平面内の線分の交差グラフである」(PDF)、ACM 計算理論シンポジウム。
• Chalopin, J.; Gonçalves, D.; Ochem, P. (2007)、「平面グラフは 1-STRING である」、第 18 回 ACM-SIAM 離散アルゴリズムシンポジウムの議事録、ACM および SIAM、pp. 609–617。
• Czyzowicz, J.; Kranakis, E.; Urrutia, J. (1998)、「二部平面グラフを直交直線セグメントの接触グラフとして表現することの簡単な証明」、Information Processing Letters、66 (3): 125–126、doi :10.1016/S0020-0190(98)00046-5。
• de Fraysseix, H.; Ossona de Mendez, P. (2005)、「接触表現と交差表現」、Pach, J. (編)、Graph Drawing、第 12 回国際シンポジウム、GD 2004、Lecture Notes in Computer Science、vol. 3383、Springer-Verlag、pp. 217–227。
• de Fraysseix, H.; Ossona de Mendez, P .; Pach, J. (1991)、「セグメントによる平面グラフの表現」、Intuitive Geometry、63 : 109–117、MR  1383616。
• Ehrlich, G.; Even, S.; Tarjan, RE (1976)、「平面における曲線の交差グラフ」、Journal of Combinatorial Theory、シリーズ B、21 (1): 8–20、doi :10.1016/0095-8956(76)90022-8、MR  0505857。
• Grötzsch、Herbert (1959)、「Zur Theorie der discreten Gebilde、VII: Ein Dreifarbensatz für dreikreisfreie Netze auf der Kugel」、Wiss。 Z. Martin-Luther-U.、Halle-Wittenberg、Math.-Nat.ライヘ、8 : 109–120、MR  0116320。
• Hartman, IB-A.; Newman, I.; Ziv, R. (1991)、「グリッド交差グラフについて」、離散数学、87 (1): 41–52、doi :10.1016/0012-365X(91)90069-E、MR  1090188。
• シェイナーマン、ER (1984)、グラフの交差クラスと複数の交差パラメータ、プリンストン大学博士論文。
• ウェスト、D. (1991)、「未解決問題#2」、SIAM Activity Group Newsletter in Discrete Mathematics、2 (1): 10–12。
• ゴンサルベス、ダニエル (2020)、「すべての平面グラフが PURE-4-DIR であるわけではない」、Journal of Graph Algorithms and Applications、24 (3): 293–301、doi : 10.7155/jgaa.00533。