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

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

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

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

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

Граф Бринкмана не является вершинно-транзитивным графом и его группа автоморфизмов изоморфна диэдральной группе порядка 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}}$.

Хроматический многочлен графа Бринкмана равен ${\displaystyle x^{21}-42x^{20}+861x^{19}-11480x^{18}+111881x^{17}-848708x^{16}+5207711x^{15}-26500254x^{14}}$ ${\displaystyle +113675219x^{13}-415278052x^{12}+1299042255x^{11}-3483798283x^{10}+7987607279x^{9}}$ ${\displaystyle -15547364853x^{8}+25384350310x^{7}-34133692383x^{6}+36783818141x^{5}-30480167403x^{4}}$ + ${\displaystyle 18168142566x^{3}-6896700738x^{2}+1242405972x}$ (последовательность 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. — JSTOR 2316101.
• Reed B. A. ${\displaystyle \omega ,\Delta }$, and ${\displaystyle \chi }$ // 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.