ブリンクマングラフ

ブリンクマングラフ
ブリンクマングラフ
名前の由来	グンナー・ブリンクマン
頂点	21
エッジ	42
半径	3
直径	3
胴回り	5
自己同型	14 ( D 7 )
彩度数	4
色指数	5
本の厚さ	3
キュー番号	2
プロパティ	オイラー ハミルトニアン
グラフとパラメータの表

数学のグラフ理論の分野において、ブリンクマングラフは、1992年にグンナー・ブリンクマンによって発見された21の頂点と42の辺を持つ4正則グラフである^。[1]ブリンクマンとメリンガーによって1997年に初めて発表された。^[2]

彩度数4、彩度指数5、半径3、直径3、周囲長5である。また、3頂点連結グラフ、3辺連結グラフでもある。彩度数4、周囲長5の最小の4正則グラフである。^[2]本の厚さは3、列数は2である。 ^[3]

ブルックスの定理によれば、すべてのk正則グラフ（奇数サイクルとクリークを除く）の彩色数は最大でkです。また、1959 年以来、すべてのkとlに対して、内周が​​ lのk彩色グラフが存在することが知られています。^{[4]これら 2 つの結果と、} Chvátal グラフを含むいくつかの例に関連して、ブランコ・グリュンバウムは 1970 年に、すべてのkとlに対して、内周が​​ lのk彩色のk正則グラフが存在すると予想しました。^[5] Chvátalグラフは この予想のk  =  l = 4の場合を解き、Brinkmannグラフはk  = 4、l = 5の場合を解きます。Grünbaumの予想は、十分に大きいk に対してJohannsenによって反証されました。Johannsenは、三角形のないグラフの彩色数はO(Δ/log Δ)であることを示しました。ここで、Δは最大頂点次数であり、Oは大きなO表記を導入します。^[6]しかし、この反証にもかかわらず、例を見つけることは興味深いままであり、非常に少数しか知られていません。

ブリンクマングラフの彩色多項式はx 21 - ⁴² x 20 ⁺ 861 x ¹⁹ - 11480 x ¹⁸ + 111881 x ¹⁷ - 848708 x ¹⁶ + 5207711 x ¹⁵ - 26500254 x ¹⁴ + 113675219 x ¹³ - 415278052 x ¹² + 1299042255 x ¹¹ - 3483798283 x ¹⁰ + 7987607279 x ⁹ - 15547364853 x ⁸ + 25384350310 x ⁷ - 34133692383 x ⁶ + 36783818141 x ⁵ - 30480167403 x ⁴ + 18168142566 x ³ - 6896700738 x ² + 1242405972 x （ OEISの配列A159192）。

ブリンクマングラフは頂点推移グラフではなく、その完全自己同型群は、回転と反射の両方を含む七角形の対称性の群である、位数 14 の二面体群と同型です。

ブリンクマングラフの特性多項式は です。 ${\displaystyle (x-4)(x-2)(x+2)(x^{3}-x^{2}-2x+1)^{2}}$${\displaystyle (x^{6}+3x^{5}-8x^{4}-21x^{3}+27x^{2}+38x-41)^{2}}$

• 
  ブリンクマングラフの別の図。
• 
  ブリンクマングラフの彩色数は4 です。
• 
  ブリンクマングラフの色指数は5 です。

• ワイスタイン、エリック W.「ブリンクマン グラフ」。マスワールド。