Граф Бринкмана

граф Бринкмана
Назван в честь	Гуннара Бринкмана
Вершин	21
Рёбер	42
Радиус	3
Диаметр	3
Обхват	5
Автоморфизмы	14 (D7)
Хроматическое число	4
Хроматический индекс	5
Свойства	Гамильтонов Эйлеров Регулярный
Число очередей	2

Граф Бринкмана — 4-регулярный граф с 21 вершинами и 42 рёбрами, обнаруженный Гуннаром Бринкманом в 1992 году. Опубликовали его Бринкман и Мерингер в 1997 году.

Граф имеет хроматическое число 4, хроматический индекс 5, радиус 3, диаметр 3 и обхват 5. Он также вершинно 3-связен и рёберно 3-связен. Это самый маленький 4-регулярный граф обхвата 5 с хроматическим числом 4. Граф имеет книжную толщину 3 и число очередей 2.

Гипотеза Грюнбаума

По теореме Брукса любой k-регулярный граф (за исключением нечётных циклов и клик) имеет хроматическое число не превосходящее k. Известно было также с 1959 года, что для любых k и l существуют k-хроматические графы с обхватом l*. В связи с этими двумя результатами и несколькими примерами, включая граф Хватала, Бранко Грюнбаум высказал гипотезу в 1970 году, что для любых k и l существуют k-хроматические k-регулярные графы с обхватом l. Граф Хватала решает случай [math]\displaystyle{ k = l = 4 }[/math] гипотезы, а граф Бринкмана решает случай [math]\displaystyle{ k = 4, l = 5 }[/math]. Гипотеза Грюнбаума опровергнута для достаточно больших k Йогансеном, который показал, что хроматическое число графа без треугольников равно [math]\displaystyle{ \mathrm{O}(\Delta/\log \Delta) }[/math], где [math]\displaystyle{ \Delta }[/math] равно максимальной степени вершины, а O означает O-большое. Тем не менее, несмотря на это опровержение, представляет интерес поиск примеров и известны только несколько таких графов.

Алгебраические свойства

Граф Бринкмана не является вершинно-транзитивным графом и его группа автоморфизмов изоморфна диэдральной группе порядка 14, группе симметрий семиугольника, включая как вращения, так и зеркальные отражения.

Характеристический многочлен графа Бринкмана равен [math]\displaystyle{ (x-4)(x-2)(x+2)(x^3-x^2-2x+1)^2 }[/math][math]\displaystyle{ (x^6+3x^5-8x^4-21x^3+27x^2+38x-41)^2 }[/math].

Хроматический многочлен графа Бринкмана равен [math]\displaystyle{ x^{21} - 42x^{20} + 861x^{19} - 11480x^{18} + 111881x^{17} - 848708x^{16} + 5207711x^{15} - 26500254x^{14} }[/math] [math]\displaystyle{ + 113675219x^{13} - 415278052x^{12} + 1299042255x^{11} - 3483798283x^{10} + 7987607279x^9 }[/math] [math]\displaystyle{ - 15547364853x^8 + 25384350310x^7 - 34133692383x^6 + 36783818141x^5 - 30480167403x^4 }[/math] + [math]\displaystyle{ 18168142566x^3 - 6896700738x^2 + 1242405972x }[/math] (последовательность A159192 в OEIS).

Галерея

• 

  Хроматическое число графа Бринкмана равно 4.

• 

  Хроматический индекс графа Бринкмана равен 5.

Литература

• Brinkmann G. Generating Cubic Graphs Faster Than Isomorphism Checking. Preprint 92-047 SFB 343. — Bielefeld, Germany: University of Bielefeld, 1992.
• Brinkmann G., Meringer M. The Smallest 4-Regular 4-Chromatic Graphs with Girth 5 // Graph Theory Notes of New York. — 1997. — Вып. 32.
• Paul Erdős. Graph theory and probability // Canadian Journal of Mathematics. — 1959. — Т. 11, вып. 0. — С. 34–38. — doi:10.4153/CJM-1959-003-9.
• Jessica Wolz. Engineering Linear Layouts with SAT. — University of Tübingen, 2018. — (Master Thesis).
• Branko Grünbaum. A problem in graph coloring // American Mathematical Monthly. — Mathematical Association of America, 1970. — Т. 77, вып. 10. — С. 1088–1092. — doi:10.2307/2316101. — .
• Reed B. A. [math]\displaystyle{ \omega, \Delta }[/math], and [math]\displaystyle{ \chi }[/math] // Journal of Graph Theory. — 1998. — Т. 27, вып. 4. — С. 177–212. — doi:10.1002/(SICI)1097-0118(199804)27:4<177::AID-JGT1>3.0.CO;2-K.