Голова быка (теория графов)

Голова Быка
Вершин	5
Рёбер	5
Радиус	2
Диаметр	3
Обхват	3
Автоморфизмы	2 (Z/2Z)
Хроматическое число	3
Хроматический индекс	3
Свойства	Планарный граф граф единичных расстояний

Голова быка — планарный неориентированный граф с 5 вершинами и 5 рёбрами в форме треугольника с двумя непересекающимися висячими рёбрами.

Хроматическое число графа равно 3, хроматический индекс равен 3, радиус 2, диаметр 3 и обхват 3. Граф является блоковым, расщепляемым, интервальным графом без клешней, вершинно 1-связным и рёберно 1связным.

Графы, свободные от голов быка

Граф свободен от голов быка, если голова не содержится в качестве порождённого подграфа. Графы без треугольников свободны от голов быка, поскольку каждая голова содержит треугольник. Сильная гипотеза о совершенных графах была доказана для графов без голов быка задолго до доказательства для графов общего вида и известен алгоритм распознавания совершенных графов без голов быка с полиномиальным временем работы.

Мария Чудновская и Самуэль Сафра изучали графы без голов быка в более общем виде и показали, что любой такой граф должен иметь либо большую клику, либо большое независимое множество (то есть гипотеза Эрдёша — Хайналя выполняется для графов-голов быка) и развили общую теорию структуры таких графов.

Хроматический и характеристический многочлены

Три графа с хроматическим многочленом $(x-2)(x-1)^{3}x$.

Хроматический многочлен головы быка равен $(x-2)(x-1)^{3}x$. Два других графа хроматически эквивалентны голове быка.

Характеристический многочлен графа равен $-x(x^{2}-x-3)(x^{2}+x-1)$.

Многочлен Татта графа равен $x^{4}+x^{3}+x^{2}y$.