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

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

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

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

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

Хроматический многочлен головы быка равен $(x - 2) (x - 1)^{3} x$ . Два других графа хроматически эквивалентны голове быка.

Характеристический многочлен графа равен $- x (x^{2} - x - 3) (x^{2} + x - 1)$ .

Многочлен Татта графа равен $x^{4} + x^{3} + x^{2} y$ . Шаблон:-