WikiSort.ru - Не сортированное

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

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

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

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

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

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

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

Хроматический многочлен головы быка равен ${\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}$ .

Примечания

Литература

Для улучшения этой статьи желательно: Проверить качество перевода с иностранного языка. Исправить статью согласно стилистическим правилам Википедии.