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

Недоказанное обобщение теоремы о четырех красках

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

Имеет ли каждый граф с хроматическим числом полный граф с -вершиной в качестве минора ? ${\displaystyle k}$ ${\displaystyle k}$

(еще нерешенные проблемы по математике)

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

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

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

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

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

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

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

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

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

Особые случаи и частичные результаты

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

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

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

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

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

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

В 1980-х годах Александр В. Косточка ^[6] и Эндрю Томасон ^[7] независимо доказали, что любой граф без миноров имеет среднюю степень и, таким образом, может быть раскрашен с использованием цветов. Последовательность улучшений этой границы привела к доказательству -раскрашиваемости для графов без миноров. ^[8] ${\displaystyle K_{k}}$ ${\textstyle O(k{\sqrt {\log k}})}$ ${\textstyle O(k{\sqrt {\log k}})}$ ${\displaystyle O(k\log \log k)}$ ${\displaystyle K_{k}}$

Обобщения

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

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

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

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

Примечания

1. Дистель (2017).
2. Bollobás, Catlin & Erdős (1980).
3. Нешетржил и Томас (1985).
4. Существование либо a, либо minor было показано Кенити Каварабаяси , а Каварабаяси и Тофт (2005) доказали существование либо a , либо minor. ${\displaystyle K_{7}}$ ${\displaystyle K_{3,5}}$ ${\displaystyle K_{7}}$ ${\displaystyle K_{4,4}}$
5. Косточка (1984). Буква в этом выражении вызывает обозначение большого О. ${\displaystyle O}$
6. Косточка (1984).
7. Томасон (1984).
8. Делькур и Постл (2024); Норин, Постл и Сонг (2023)
9. Ю и Зикфельд (2006).
10. Фойгт (1993); Томассен (1994).
11. Барат, Жоре и Вуд (2011).
12. Гилен и др. (2006); Каварабаяши (2009).
13. Пегг (2002).

Ссылки

• Барат, Янош; Йорет, Гвенаэль; Вуд, Дэвид Р. (2011), «Опровержение гипотезы Хадвигера о списке», Электронный журнал комбинаторики , 18 (1) P232, arXiv : 1110.2272 , doi : 10.37236/719, S2CID  13822279
• Боллобаш, Б .; Кэтлин, П.А.; Эрдёш, Пол (1980), «Гипотеза Хадвигера верна почти для каждого графа» (PDF) , Европейский журнал комбинаторики , 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
• Делькур, Мишель; Постл, Люк (июль 2024 г.), «Сведение линейной гипотезы Хадвигера к раскраске небольших графов», Журнал Американского математического общества , arXiv : 2108.01633 , doi : 10.1090/jams/1047
• Дистель, Рейнхард (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
• Geelen, Jim ; Gerards, Bert; Reed, Bruce ; Seymour, Paul ; Vetta, Adrian (2006), «О нечетно-минорном варианте гипотезы Хадвигера», Journal of Combinatori Theory, Series B , 99 (1): 20–29, doi :10.1016/j.jctb.2008.03.006
• Хадвигер, Хьюго (1943), «Über eine Klassifikation der Streckkomplexe», Vierteljschr. Натурфорш. Гес. Цюрих , 88 : 133–143.
• Каварабаяси, Кен-ичи (2009), «Заметка о раскраске графов без нечетных K _k -миноров», Журнал комбинаторной теории , Серия B, 99 (4): 728–731, doi : 10.1016/j.jctb.2008.12.001 , MR  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), «Заметки о пространственном представлении графов», Commentationes Mathematicae Universitatis Carolinae , 26 (4): 655–659, hdl :10338.dmlcz/106404, MR  0831801
• Норин, Сергей; Постл, Люк; Сонг, Цзы-Ся (2023), «Преодоление барьера вырожденности для раскраски графов без миноров», Advances in Mathematics , 422 109020, arXiv : 1910.09378 , doi : 10.1016/j.aim.2023.109020, MR  4576840 ${\displaystyle K_{t}}$
• Пегг, Эд младший (2002), «Обзор книги: Колоссальная книга математики» (PDF) , Notices of the American Mathematical Society , 49 (9): 1084–1086
• Робертсон, Нил ; Сеймур, Пол ; Томас, Робин (1993), «Гипотеза Хадвигера для графов, свободных от K6» (PDF) , Combinatorica , 13 (3): 279–361, doi :10.1007/BF01202354, MR  1238823, S2CID  9608738
• Томасон, Эндрю (1984), «Экстремальная функция для стягивания графов», Математические труды Кембриджского философского общества , 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
• Voigt, Margit (1993), «Списочные раскраски планарных графов», Discrete Mathematics , 120 (1–3): 215–219, doi : 10.1016/0012-365X(93)90579-I , MR  1235909
• Вагнер, Клаус (1937), «Über eine Eigenschaft der ebenen Komplexe», Mathematische Annalen , 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 , MR  2232386