Число Хадвигера

Граф с четырьмя связными подграфами, которые при сжатии образуют полный граф. он не имеет полного минора из пяти вершин По теореме Вагнера , поэтому его число Хадвигера равно четырем.

В теории графов неориентированного число Хадвигера графа G — это размер наибольшего полного графа который можно получить, ребра G. сжимая , Аналогично, число Хадвигера h ( G ) — это наибольшее число n, для которого полный граф K _n является минорным графом G , меньшим графом, полученным из G путем сжатия ребер и удаления вершин и ребер. Число Хадвигера также известно как клики сжатия число G. или степень гомоморфизма группы G . Оно названо в честь Хьюго Хадвигера его в 1943 году в сочетании с гипотезой Хадвигера которая утверждает, что число Хадвигера всегда не меньше хроматического числа G. , который представил ,

Графы, у которых число Хадвигера не превышает четырех, были охарактеризованы Вагнером (1937) . Графы с любой конечной границей числа Хадвигера разрежены и имеют небольшое хроматическое число. Определить число Хадвигера графа NP-сложно , но с фиксированными параметрами можно .

с малым

Граф G имеет число Хадвигера не более двух тогда и только тогда, когда является лесом , поскольку полный минор с тремя вершинами может быть образован только путем сжатия цикла в G. он

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

Клика-сумма двух плоских графов и графа Вагнера, образующая больший граф с номером Хадвигера четыре.

Теорема Вагнера , которая характеризует плоские графы их запрещенными минорами , подразумевает, что плоские графы имеют число Хадвигера не более четырех. В той же статье, в которой была доказана эта теорема, Вагнер (1937) также более точно охарактеризовал графы с числом Хадвигера не более четырех: это графы, которые могут быть сформированы с помощью операций суммы клик , объединяющих плоские графы с восьмивершинным графом Вагнера .

Графы с числом Хадвигера не более пяти включают вершинные графы и бессвязно встраиваемые графы , оба из которых имеют полный граф K ₆ среди своих запрещенных миноров.

Разреженность

Каждый граф с n вершинами и числом Хадвигера k имеет ⁠ $O(nk{\sqrt {\log k}})$⁠ края. Эта граница точна: для каждого k существуют графы с числом Хадвигера k , которые имеют ⁠ $\Omega (nk{\sqrt {\log k}})$⁠ края. Если граф G имеет число Хадвигера k , то все его подграфы также имеют число Хадвигера не более k , и отсюда следует, что G должен иметь вырождение ⁠ $O(k{\sqrt {\log k}})$⁠ . Следовательно, графы с ограниченным числом Хадвигера являются разреженными графами .

Раскраска

утверждает Гипотеза Хадвигера Хадвигера всегда не меньше хроматического числа G. , что число То есть каждый граф с числом Хадвигера k должен иметь раскраску графа не более чем в k цветов. Случай k = 4 эквивалентен (согласно характеристике Вагнера графов с этим числом Хадвигера) теореме о четырех цветах о раскрасках плоских графов , и гипотеза также была доказана для k ≤ 5 , но остается недоказанной для больших значений k . .

Из-за низкой вырожденности графы с числом Хадвигера не выше k можно раскрасить с помощью жадного алгоритма раскраски, используя ⁠ $O(k{\sqrt {\log k}})$⁠ цвета.

сложность

Проверка того, является ли число Хадвигера данного графа хотя бы заданным значением k, является NP-полной , откуда следует, что определение числа Хадвигера NP-трудно . Однако проблема разрешима с фиксированными параметрами : существует алгоритм поиска наибольшего минора клики за время, которое зависит только полиномиально от размера графа, но экспоненциально от h ( G ) . Кроме того, алгоритмы с полиномиальным временем могут аппроксимировать число Хадвигера значительно точнее, чем лучшее приближение с полиномиальным временем (при условии, что P ≠ NP ) до размера наибольшего полного подграфа .

Связанные понятия

Ахроматическое число графа G — это размер наибольшей клики, которая может быть образована сжатием семейства множеств в G. независимых

Несчетные миноры клики в бесконечных графах можно охарактеризовать с помощью убежищ , которые формализуют стратегии уклонения для некоторых игр преследования-уклонения : если число Хадвигера несчетно, то оно равно наибольшему порядку убежища в графе.

Каждый граф с числом Хадвигера k имеет не более n 2 ^{O ( k журнал (журнал k ))} клики (полные подграфы).

Халин (1976) определяет класс параметров графа, который он называет S -функциями, которые включают число Хадвигера. Эти функции от графов к целым числам должны быть равны нулю на графах без ребер , быть минорно-монотонными , увеличиваться на единицу при добавлении новой вершины, смежной со всеми предыдущими вершинами, и брать большее значение из двух подграфов по обе стороны от клик разделителя . Множество всех таких функций образует полную решетку относительно операций поэлементной минимизации и максимизации. Нижний элемент в этой решетке — это число Хадвигера, а верхний элемент — ширина дерева .

Ссылки

• Алон, Нога ; Лингас, Анджей; Вален, Мартин (2007), «Аппроксимация максимальной минорной клики и некоторые проблемы гомеоморфизма подграфов» (PDF) , Theoretical Computer Science , 374 (1–3): 149–158, doi : 10.1016/j.tcs.2006.12.021 .
• Боллобас, Б. ; Кэтлин, Пенсильвания; Эрдеш, Пол (1980), «Гипотеза Хадвигера верна почти для каждого графа» (PDF) , European Journal of Combinatorics , 1 (3): 195–199, doi : 10.1016/s0195-6698(80)80001-1 .
• Эппштейн, Дэвид (2009), «Найти миноры больших клик сложно», Журнал графовых алгоритмов и приложений , 13 (2): 197–204, arXiv : 0807.0007 , doi : 10.7155/jgaa.00183 , S2CID   166774 .
• Фомин Федор Владимирович; Oum, Санг-ил ; Тиликос, Димитриос М. (2010), «Ранговая и древовидная ширина H графов без -миноров», European Journal of Combinatorics , 31 (7): 1617–1628, arXiv : 0910.0079 , doi : 10.1016/j. ejc.2010.05.003 , S2CID   248400643 .
• Хадвигер, Хьюго (1943), «О классификации комплексов маршрутов», Quarterjschr. Натуралист Гес Цюрих , 88 : 133–143 .
• Халин, Рудольф (1976), « S -функции для графов», Journal of Geometry , 8 (1–2): 171–186, doi : 10.1007/BF01917434 , MR   0444522 , S2CID   120256194 .
• Косточка, А. В. (1984), «Нижняя граница числа Хадвигера графов по их средней степени», Combinatorica , 4 (4): 307–316, doi : 10.1007/BF02579141 , S2CID   15736799 .
• Робертсон, Нил ; Сеймур, Пол ; Томас, Робин (1991), «Исключая бесконечные миноры», Discrete Mathematics , 95 (1–3): 303–319, doi : 10.1016/0012-365X(91)90343-Z , MR   1141945 .
• Робертсон, Нил ; Сеймур, Пол ; Томас, Робин (1993a), «Гипотеза Хадвигера для ₍ графов, свободных от K6» PDF) , Combinatorica , 13 (3): 279–361, doi : 10.1007/BF01202354 , S2CID   9608738 .
• Робертсон, Нил ; Сеймур, Полиция ; Томас, Робин (1993b), «Бесзвенные вложения графов в трехмерное пространство», Бюллетень Американского математического общества , 28 (1): 84–89, arXiv : math/9301216 , doi : 10.1090/S0273-0979-1993- 00335-5 , МР   1164063 , S2CID   1110662 .
• Томасон, Эндрю (2001), «Экстремальная функция для полных миноров», Журнал комбинаторной теории , серия B, 81 (2): 318–338, doi : 10.1006/jctb.2000.2013 .
• Вагнер, К. (1937), «О свойстве плоских комплексов», Math. , 114 : 570–590, doi : 10.1007/BF01594196 , S2CID   123534907 .