Loading article…
| プッサングラフ | |
|---|---|
 | |
| 頂点 | 15 |
| エッジ | 39 |
| 半径 | 3 |
| 直径 | 3 |
| 胴回り | 3 |
| 自己同型 | 2 ( Z /2 Z ) |
| 彩度数 | 4 |
| 色指数 | 6 |
| プロパティ | ハミルトン 平面 |
| グラフとパラメータの表 | |
グラフ理論において、プッサングラフは15 個の頂点と 39 個の辺を持つ平面グラフです。シャルル・ジャン・ド・ラ・ヴァレ＝プッサンにちなんで名付けられました。
歴史
1879年、アルフレッド・ケンペはグラフ理論における大きな予想の一つである四色定理の証明を発表しました。[1] 定理は正しいものの、ケンペの証明は誤りです。パーシー・ジョン・ヒーウッドは1890年に 反例を用いてこれを示しました。 [2]そして、デ・ラ・ヴァレ・プッサンは1896年にプッサングラフを用いて同じ結論に達しました。[3]
ケンペの（誤った）証明は交互鎖に基づいており、これらの鎖がグラフ理論で有用であることが証明されているため、数学者はそのような反例に興味を持ち続けています。その後、さらに多くの反例が見つかりました。最初は1921年のエレラグラフ、[4] [5]、 次に1935年の23頂点のキッテルグラフ、[6] 、そして最後に2つの極小反例（1997年のソイファーグラフと1998年のフリッチュグラフ、どちらも位数は9）です。[7] [8] [9]
参考文献
- ^ Kempe, AB「4色の地理的問題について」Amer. J. Math. 2, 193–200, 1879年。
- ^ PJ Heawood、「地図の色定理」、Quart. J. Pure Appl. Math. 24 (1890)、332–338。
- ^ RA Wilson、「グラフ、着色、および4色定理」、オックスフォード大学出版局、オックスフォード、2002年。MR 1888337 Zbl 1007.05002 。
- ^ Errera, A. 「分析状況に関する色とりどりの質問」。博士号論文。 1921年。
- ^ Peter Heinig. Errera Graph が狭い Kempe-Impasse であることの証明。2007 年。
- ^ Kittell, I. 「部分的に色付けされた地図上の一連の演算」 Bull. Amer. Math. Soc. 41, 407–413, 1935.
- ^ A. Soifer、「ビクトリア朝時代の地図の色付け：問題と歴史」、数学コンペティション10（1997）、20-31。
- ^ R. Fritsch と G. Fritsch、「The Four-Color Theorem」、Springer、ニューヨーク、1998 年。MR 1633950。
- ^ ゲスナー、E. およびシュプリンガー、WM II。「ケンプの4色定理の証明はどの程度間違っているか？」コングレ。Numer。164、159–175、2003年。
外部リンク
- エリック W. ワイスタイン、プッサン グラフ ( MathWorld )