ブルグラフ

ブルグラフ
ブルグラフ
頂点	5
エッジ	5
半径	2
直径	3
周囲	3
自己同型写像	2 ( Z /2 Z )
彩色数	3
色度指数	3
物件	平面単位距離
グラフとパラメータの表

グラフ理論の数学分野では、ブルグラフは、2つの互いに素な垂下辺を持つ三角形の形をした、5つの頂点と5つの辺を持つ平面無向グラフである。 ^{[ 1 ]}

彩色数3、彩色指数3、半径2、直径3、周長3を持つ。また、自己相補グラフ、ブロックグラフ、分割グラフ、区間グラフ、爪のないグラフ、1頂点連結グラフ、 1辺連結グラフでもある。

グラフがブルフリーであるとは、誘導部分グラフとしてブルを持たない場合をいう。三角形フリーのグラフは、すべてのブルが三角形を含むため、ブルフリーのグラフである。強力な完全グラフ定理は、一般のグラフに対する証明よりもずっと前にブルフリーのグラフに対して証明されており^{[ 2 ]}、ブルフリーの完全グラフに対する多項式時間認識アルゴリズムが知られている^{[ 3 ] 。}

Maria ChudnovskyとShmuel Safra は、より一般的にブルフリーグラフを研究し、そのようなグラフは大きなクリークまたは大きな独立集合のいずれかを持つ必要があること(つまり、Erdős–Hajnal 予想はブルグラフに対して成り立つ) を示し、^{[ 4 ]}これらのグラフの一般的な構造理論を開発しました。^{[ 5 ] [ 6 ] [ 7 ]}

雄牛グラフの彩色多項式は${\displaystyle (x-2)(x-1)^{3}x}$他の2つのグラフは、ブルグラフと色彩的に同等である。

その固有多項式は${\displaystyle -x(x^{2}-x-3)(x^{2}+x-1)}$。

そのタッテ多項式は${\displaystyle x^{4}+x^{3}+x^{2}y}$。