Гипотеза Хадвигера (теория графов) - Hadwiger conjecture (graph theory)

Смотрите также: Гипотеза Хадвигера (комбинаторная геометрия)
Вопрос, Web Fundamentals.svgНерешенная проблема в математике:
Каждый ли график с хроматическое число есть -вертекс полный график как незначительный ?
(больше нерешенных задач по математике)
Граф, который требует четырех цветов любой раскраски и четырех связанных подграфов, которые при сжатии образуют полный граф, иллюстрирующий случай k = 4 гипотезы Хадвигера

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

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

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

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

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

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

Если Fk обозначает семейство графов, обладающее тем свойством, что все миноры графов в Fk может быть (k - 1) -окрашен, то из Теорема Робертсона – Сеймура это Fk можно охарактеризовать конечным набором запрещенные несовершеннолетние. Гипотеза Хадвигера состоит в том, что этот набор состоит из одного запрещенного минора, Kk.

В Число Хадвигера час(г) графа г это размер k наибольшего полного графа Kk это несовершеннолетний г (или, что то же самое, можно получить, стягивая ребра г). Он также известен как кликовое число сокращения из г.[2] Гипотезу Хадвигера можно сформулировать в простой алгебраической форме χ(г) ≤ час(г) где χ(г) обозначает хроматическое число из г.

Частные случаи и частичные результаты

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

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

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

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

Для k = 7, известны некоторые частичные результаты: каждый 7-хроматический граф должен содержать либо K7 несовершеннолетний или оба K4,4 несовершеннолетний и K3,5 незначительный.[4]

Каждый график г имеет вершину с не более чем O (час(г) √журнал час(г)) падающие ребра,[5] откуда следует, что a жадная окраска Алгоритм, который удаляет эту вершину низкой степени, окрашивает оставшийся граф, а затем добавляет обратно удаленную вершину и окрашивает ее, раскрасит данный граф в O (час(г) √журнал час(г)) цвета.

Ван дер Зипен (2012) построил граф ЧАС с участием χ (H) =ω но нет Kω второстепенный, демонстрируя, что гипотеза не для графов со счетно бесконечным числом раскраски.

Обобщения

Дьёрдь Хаджос предположил, что гипотеза Хадвигера может быть усилена до подразделения а не миноры: то есть каждый граф с хроматическим числом k содержит подраздел полного графа Kk. Гипотеза Хаджоса верна для k ≤ 4, но Кэтлин (1979) нашли контрпримеры к этой усиленной гипотезе для k ≥ 7; дела k = 5 и k = 6 остаются открытыми.[6] Эрдеш и Файтлович (1981) заметил, что гипотеза Хаджоса плохо случайные графы: для любого ε> 0 в пределе по числу вершин п, стремится к бесконечности, вероятность приближается к той, что случайный п-вершинный граф имеет хроматическое число ≥ (1/2 - ε)п / журнал2 п, и что его крупнейшее кликовое подразделение имеет не более сп1/2 вершины для некоторой постоянной c. В этом контексте стоит отметить, что вероятность также приближается к той, что случайный п-вершинный граф имеет число Хадвигера, большее или равное его хроматическому числу, поэтому гипотеза Хадвигера верна для случайных графов с высокой вероятностью; точнее, число Хадвигера с большой вероятностью постоянно п/√журналп.[2]

Боровецкий (1993) спросил, можно ли распространить гипотезу Хадвигера на раскраска списка. Для k ≤ 4, каждый граф со списковым хроматическим номером k имеет k-вертикальная клика малая. Однако максимальное хроматическое число плоских графов в списке равно 5, а не 4, поэтому расширение не работает уже для K5-безминорные графы.[7] В целом, для каждого т ≥ 1, существуют графы с числом Хадвигера 3т + 1 и хроматическое число которого равно 4т + 1.[8]

Джерардс и Сеймур предположили, что каждый граф г с хроматическим числом k имеет полный график Kk как странный минор. Такую структуру можно представить как семейство k вершинно-непересекающиеся поддеревья г, каждое из которых двухцветное, так что каждая пара поддеревьев соединена одноцветным ребром. Хотя графики без нечетных Kk несовершеннолетние не обязательно редкий, для них верна такая же верхняя оценка, как и для стандартной гипотезы Хадвигера: граф без нечетных Kk минор имеет хроматический номер χ(г) = O (k√журналk).[9]

Налагая дополнительные условия на г, возможно, удастся доказать наличие несовершеннолетних более крупных, чем Kk. Одним из примеров является теорема Снарка, что каждый кубический граф требуя четырех цветов в любом окраска края имеет Граф Петерсена как несовершеннолетний, по предположению В. Т. Тутте и в 2001 году было объявлено, что оно доказано Робертсоном, Сандерсом, Сеймуром и Томасом.[10]

Заметки

  1. ^ Дистель, Рейнхард, 1959 - Верфассер. (30 июня 2017 г.). Теория графов. ISBN  9783662536216. OCLC  1048203362.CS1 maint: несколько имен: список авторов (ссылка на сайт)
  2. ^ а б c Боллобас, Катлин и Эрдеш (1980).
  3. ^ Нешетржил и Томас (1985).
  4. ^ Существование либо K7 или K3,5 несовершеннолетний был показан Кен-ичи Каварабаяси, и Каварабаяши и Тофт (2005) доказал существование либо K7 или K4,4 незначительный.
  5. ^ Косточка (1984). Буква O в этом выражении вызывает нотация большой O.
  6. ^ Ю и Зикфельд (2006).
  7. ^ Войт (1993); Томассен (1994).
  8. ^ Барат, Жорет и Вуд (2011).
  9. ^ Geelen et al. (2006); Каварабаяси (Журнал комбинаторной теории, серия B, том 99, выпуск 1, январь 2009 г., страницы 20-29).
  10. ^ Пегг, Эд, младший (2002), «Книжное обозрение: колоссальная книга математики» (PDF), Уведомления Американского математического общества, 49 (9): 1084–1086, Bibcode:2002ITED ... 49.1084A, Дои:10.1109 / TED.2002.1003756.

использованная литература