Гипотеза Хадвигера: обобщение теоремы о четырёх красках

Введение

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

В теории графов гипотеза Хадвигера утверждает, что если граф лишен петель и не имеет K5-минора, то его хроматическое число удовлетворяет χ(G) ≤ ω(G). Известно, что она верна для полных графов. Гипотеза является обобщением теоремы о четырех красках и считается одной из важнейших и сложнейших нерешенных проблем в этой области. Более конкретно, если все правильные раскраски неориентированного графа G используют не менее k цветов, то можно найти k непересекающихся связных подграфов в G, таких что каждый подграф соединен ребром с каждым другим подграфом. Сжатие ребер внутри каждого из этих подграфов так, чтобы каждый подграф схлопнулся в одну вершину, приводит к полному графу Kk на k вершинах как минору G.

Эта гипотеза, являющаяся далеко идущим обобщением задачи о четырех красках, была сформулирована Хьюго Хадвигером в 1943 году и до сих пор остается нерешенной. Её называют "одной из самых глубоких нерешенных проблем в теории графов".

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

Эквивалентная формулировка гипотезы Хадвигера (контрапозиция к вышеприведенной формулировке) заключается в том, что если не существует последовательности сжатия ребер (каждое из которых объединяет два конца некоторого ребра в одну супервершину), приводящей граф к полному графу , то граф должен иметь раскраску в цветов. В минимальной раскраске любого графа, сжатие каждого цветового класса раскраски в одну вершину порождает полный граф. Однако этот процесс сжатия не дает минор, поскольку (по определению) между любыми двумя вершинами в одном и том же цветовом классе нет ребер, следовательно, сжатие не является сжатием ребер (которое необходимо для миноров). Гипотеза Хадвигера утверждает, что существует другой способ корректного сжатия реберных множеств вершин в отдельные вершины, создавая полный граф , таким образом, чтобы все сжатые множества были связными. Если обозначает семейство графов, обладающих свойством, что все миноры графов из можно раскрасить в цветов, то из теоремы Робертсона — Сеймура следует, что можно охарактеризовать конечным множеством запрещенных миноров. Гипотеза Хадвигера состоит в том, что этот набор состоит из одного запрещенного минора. Хадвигеровский номер графа — это размер наибольшего полного графа , являющегося минором (или, эквивалентно, получаемого сжатием ребер ). Он также известен как число сжатой клики . Гипотезу Хадвигера можно выразить в простой алгебраической форме , где обозначает хроматическое число .

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

Это тривиально: граф требует более одного цвета, если и только если у него есть ребро, и это ребро само по себе является минором. Случай с тремя цветами также прост: графы, требующие трех цветов, — это недвудольные графы, и каждый недвудольный граф имеет нечетный цикл, который можно сжать до 3-цикла, то есть минора. В той же статье, в которой он представил гипотезу, Хадвигер доказал ее истинность для графов, не имеющих миноров — это последовательно-параллельные графы и их подграфы. Каждый граф этого типа имеет вершину, инцидентную не более чем двум ребрам; любой такой граф можно 3-раскрасить, удалив одну из таких вершин, рекурсивно раскрасив оставшийся граф, а затем добавив обратно и раскрасив удаленную вершину. Поскольку удаленная вершина имеет не более двух ребер, один из трех цветов всегда будет доступен для ее раскраски при добавлении обратно. Истинность гипотезы для влечет за собой теорему о четырех красках: ведь если гипотеза верна, то каждый граф, требующий пяти или более цветов, будет иметь минор и, следовательно (по теореме Вагнера), будет непланарным. Клаус Вагнер доказал в 1937 году, что это утверждение на самом деле эквивалентно теореме о четырех красках, и поэтому мы теперь знаем, что оно верно. Как показал Вагнер, каждый граф, не имеющий минора, можно разложить посредством сумм клик на части, которые либо планарны, либо являются 8-вершинной лестницей Мёбиуса, и каждую из этих частей можно раскрасить в 4 цвета независимо друг от друга, поэтому 4-раскрашиваемость графа, свободного от миноров, следует из 4-раскрашиваемости каждой из планарных частей. доказал гипотезу для , также используя теорему о четырех красках; их статья с этим доказательством получила премию Фулкерсона в 1994 году. Из их доказательства следует, что графы, допускающие безсвязное вложение (трехмерный аналог планарных графов), имеют хроматическое число не более пяти. В связи с этим результатом, гипотеза, как известно, верна для , но она остается нерешенной для всех .
Для известны некоторые частные результаты: каждый 7-хроматический граф должен содержать либо минор, либо минор и минор. Каждый граф имеет вершину, инцидентную не более чем ребрам, из чего следует, что жадный алгоритм раскраски, который удаляет эту вершину малой степени, раскрашивает оставшийся граф, а затем добавляет обратно удаленную вершину и раскрашивает ее, раскрасит данный граф цветами. В 1980-х годах Александр В. Косточка и Эндрю Томасон независимо доказали, что каждый граф, не имеющий минора, имеет среднюю степень и, следовательно, может быть раскрашен с использованием цветов. Последовательность улучшений этой границы привела к доказательству -раскрашиваемости графов без миноров.

The case is trivial: a graph requires more than one color if and only if it has an edge, and that edge is itself a minor. The case is also easy: the graphs requiring three colors are the non bipartite graphs, and every non bipartite graph has an odd cycle, which can be contracted to a 3 cycle, that is, a minor. In the same paper in which he introduced the conjecture, Hadwiger proved its truth for The graphs with no minor are the series–parallel graphs and their subgraphs. Each graph of this type has a vertex with at most two incident edges; one can 3 color any such graph by removing one such vertex, coloring the remaining graph recursively, and then adding back and coloring the removed vertex. Because the removed vertex has at most two edges, one of the three colors will always be available to color it when the vertex is added back. The truth of the conjecture for implies the four color theorem: for, if the conjecture is true, every graph requiring five or more colors would have a minor and would (by Wagner's theorem) be nonplanar. Klaus Wagner proved in 1937 that the case is actually equivalent to the four color theorem and therefore we now know it to be true. As Wagner showed, every graph that has no minor can be decomposed via clique sums into pieces that are either planar or an 8 vertex Möbius ladder, and each of these pieces can be 4 colored independently of each other, so the 4 colorability of a minor free graph follows from the 4 colorability of each of the planar pieces. proved the conjecture for , also using the four color theorem; their paper with this proof won the 1994 Fulkerson Prize. It follows from their proof that linklessly embeddable graphs, a three dimensional analogue of planar graphs, have chromatic number at most five. Due to this result, the conjecture is known to be true for , but it remains unsolved for all
For , some partial results are known: every 7 chromatic graph must contain either a minor or both a minor and a minor. Every graph has a vertex with at most incident edges, from which it follows that a greedy coloring algorithm that removes this low degree vertex, colors the remaining graph, and then adds back the removed vertex and colors it, will color the given graph with colors. In the 1980s, Alexander V. Kostochka and Andrew Thomason both independently proved that every graph with no minor has average degree and can thus be colored using colors. A sequence of improvements to this bound have led to a proof of colorability for graphs without minors.

Обобщения

Гиорги Хаёс предположил, что гипотезу Хадвигера можно усилить до подразделений, а не миноров: то есть, что каждый граф с хроматическим числом *k* содержит подразделение полного графа *Kk*. Гипотеза Хаёса верна для *k* = 2, но найдены контрпримеры к этой усиленной гипотезе для *k* ≥ 3; случаи *k* = 3 и *k* = 4 остаются открытыми. Отмечено, что гипотеза Хаёса плохо работает для случайных графов: для любого *k*, в пределе, когда число вершин *n* стремится к бесконечности, вероятность приближается к единице, что случайный *n*-вершинный граф имеет хроматическое число *k*, и что его наибольшее подразделение клики имеет *k* вершин. В этом контексте стоит отметить, что вероятность также приближается к единице, что случайный *n*-вершинный граф имеет число Хадвигера больше или равное его хроматическому числу, поэтому гипотеза Хадвигера выполняется для случайных графов с высокой вероятностью; точнее, число Хадвигера с высокой вероятностью пропорционально *n*.

György Hajós conjectured that Hadwiger's conjecture could be strengthened to subdivisions rather than minors: that is, that every graph with chromatic number contains a subdivision of a complete graph Hajós' conjecture is true for , but found counterexamples to this strengthened conjecture for ; the cases and remain observed that Hajós' conjecture fails badly for random graphs: for any , in the limit as the number of vertices, , goes to infinity, the probability approaches one that a random vertex graph has chromatic number , and that its largest clique subdivision has vertices. In this context, it is worth noting that the probability also approaches one that a random vertex graph has Hadwiger number greater than or equal to its chromatic number, so the Hadwiger conjecture holds for random graphs with high probability; more precisely, the Hadwiger number is with high probability proportional

asked whether Hadwiger's conjecture could be extended to list coloring. For , every graph with list chromatic number has a vertex clique minor. However, the maximum list chromatic number of planar graphs is 5, not 4, so the extension fails already for minor free graphs. More generally, for every , there exist graphs whose Hadwiger number is and whose list chromatic number

Gerards and Seymour conjectured that every graph with chromatic number has a complete graph as an odd minor. Such a structure can be represented as a family of vertex disjoint subtrees of , each of which is two colored, such that each pair of subtrees is connected by a monochromatic edge. Although graphs with no odd minor are not necessarily sparse, a similar upper bound holds for them as it does for the standard Hadwiger conjecture: a graph with no odd minor has chromatic number
By imposing extra conditions on , it may be possible to prove the existence of larger minors than One example is the snark theorem, that every cubic graph requiring four colors in any edge coloring has the Petersen graph as a minor, conjectured by W. T. Tutte and announced to be proved in 2001 by Robertson, Sanders, Seymour, and Thomas.

Спросили, можно ли расширить гипотезу Хадвигера на раскраску списками. Для *k* = 2, каждый граф с хроматическим числом раскраски списками имеет 2-вершинный минор клики. Однако максимальное хроматическое число раскраски списками планарных графов равно 5, а не 4, поэтому расширение уже не работает для графов, не имеющих миноров *K5*. В более общем случае, для каждого *k*, существуют графы, число Хадвигера которых равно *k*, а хроматическое число раскраски списками больше *k*.

Герардс и Сеймур предположили, что каждый граф с хроматическим числом *k* имеет полный граф *Kk* как нечётный минор. Такую структуру можно представить как семейство *k* непересекающихся поддеревьев *T1, ..., Tk* графа *G*, каждое из которых двуцветно, так что каждая пара поддеревьев соединена монохромным ребром. Хотя графы, не имеющие нечётных миноров *Kk*, не обязательно разрежены, для них действует аналогичная верхняя граница, как и для стандартной гипотезы Хадвигера: граф, не имеющий нечётного минора *Kk*, имеет хроматическое число не более *f(k)*.

Налагая дополнительные условия на *G*, возможно доказать существование миноров большего размера. Одним из примеров является теорема о снарках, согласно которой каждый кубический граф, требующий четыре цвета в любом раскраске рёбер, имеет граф Петерсена как минор, что было предположено В. Т. Тутте и доказано в 2001 году Робертсоном, Сандерсом, Сеймуром и Томасом.