График быка

В математической области теории графов бычий граф — это плоский неориентированный граф с 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. Вайсштейн, Эрик В. «Bull Graph». MathWorld .
2. Chvátal, V. ; Sbihi, N. (1987), «Без быков графы Берже совершенны», Графы и комбинаторика , 3 (1): 127–139, doi :10.1007/BF01788536, S2CID  44570627.
3. Рид, Б.; Сбихи , Н. (1995), «Распознавание совершенных графов без быков», Графы и комбинаторика , 11 (2): 171–178, doi :10.1007/BF01929485, S2CID  206808701.
4. Чудновский, М .; Сафра, С. (2008), «Гипотеза Эрдёша–Хайнала для графов без быков», Журнал комбинаторной теории , Серия B, 98 (6): 1301–1310, CiteSeerX 10.1.1.606.3091 , doi : 10.1016/j.jctb.2008.02.005 .
5. Чудновский, М. (2008), Структура графов без быков. I. Трехреберные пути с центрами и антицентрами (PDF).
6. Чудновский, М. (2008), Структура графов без быков. II. Элементарные триграфы (PDF).
7. Чудновский, М. (2008), Структура графов без быков. III. Глобальная структура (PDF).