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

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

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

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

Графи, вільні від голів бика

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

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

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

Три графи з хроматичним многочленом ${\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}$.

Примітки

1. Weisstein, Eric W. Bull Graph(англ.) на сайті Wolfram MathWorld.
2. Chvátal, Sbihi, 1987, с. 127–139.
3. Reed, Sbihi, 1995, с. 171–178.
4. Chudnovsky, Safra, 2008, с. 1301–1310.

Література

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