Строительство Hajós

В теории графов , разделе математики, построение Хайоша — это операция над графами, названная в честь Дьёрдя Хайоша  (1961), которая может быть использована для построения любого критического графа или любого графа, хроматическое число которого равно по крайней мере некоторому заданному пороговому значению.

Пусть G и H — два неориентированных графа , vw — ребро G , а xy — ребро H. Тогда конструкция Хайоша образует новый граф, который объединяет два графа, отождествляя вершины v и x в одну вершину, удаляя два ребра vw и xy и добавляя новое ребро wy .

Например, пусть G и H каждый — полный граф K ₄ на четырех вершинах; из-за симметрии этих графов выбор того, какое ребро выбрать из каждого из них, не важен. В этом случае результатом применения конструкции Хайоша является веретено Мозера , граф единичных расстояний с семью вершинами , требующий четырех цветов.

В качестве другого примера, если G и H являются графами-циклами длины p и q соответственно, то результатом применения конструкции Хайоша является сам граф-цикл длиной p + q − 1 .

Граф G называется k - конструктивным (или Hajós- k -конструктивным), если он образован одним из следующих трех способов: ^[1]

• Полный граф K _k является k -конструируемым.
• Пусть G и H — любые два k -конструируемых графа. Тогда граф, образованный применением конструкции Хайоша к G и H, является k -конструируемым.
• Пусть G — любой k -конструируемый граф, и пусть u и v — любые две несмежных вершины в G. Тогда граф, образованный объединением u и v в одну вершину, также является k -конструируемым. Эквивалентно, этот граф может быть образован добавлением ребра uv к графу и последующим его стягиванием .

Легко проверить, что каждый k -конструируемый граф требует по крайней мере k цветов в любой правильной раскраске графа . Действительно, это ясно для полного графа K _k , и эффект идентификации двух несмежных вершин заключается в том, чтобы заставить их иметь одинаковый цвет друг с другом в любой раскраске, что не уменьшает количество цветов. В самой конструкции Хайоша новое ребро wy заставляет по крайней мере одну из двух вершин w и y иметь цвет, отличный от объединенной вершины для v и x , поэтому любая правильная раскраска объединенного графа приводит к правильной раскраске одного из двух меньших графов, из которых он был сформирован, что снова заставляет его требовать k цветов. ^[1]

Хайош доказал более строго, что граф требует по крайней мере k цветов, в любой правильной раскраске , тогда и только тогда, когда он содержит k -конструируемый граф как подграф. Эквивалентно, каждый k -критический граф (граф, который требует k цветов, но для которого каждый правильный подграф требует меньше цветов) является k -конструируемым. ^[2] Альтернативно, каждый граф, который требует k цветов, может быть сформирован путем объединения построения Хайоша, операции идентификации любых двух несмежных вершин и операций добавления вершины или ребра к данному графу, начиная с полного графа K _k . ^[3]

Аналогичную конструкцию можно использовать для раскраски списка вместо раскраски. ^[4]

Для k = 3 каждый k -критический граф (то есть каждый нечетный цикл) может быть сгенерирован как k -конструируемый граф, такой что все графы, образованные при его построении, также являются k -критическими. Для k = 8 это неверно: граф, найденный Кэтлином (1979) как контрпример к гипотезе Хайоша о том, что k -хроматические графы содержат подразделение K _k , также служит контрпримером к этой проблеме. Впоследствии k -критические, но не k -конструируемые графы исключительно через k -критические графы были найдены для всех k ≥ 4 . Для k = 4 одним из таких примеров является граф, полученный из графа додекаэдра путем добавления нового ребра между каждой парой антиподальных вершин ^[5]

Поскольку объединение двух несмежных вершин уменьшает количество вершин в результирующем графе, количество операций, необходимых для представления заданного графа G с использованием операций, определенных Хайошем, может превысить количество вершин в G. ^[6]

Более конкретно, Мэнсфилд и Уэлш (1982) определяют число Хайоша h ( G ) k -хроматического графа G как минимальное число шагов, необходимых для построения G из K _k , где каждый шаг формирует новый граф путем объединения двух ранее сформированных графов, слияния двух несмежных вершин ранее сформированного графа или добавления вершины или ребра к ранее сформированному графу. Они показали, что для n -вершинного графа G с m ребрами h ( G ) ≤ 2 ^{n 2 /3 − m + 1} − 1 . Если бы каждый граф имел полиномиальное число Хайоша, это означало бы, что можно доказать нераскрашиваемость за недетерминированное полиномиальное время , и, следовательно, подразумевать, что NP =  co-NP , вывод, который теоретики сложности считают маловероятным. ^[7] Однако неизвестно, как доказать неполиномиальные нижние границы числа Хайоша, не делая некоторых предположений теории сложности, и если бы такую ​​границу можно было доказать, это также означало бы существование неполиномиальных границ для определенных типов систем Фреге в математической логике . ^[7]

Минимальный размер дерева выражения, описывающего конструкцию Хайоша для данного графа G , может быть значительно больше числа Хайоша для G , поскольку кратчайшее выражение для G может повторно использовать одни и те же графы несколько раз, что не допускается в дереве выражения. Существуют 3-хроматические графы, для которых наименьшее такое дерево выражения имеет экспоненциальный размер. ^[8]

Koester (1991) использовал конструкцию Hajós для генерации бесконечного множества 4-критических полиэдральных графов , каждый из которых имел более чем в два раза больше ребер, чем вершин. Аналогично, Liu & Zhang (2006) использовали конструкцию, начиная с графа Grötzsch , для генерации множества 4-критических графов без треугольников , которые, как они показали, трудно раскрасить с помощью традиционных алгоритмов обратного отслеживания .

В полиэдральной комбинаторике Эйлер (2003) использовал конструкцию Хайоша для генерации граней устойчивого множества многогранников .

• Кэтлин, П. А. (1979), «Гипотеза Хайоша о раскраске графов: вариации и контрпримеры», Журнал комбинаторной теории , Серия B, 26 (2): 268–274, doi : 10.1016/0095-8956(79)90062-5.
• Дистель, Рейнхард (2006), Теория графов, Graduate Texts in Mathematics, т. 173 (3-е изд.), Springer-Verlag, стр. 117–118, ISBN 978-3-540-26183-4.
• Эйлер, Рейнхардт (2003), «Конструкция Хайоша и многогранники», Комбинаторная оптимизация — Эврика, вы сокращаетесь! , Конспект лекций по информатике, т. 2570, Берлин: Springer-Verlag, стр. 39–47, doi :10.1007/3-540-36478-1_6, ISBN 978-3-540-00580-3, г-н  2163949.
• Гравье, Сильвен (1996), «Теорема типа Хайоша для раскраски списков», Дискретная математика , 152 (1–3): 299–302, doi : 10.1016/0012-365X(95)00350-6 , MR  1388650.
• Хайос, Г. (1961), «Über eine Konstruktion nicht n -färbbarer Graphen», Wiss. З. Мартин-Лютер-Унив. Галле-Виттенберг Math.-Natur. Рейхе , 10 : 116–117.. Как цитируют Дженсен и Тофт (1994).
• Ивама, Казуо ; Питасси, Тониан (1995), «Экспоненциальные нижние оценки для древовидного исчисления Хайоша», Information Processing Letters , 54 (5): 289–294, doi :10.1016/0020-0190(95)00035-B, MR  1336013.
• Йенсен, Томми Р.; Ройл, Гордон Ф. (1999), «Конструкции критических графов по Хайосу», Журнал теории графов , 30 (1): 37–50, doi :10.1002/(SICI)1097-0118(199901)30:1<37::AID-JGT5>3.0.CO;2-V, MR  1658542.
• Дженсен, Томми Р.; Тофт, Бьярне (1994), Проблемы раскраски графов (2-е изд.), John Wiley and Sons, ISBN 978-0-471-02865-9.
• Кестер, Герхард (1991), «О 4-критических планарных графах с высокой плотностью ребер», Дискретная математика , 98 (2): 147–151, doi : 10.1016/0012-365X(91)90039-5 , MR  1144633.
• Кубале, Марек (2004), Раскраска графов, Contemporary Mathematics, т. 352, Американское математическое общество, стр. 156, ISBN 978-0-8218-3458-9.
• Лю, Шэн; Чжан, Цзянь (2006), «Использование конструкции Хайоша для генерации примеров трехцветной раскраски сложных графов», Искусственный интеллект и символьные вычисления , Конспект лекций по информатике, т. 4120, Springer-Verlag, стр. 211–225, doi :10.1007/11856290_19, ISBN 978-3-540-39728-1.
• Мэнсфилд, А. Дж.; Уэлш, Д. Дж. А. (1982), «Некоторые проблемы раскраски и их сложность», Теория графов (Кембридж, 1981) , North-Holland Math. Stud., т. 62, Амстердам: North-Holland, стр. 159–170, MR  0671913.
• Питасси, Тонианн ; Уркхарт, Аласдер (1995), «Сложность исчисления Хайоса», SIAM Journal on Discrete Mathematics , 8 (3): 464–483, CiteSeerX  10.1.1.30.5879 , doi : 10.1137/S089548019224024X, MR  1341550.