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

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

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

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

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

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

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

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

Література

• Шаблон:Стаття
• Шаблон:Стаття
• Шаблон:Стаття