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

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

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

Сумма по кликам двух планарных графов и графа Вагнера даёт граф с числом Хадвигера, равным четырём.

Из теоремы Вагнера, описывающей планарные графы их запрещёнными подграфами, следует, что планарные графы имеют число Хадвигера, не превосходящее 4. В некоторых статьях, содержащих доказательство теоремы, Вагнер[3] описывает графы с числом Хадвигера четыре и менее более точно — это графы, которые можно образовать с помощью операций сумма по клике планарных графов с графом Вагнера, имеющим 8 вершин.

Графы с числом Хадвигера пяти менее включают верхушечные графы и вложимые без зацепления графы, оба семейства имеют полный граф K₆ среди запрещённых миноров[4]

Любой граф с n вершинами и числом Хадвигера k имеет O(nk √log k) рёбер. Эта граница точна — для любого k существует граф с числом Хадвигера k, имеющий Ω(nk √log k) рёбер [5][6][7]. Если граф G имеет число Хадвигера k, то все его подграфы также имеют число Хадвигера, не превосходящее k, и отсюда следует, что граф G должен иметь вырожденность O(k √log k). Таким образом, графы с ограниченным числом Хадвигера являются разреженными графами.

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

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

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

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

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

Любой граф с числом Хадвигера k имеет максимум n2^{O(k log log k)} клик (полных подграфов) [12].

Халин [2] определил класс параметров графа, которые он назвал S-функциями. Среди них есть и число Хадвигера. Требуется, чтобы эти функции, отображающие графы в целые числа, принимали нулевое значение на графах без рёбер, были минорно монотонными, требуется увеличение на единицу при добавлении новой вершины, смежной со всеми предыдущими вершинами, и из двух значений для подграфов по обеим сторонам сепаратора клик функция должна принимать большее значение. Множество таких функций образует полную решётку по операциям взятия минимального или максимального элементов. Нижний элемент в такой решётке является числом Хадвигера, а верхний элемент — древесная ширина.