Гипотеза Хадвигера (теория графов)

Смотрите также: гипотеза Хадвигера (комбинаторная геометрия)

Нерешенная задача по математике :

Каждый ли график с хроматическим числом $k$ иметь $k$-вершинный полный граф как минор ?

(еще нерешенные задачи по математике)

Граф, для которого требуется четыре цвета в любой раскраске и четыре связных подграфа, которые при сжатии образуют полный граф, иллюстрирующий случай k = 4 гипотезы Хадвигера.

В теории графов утверждает гипотеза Хадвигера , что если $G$ не имеет петель и не имеет $K_{t}$ минор , то его хроматическое число удовлетворяет $\chi (G)<t$. Известно, что это верно для $1\leq t\leq 6$. Гипотеза является обобщением теоремы о четырех цветах и ​​считается одной из наиболее важных и сложных открытых проблем в этой области.

Более подробно, если все правильные раскраски неориентированного графа $G$ использовать $k$ или более цветов, то можно найти $k$ непересекающиеся связные подграфы ​ $G$ такой, что каждый подграф соединен ребром с каждым другим подграфом. Сжатие ребер внутри каждого из этих подграфов так, чтобы каждый подграф сжимался до одной вершины, дает полный граф. $K_{k}$ на $k$ вершины как минорные из $G$.

Эта гипотеза, представляющая собой далеко идущее обобщение проблемы четырех цветов , была высказана Хьюго Хадвигером в 1943 году и до сих пор не решена. Боллобас, Катлин и Эрдеш (1980) называют это «одной из самых глубоких нерешенных проблем теории графов».

Эквивалентные формы

Эквивалентная форма гипотезы Хадвигера ( противоположная форме, указанной выше) заключается в том, что если не существует последовательности сокращений ребер (каждое из которых объединяет две конечные точки некоторого ребра в одну супервершину), которая приводит к графу $G$ к полному графику $K_{k}$, затем $G$ должен иметь раскраску вершин с $k-1$ цвета.

В минимальном $k$-раскраска любого графа $G$, сведение каждого цветового класса раскраски к одной вершине создаст полный граф $K_{k}$. Однако этот процесс сокращения не приводит к незначительному $G$ поскольку между любыми двумя вершинами одного и того же цветового класса (по определению) нет края, поэтому сокращение не является сжатием края (которое требуется для миноров). Гипотеза Хадвигера утверждает, что существует другой способ правильного сжатия ребер множества вершин до отдельных вершин, создавая полный граф. $K_{k}$, таким образом, что все сжимаемые множества связаны.

Если ${\mathcal {F}}_{k}$ обозначает семейство графов, обладающее свойством, что все миноры графов в ${\mathcal {F}}_{k}$ может быть $(k-1)$-цветные, следует то из теоремы Робертсона–Сеймура , что ${\mathcal {F}}_{k}$ может быть охарактеризовано конечным набором запрещенных миноров . Гипотеза Хадвигера состоит в том, что это множество состоит из единственного запрещенного минора, $K_{k}$.

Хадвигера Число $h(G)$ графика $G$ это размер $k$ самого большого полного графа $K_{k}$ это несовершеннолетний из $G$ (или, что то же самое, может быть получено путем стягивания ребер $G$). Его еще называют сокращения . числом клики $G$. Гипотезу Хадвигера можно сформулировать в простой алгебраической форме $\chi (G)\leq h(G)$ где $\chi (G)$ обозначает хроматическое число $G$.

и

Дело $k=2$ тривиально: графу требуется более одного цвета тогда и только тогда, когда у него есть ребро, и это ребро само является $K_{2}$ незначительный. Дело $k=3$ тоже просто: графы, требующие трех цветов, являются недвудольными графами , и каждый недвудольный граф имеет нечетный цикл , который можно свернуть до 3-цикла, то есть $K_{3}$ незначительный.

В той же статье, в которой он представил эту гипотезу, Хадвигер доказал ее истинность для $k=4$. Графики без $K_{4}$ второстепенными являются последовательно-параллельные графы и их подграфы. Каждый граф этого типа имеет вершину, имеющую не более двух инцидентных ребер; любой такой граф можно раскрасить в три цвета, удалив одну такую ​​вершину, рекурсивно раскрасив оставшийся граф, а затем добавив обратно и раскрасив удаленную вершину. Поскольку удаленная вершина имеет не более двух ребер, при повторном добавлении вершины для ее окраски всегда будет доступен один из трех цветов.

Справедливость гипотезы для $k=5$ подразумевает теорему о четырех цветах : если гипотеза верна, каждый граф, требующий пяти или более цветов, будет иметь $K_{5}$ минорным и будет (по теореме Вагнера ) неплоским. Клаус Вагнер доказал в 1937 году, что дело $k=5$ на самом деле эквивалентно теореме о четырех цветах, и поэтому теперь мы знаем, что это верно. Как показал Вагнер, каждый график, не имеющий $K_{5}$ минор может быть разложен с помощью клик-суммы на части, которые являются либо плоскими, либо 8-вершинной лестницей Мёбиуса , и каждая из этих частей может быть раскрашена в 4 цвета независимо друг от друга, поэтому 4-раскраска $K_{5}$-безминорный граф следует из 4-раскраски каждой из плоских частей.

Робертсон, Сеймур и Томас (1993) доказали гипотезу о $k=6$, также используя теорему о четырех цветах; их статья с этим доказательством получила премию Фулкерсона 1994 года . Из их доказательства следует, что бессвязно встраиваемые графы — трёхмерный аналог планарных графов — имеют хроматическое число не более пяти. Благодаря этому результату известно, что гипотеза верна для $k\leq 6$, но она остается нерешенной для всех $k>6$.

Для $k=7$известны некоторые частичные результаты: каждый 7-хроматический граф должен содержать либо $K_{7}$ несовершеннолетний или оба $K_{4,4}$ несовершеннолетний и $K_{3,5}$ незначительный.

Каждый график $G$ имеет вершину с не более чем ${\textstyle O{\bigl (}h(G){\sqrt {\log h(G)}}{\bigr )}}$ инцидентные края, откуда следует, что жадный алгоритм раскраски , который удаляет эту вершину низкой степени, раскрашивает оставшийся граф, а затем добавляет обратно удаленную вершину и раскрашивает ее, раскрасит данный граф в ${\textstyle O{\bigl (}h(G){\sqrt {\log h(G)}}{\bigr )}}$ цвета.

In the 1980s, Alexander V. Kostochka и Эндрю Томасон оба независимо друг от друга доказали, что каждый граф без $K_{k}$ несовершеннолетний имеет среднюю степень ${\textstyle O(k{\sqrt {\log k}})}$ и, таким образом, может быть раскрашен с помощью ${\textstyle O(k{\sqrt {\log k}})}$ цвета. Последовательность улучшений этой оценки привела к доказательству $O(k\log \log k)$-раскраска для графиков без $K_{k}$ несовершеннолетние.

Обобщения

Дьёрдь Хайош предположил, что гипотезу Хадвигера можно усилить до подразделений, а не до миноров: то есть, что каждый граф с хроматическим числом $k$ содержит подразделение полного графа $K_{k}$. Гипотеза Хайоса верна для $k\leq 4$, но Кэтлин (1979) нашел контрпримеры этой усиленной гипотезе для $k\geq 7$; дела $k=5$ и $k=6$ оставаться открытым. Эрдеш и Файтлович (1981) заметили, что гипотеза Хайоша совершенно не работает для случайных графов : для любых $\varepsilon >0$, в пределе количества вершин, $n$, стремится к бесконечности, вероятность приближается к той, что случайное $n$-граф вершин имеет хроматическое число $\geq ({\tfrac {1}{2}}-\varepsilon )n/\log _{2}n$и что его крупнейшее кликовое подразделение имеет ${\textstyle O({\sqrt {n}})}$ вершины. В этом контексте стоит отметить, что вероятность также приближается к той, что случайное $n$-вершинный граф имеет число Хадвигера, большее или равное его хроматическому числу, поэтому гипотеза Хадвигера справедлива для случайных графов с высокой вероятностью; точнее, число Хадвигера с большой вероятностью пропорционально ${\textstyle n/{\sqrt {\log n}}}$.

Боровецкий (1993) задался вопросом, можно ли распространить гипотезу Хадвигера на раскраску списков . Для $k\leq 4$, каждый граф со списком хроматических номеров $k$ имеет $k$-малая вершинная клика. Однако максимальное хроматическое число планарных графов в списке равно 5, а не 4, поэтому расширение не выполняется уже для $K_{5}$-безминорные графы. В более общем плане для каждого $t\geq 1$, существуют графы, у которых число Хадвигера равно $3t+1$ и чье хроматическое число в списке равно $4t+1$.

Джерардс и Сеймур предположили, что каждый граф $G$ с хроматическим номером $k$ имеет полный график $K_{k}$ как странный несовершеннолетний . Такую структуру можно представить как семейство $k$ вершинно-непересекающиеся поддеревья $G$, каждое из которых двухцветное, так что каждая пара поддеревьев соединена одноцветным ребром. Хотя графики без странностей $K_{k}$ минорные не обязательно разрежены , для них справедлива такая же верхняя оценка, как и для стандартной гипотезы Хадвигера: граф без нечетных $K_{k}$ минор имеет хроматическое число ${\textstyle \chi (G)=O{\bigl (}k{\sqrt {\log k}}{\bigr )}}$.

Навязывая дополнительные условия $G$, возможно, удастся доказать существование более крупных миноров, чем $K_{k}$. Одним из примеров является теорема Снарка , согласно которой каждый кубический граф, требующий четырех цветов в любой раскраске ребер, имеет граф Петерсена в качестве минора, выдвинутую У. Таттом и объявленную доказанной в 2001 году Робертсоном, Сандерсом, Сеймуром и Томасом.

Ссылки

• Барат, Янош; Жоре, Гвенаэль; Вуд, Дэвид Р. (2011), «Опровержение гипотезы Хадвигера о списке» , Electronic Journal of Combinatorics , 18 (1): P232, arXiv : 1110.2272 , doi : 10.37236/719 , S2CID   13822279
• Боллобас, Б. ; Кэтлин, Пенсильвания; Эрдеш, Пол (1980), «Гипотеза Хадвигера верна почти для каждого графа» (PDF) , European Journal of Combinatorics , 1 (3): 195–199, doi : 10.1016/s0195-6698(80)80001-1
• Боровецкий, Мечислав (1993), «Исследовательская задача 172», Дискретная математика , 121 (1–3): 235–236, doi : 10.1016/0012-365X(93)90557-A
• Кэтлин, Пенсильвания (1979), «Гипотеза Хайоса о раскраске графов: вариации и контрпримеры», Журнал комбинаторной теории, серия B , 26 (2): 268–274, doi : 10.1016/0095-8956(79)90062-5
• Делькур, Мишель; Постл, Люк (2021), Сведение линейной гипотезы Хадвигера к раскраске небольших графов , arXiv : 2108.01633
• Дистель, Рейнхард (2017), «Гипотеза 7.3 Хадвигера», Теория графов , Тексты для выпускников по математике, том. 173 (5-е изд.), Springer, Берлин, стр. 183–186, ISBN.  978-3-662-57560-4 , МР   3822066
• Эрдос, Пол ; Файтлович, Семион (1981), «О гипотезе Хайоса», Combinatorica , 1 (2): 141–143, doi : 10.1007/BF02579269 , S2CID   1266711
• Гилен, Джим ; Джерардс, Берт; Рид, Брюс ; Сеймур, Пол ; Ветта, Адриан (2006), «О нечетно-минорном варианте гипотезы Хадвигера» , Журнал комбинаторной теории, серия B , 99 (1): 20–29, doi : 10.1016/j.jctb.2008.03.006
• Хадвигер, Хьюго (1943), «О классификации комплексов маршрутов», Quarterjschr. Натуралист Гес, Цюрих , 88 : 133–143.
• Каварабаяши, Кен-ичи (2009), «Замечание о раскраске графов без нечетных K _k -миноров», Журнал комбинаторной теории , серия B, 99 (4): 728–731, doi : 10.1016/j.jctb.2008.12. 001 , МР   2518204
• Каварабаяси, Кеничи ; Тофт, Бьярн (2005), «Любой 7-хроматический граф имеет K ₇ или K _4,4 минорный », Combinatorica , 25 (3): 327–353, doi : 10.1007/s00493-005-0019-1 , S2CID   41451753
• Косточка, А. В. (1984), «Нижняя граница числа Хадвигера графов по их средней степени», Combinatorica , 4 (4): 307–316, doi : 10.1007/BF02579141 , MR   0779891 , S2CID   15736799
• Нешетрил, Ярослав ; Томас, Робин (1985), «Заметки о пространственном представлении графов», Математические заметки Университета Каролины , 26 (4): 655–659, hdl : 10338.dmlcz/106404 , MR   0831801
• Норин, Сергей; Постл, Люк; Сун, Цзы-Ся (2023), «Преодоление барьера вырождения для раскраски графов без $K_{t}$ минор», «Достижения в математике» , 422 , статья № 109020, 23 стр., arXiv : 1910.09378 , doi : 10.1016/j.aim.2023.109020 , MR   4576840
• Пегг, Эд-младший (2002), «Рецензия на книгу: колоссальная книга по математике» (PDF) , Уведомления Американского математического общества , 49 (9): 1084–1086
• Робертсон, Нил ; Сеймур, Пол ; Томас, Робин (1993), «Гипотеза Хадвигера для K ₆ графов, свободных от » (PDF) , Combinatorica , 13 (3): 279–361, doi : 10.1007/BF01202354 , MR   1238823 , S2CID   9608738
• Томасон, Эндрю (1984), «Экстремальная функция для сжатия графов», Mathematical Proceedings of the Cambridge Philosophical Society , 95 (2): 261–265, doi : 10.1017/S0305004100061521 , MR   0735367 , S2CID   124801301
• Томассен, Карстен (1994), «Каждый плоский граф выбираем 5», Журнал комбинаторной теории , серия B, 62 (1): 180–181, doi : 10.1006/jctb.1994.1062 , MR   1290638
• Фойгт, Маргит (1993), «Раскраски списков плоских графов», Discrete Mathematics , 120 (1–3): 215–219, doi : 10.1016/0012-365X(93)90579-I , MR   1235909
• Вагнер, Клаус (1937), «О свойстве плоских комплексов», Mathematical Annals , 114 : 570–590, doi : 10.1007/BF01594196 , S2CID   123534907
• Ю, Синсин; Зикфельд, Флориан (2006), «Сведение гипотезы Хайоса о 4-раскраске к 4-связным графам», Журнал комбинаторной теории, серия B , 96 (4): 482–492, doi : 10.1016/j.jctb.2005.10.001 , МР   2232386