ヒーウッド数

9色の三重トーラス（種数3の表面）–点線はハンドルを表す

数学において、曲面のヒーウッド数とは、曲面に 埋め込まれたグラフを着色するのに十分な色の数の上限です。

1890年にヒーウッドは球面以外のすべて の表面について、

${\displaystyle H(S)=\left\lfloor {\frac {7+{\sqrt {49-24e(S)}}}{2}}\right\rfloor =\left\lfloor {\frac {7+{\sqrt {1+48g(S)}}}{2}}\right\rfloor }$

オイラー特性 の曲面、または有向曲面の種数 の曲面に埋め込まれたグラフを色付けするには、色が必要です。 ^{[ 1 ]} この数は1976年にヒーウッド数として知られるようになりました。 ${\displaystyle e(S)}$ ${\displaystyle g(S)}$ ${\displaystyle H(S)}$

6色のクラインの壺は、ヒーウッド予想の唯一の例外である。

フランクリンは、クラインの壺に埋め込まれたグラフの彩色数はまで大きくなり得るが、 を超えることはないことを証明した。^{[ 2 ]}その後、ゲルハルト・リンゲル、JWTヤングス、その他の貢献者 の研究で、 がクラインの壺でない限り、頂点を持つ完全グラフは曲面に埋め込むことができることが証明された。^{[ 3 ]}これにより、ヒーウッドの境界は改善できないことが確立された。 ${\displaystyle 6}$ ${\displaystyle 6}$ ${\displaystyle H(S)}$ ${\displaystyle S}$ ${\displaystyle S}$

たとえば、頂点上の完全グラフは次のようにトーラスに埋め込むことができます。 ${\displaystyle 7}$

球面の場合は4色予想であり、1976年にケネス・アペルとヴォルフガング・ハーケンによって解決されました。 ^{[ 4 ] [ 5 ]}

注記

• Béla Bollobás、「グラフ理論：入門コース」、Graduate Texts in Mathematics、第 63 巻、Springer-Verlag、1979 年。Zbl  0411.05032。
• Thomas L. SaatyとPaul Chester Kainen ; The Four-Color Problem: Assaults and Conquest、ドーバー、1986 年。Zbl 0463.05041。 

この記事には、Creative Commons Attribution-Share-Alike Licenseに基づいてライセンスされているPlanetMathの Heawood 番号からの資料が組み込まれています。

参考文献

1. PJ Heawood ( 1890)、「地図着色定理」、Quarterly J. Math.、24 : 322–339
2. P. Franklin (1934)、「6色問題」、数学物理学ジャーナル、13 ( 1–4 ): 363– 379、doi : 10.1002/sapm1934131363
3. Gerhard Ringel; JWT Youngs (1968)、「Heawood Map-Coloring Problemの解法」、米国科学アカデミー紀要、60 (2): 438– 445、Bibcode : 1968PNAS...60..438R、doi : 10.1073/pnas.60.2.438、ISSN 0027-8424、PMC 225066、PMID 16591648   
4. ケネス・アペル、ヴォルフガング・ハーケン (1977)、「すべての平面地図は4色に色付け可能。I. 放電」、イリノイ数学ジャーナル、21 (3): 429– 490、MR 0543792 
5. ケネス・アペル、ヴォルフガング・ハーケン、ジョン・コッホ (1977)、「すべての平面地図は4色に色付け可能。II. 還元可能性」、イリノイ数学ジャーナル、21 (3): 491– 567、doi : 10.1215/ijm/1256049012、MR 0543793