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

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

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

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

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

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

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

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

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

Галерея

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

Литература

• Шаблон:Книга
• Шаблон:Статья
• Шаблон:Статья
• Шаблон:Книга
• Шаблон:Статья
• Шаблон:Статья