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

Голова Быка
Вершин	5
Рёбер	5
Радиус	2
Диаметр	3
Обхват	3
Автоморфизмы	2 (Z/2Z)
Хроматическое число	3
Хроматический индекс	3
Свойства	Планарный граф граф единичных расстояний

Голова быка — планарный неориентированный граф с 5 вершинами и 5 рёбрами в форме треугольника с двумя непересекающимися висячими рёбрами^[1].

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

Графы, свободные от голов быка

Граф свободен от голов быка, если голова не содержится в качестве порождённого подграфа. Графы без треугольников свободны от голов быка, поскольку каждая голова содержит треугольник. Сильная гипотеза о совершенных графах была доказана для графов без голов быка задолго до доказательства для графов общего вида^[2] и известен алгоритм распознавания совершенных графов без голов быка с полиномиальным временем работы^[3].

Мария Чудновская^[англ.] и Самуэль Сафра изучали графы без голов быка в более общем виде и показали, что любой такой граф должен иметь либо большую клику, либо большое независимое множество (то есть гипотеза Эрдёша — Хайналя выполняется для графов-голов быка)^[4] и развили общую теорию структуры таких графов^[5][6][7].

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

Три графа с хроматическим многочленом ${\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.
5. Chudnovsky, M. (2008), The structure of bull-free graphs. I. Three-edge paths with centers and anticenters (PDF), Архивировано (PDF) 3 марта 2016, Дата обращения: 27 февраля 2017 Источник  (неопр.). Дата обращения: 27 февраля 2017. Архивировано 3 марта 2016 года..
6. Chudnovsky, M. (2008), The structure of bull-free graphs. II. Elementary trigraphs (PDF), Архивировано (PDF) 4 марта 2016, Дата обращения: 27 февраля 2017 Источник  (неопр.). Дата обращения: 27 февраля 2017. Архивировано 4 марта 2016 года..
7. Chudnovsky, M. (2008), The structure of bull-free graphs. III. Global structure (PDF), Архивировано (PDF) 3 марта 2016, Дата обращения: 27 февраля 2017 Источник  (неопр.). Дата обращения: 27 февраля 2017. Архивировано 3 марта 2016 года..

Литература

• 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. — doi:10.1016/j.jctb.2008.02.005. Архивировано 25 июня 2010 года.