Граф Бринкмана — 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. Граф Хватала решает случай гипотезы, а граф Бринкмана решает случай . Гипотеза Грюнбаума опровергнута для достаточно больших k Йогансеном, который показал, что хроматическое число графа без треугольников равно , где равно максимальной степени вершины, а O означает O-большое. Тем не менее, несмотря на это опровержение, представляет интерес поиск примеров и известны только несколько таких графов.
Алгебраические свойства Граф Бринкмана не является вершинно-транзитивным графом и его группа автоморфизмов изоморфна диэдральной группе порядка 14, группе симметрий семиугольника, включая как вращения, так и зеркальные отражения.
Характеристический многочлен графа Бринкмана равен .
Хроматический многочлен графа Бринкмана равен + ().
Галерея
Примечания
Литература
Категория:Регулярные графы Категория:Графы, имеющие собственные названия