ゴロムグラフ

ゴロムグラフ
名前の由来	ソロモン・W・ゴロム
頂点	10
エッジ	18
自己同型	6
彩色数	4
プロパティ	多面体 単位距離
グラフとパラメータの表

グラフ理論において、ゴロムグラフは10頂点18辺の多面体グラフである。ソロモン・W・ゴロムにちなんで名付けられた。彼は、このグラフを（非平面埋め込みを用いて）任意のグラフ彩色において4色を必要とする単位距離グラフとして構築した。したがって、より単純なモーザースピンドルと同様に、ゴロムグラフはハドヴィガー・ネルソン問題（ユークリッド平面上の点を、各単位線分の端点が異なる色になるように彩色するには、少なくとも4色が必要である）の下限値を提供する。 ^{[ 1 ]}

工事

単位距離グラフとして描かれたゴロムグラフの4色塗り

ゴロムグラフを単位距離グラフとして構築する方法は、外側の正多角形を描き、内側のねじれ多角形または星型多角形に接続することで、ピーターセングラフや一般化ピーターセングラフの単位距離表現にも使用されています。^{[ 2 ]}モーザースピンドルと同様に、ゴロムグラフの単位距離埋め込みの座標は二次形式 で表すことができます。^{[ 3 ]}${\displaystyle \mathbb {Q} [{\sqrt {33}}]}$

分数着色

ゴロムグラフの分数彩色数は10/3である。この数が少なくともこの大きさであることは、グラフが10個の頂点を持ち、そのうち最大3個が任意の独立集合に存在できるという事実から導かれる。この数が最大でこの大きさであることは、各頂点がちょうど3個存在するような3頂点独立集合が10個存在できることから導かれる。この分数彩色数は、モーザースピンドルの7/2よりも小さく、平面の単位距離グラフの分数彩色数（3.6190と4.3599の間に制限される）よりも小さい。^{[ 4 ]}

参考文献

1. ソイファー、アレクサンダー（2008年）、数学的ぬり絵の本：色彩の数学とその創作者たちの多彩な人生、ニューヨーク：シュプリンガー、p. 19、ISBN 978-0-387-74640-1
2. ジトニク、アルジャナ;ホーヴァット、ボリス。Pisanski、Tomaž (2012)、「すべての一般化された Petersen グラフは単位距離グラフである」、Journal of the Korea Mathematical Society、49 (3): 475–491、doi : 10.4134/JKMS.2012.49.3.475、MR 2953031 
3. Pegg, Ed Jr. (2017年12月21日)、「Moser Spindles, Golomb Graphs and Root 33」、Wolfram Demonstrations Project
4. クランストン、ダニエル・W.; ラバーン、ランドン (2017)、「平面の分数彩色数」、コンビナトリカ、37 (5): 837– 861、arXiv : 1501.01647、doi : 10.1007/s00493-016-3380-3、MR 3737371、S2CID 4687673  

外部リンク

• Weisstein, Eric W. 「ゴロムグラフ」 . MathWorld .