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

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

Голова бика
Bull graph.circo.svg
Вершин	5
Ребер	5
Радіус	2
Діаметр	3
Обхват	3
Автоморфізм	2 (Z/2Z)
Хроматичне число	3
Хроматичний індекс	3
Властивості	планарний граф граф одиничних відстаней

Хроматичне число графа дорівнює 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$.

Література

• V. Chvátal, N. Sbihi. Bull-free Berge graphs are perfect // Graphs and Combinatorics. — 1987. — Т. 3, вип. 1. — С. 127–139. — DOI:10.1007/BF01788536.
• B. Reed, N. Sbihi. Recognizing bull-free perfect graphs // Graphs and Combinatorics. — 1995. — Т. 11, вип. 2. — С. 171–178. — DOI:10.1007/BF01929485.
• M. Chudnovsky, S. Safra. The Erdős–Hajnal conjecture for bull-free graphs // Journal of Combinatorial Theory. — 2008. — Т. 98, вип. 6. — С. 1301–1310. — (Series B). — DOI:10.1016/j.jctb.2008.02.005. Архівовано з джерела 25 червня 2010.