Голова́ бика́ — планарний неорієнтований граф із 5 вершинами і 5 ребрами у формі трикутника з двома висячими ребрами, що не перетинаються.
Хроматичне число графа дорівнює 3, хроматичний індекс дорівнює 3, радіус 2, діаметр 3 і обхват 3. Граф є блоковим, розщеплюваним, інтервальним графом без клешень, 1-вершинно-зв'язним і 1-реберно-зв'язним.
Графи, вільні від голів бика Граф вільний від голів бика, якщо голова не міститься як породжений подграф. Графи без трикутників вільні від голів бика, оскільки кожна голова містить трикутник. Сильну гіпотезу про досконалі графи доведено для графів без голів бика задовго до доведення для графів загального вигляду і відомо алгоритм розпізнавання досконалих графів без голів бика з поліноміальним часом роботи.
Марія Чудновська й Самуель Сафра вивчали графи без голів бика в загальнішому вигляді й показали, що кожен такий граф повинен мати або велику кліку, або велику незалежну множину (тобто для графів-голів бика виконується гіпотеза Ердеша — Хайналя) і розвинули загальну теорію структури таких графів.
Хроматичний та характеристичний многочлени
Хроматичний многочлен голови бика дорівнює . Два інші графи хроматично еквівалентні голові бика.
Характеристичний многочлен графа дорівнює .
Многочлен Татта графа дорівнює .
Примітки
Література