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

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

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

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

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

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

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