Loading article…
| ゴロムグラフ | |
|---|---|
 | |
| 名前の由来 | ソロモン・W・ゴロム |
| 頂点 | 10 |
| エッジ | 18 |
| 自己同型 | 6 |
| 彩度数 | 4 |
| プロパティ | |
| グラフとパラメータの表 | |
グラフ理論において、ゴロムグラフは10 個の頂点と 18 個の辺を持つ多面体グラフである。これは、任意のグラフ彩色で 4 色を必要とする単位距離グラフとして (非平面埋め込みを使用して) 構築したSolomon W. Golombにちなんで名付けられた。したがって、より単純なMoser スピンドルと同様に、これはHadwiger-Nelson 問題(ユークリッド平面の点を彩色して各単位線分の端点が異なる色になるようにするには、少なくとも 4 色が必要である)の下限を提供する。 [1]
工事
ゴロムグラフを単位距離グラフとして構築する方法は、外側の正多角形を描き、内側のねじれた多角形または星型多角形に接続することで、ピーターセングラフや一般化ピーターセングラフの単位距離表現にも使用されています。[2]モーザースピンドルと同様に、ゴロムグラフの単位距離埋め込みの座標は、 2次体 で表すことができます。[3]
![{\displaystyle \mathbb {Q} [{\sqrt {33}}]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/1b920b3da2daef8f7f2ff1cbc6618b2ad08963bd)
分数着色
ゴロムグラフの分数彩色数は 10/3 である。この数が少なくともこの大きさであるという事実は、グラフが 10 個の頂点を持ち、そのうち最大 3 個が任意の独立集合に含まれるという事実から導かれる。この数が最大この大きさであるという事実は、各頂点がちょうど 3 個の集合に含まれるような 3 頂点独立集合が 10 個見つかるという事実から導かれる。この分数彩色数は、モーザースピンドルの 7/2 よりも小さく、平面の単位距離グラフの分数彩色数よりも小さく、3.6190 から 4.3599 の間に制限される。[4]
参考文献
- ^ ソイファー、アレクサンダー（2008）、数学的ぬり絵の本：色彩の数学とその創作者の多彩な人生、ニューヨーク：シュプリンガー、p. 19、ISBN 978-0-387-74640-1
- ^ ジトニク、アルジャナ;ホーヴァット、ボリス。Pisanski、Tomaž (2012)、「すべての一般化された Petersen グラフは単位距離グラフである」、Journal of the Korea Mathematical Society、49 (3): 475–491、doi : 10.4134/JKMS.2012.49.3.475、MR 2953031
- ^ Pegg, Ed Jr. (2017 年 12 月 21 日)、「Moser Spindles、Golomb Graphs、および Root 33」、Wolfram Demonstrations Project
- ^ クランストン、ダニエル W.; ラバーン、ランドン (2017)、「平面の分数彩色数」、コンビナトリカ、37 (5): 837–861、arXiv : 1501.01647、doi :10.1007/s00493-016-3380-3、MR 3737371、S2CID 4687673
外部リンク
- Weisstein、Eric W.「ゴロムグラフ」。MathWorld。