Голова бика (теорія графів)
| Голова бика | |
|---|---|
| Bull graph.circo.svg | |
| Вершин | 5 |
| Ребер | 5 |
| Радіус | 2 |
| Діаметр | 3 |
| Обхват | 3 |
| Автоморфізм | 2 (Z/2Z) |
| Хроматичне число | 3 |
| Хроматичний індекс | 3 |
| Властивості | планарний граф граф одиничних відстаней |
Голова́ бика́ — планарний неорієнтований граф із 5 вершинами і 5 ребрами у формі трикутника з двома висячими ребрами, що не перетинаються[1].
Хроматичне число графа дорівнює 3, хроматичний індекс дорівнює 3, радіус 2, діаметр 3 і обхват 3. Граф є блоковим, розщеплюваним, інтервальним графом без клешень, 1-вершинно-зв'язним і 1-реберно-зв'язним.
Граф вільний від голів бика, якщо голова не міститься як породжений подграф. Графи без трикутників вільні від голів бика, оскільки кожна голова містить трикутник. Сильну гіпотезу про досконалі графи доведено для графів без голів бика задовго до доведення для графів загального вигляду[2] і відомо алгоритм розпізнавання досконалих графів без голів бика з поліноміальним часом роботи[3].
Марія Чудновська й Самуель Сафра вивчали графи без голів бика в загальнішому вигляді й показали, що кожен такий граф повинен мати або велику кліку, або велику незалежну множину (тобто для графів-голів бика виконується гіпотеза Ердеша — Хайналя)[4] і розвинули загальну теорію структури таких графів.
Хроматичний многочлен голови бика дорівнює . Два інші графи хроматично еквівалентні голові бика.
Характеристичний многочлен графа дорівнює .
Многочлен Татта графа дорівнює .
- ↑ Weisstein, Eric W. Bull Graph(англ.) на сайті Wolfram MathWorld.
- ↑ Chvátal, Sbihi, 1987, с. 127–139.
- ↑ Reed, Sbihi, 1995, с. 171–178.
- ↑ Chudnovsky, Safra, 2008, с. 1301–1310.
- V. Chvátal, N. Sbihi. Bull-free Berge graphs are perfect // Graphs and Combinatorics. — 1987. — Т. 3, вип. 1. — С. 127–139. — DOI:.
- B. Reed, N. Sbihi. Recognizing bull-free perfect graphs // Graphs and Combinatorics. — 1995. — Т. 11, вип. 2. — С. 171–178. — DOI:.
- 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:. Архівовано з джерела 25 червня 2010.