Теорема Галлаи — Хассе — Роя — Витавера

Теорема Галлаи – Хассе – Роя – Витавера — это вид двойственности между раскрасками вершин заданного неориентированного графа и ориентациями его рёбер. Теорема утверждает, что минимальное число красок, необходимых для правильной раскраски любого графа G, на единицу больше длины максимального пути^[англ.] в ориентации графа G, в которой эта длина пути минимальна^[1]. В ориентации, в которых путь максимальной длины имеет минимальную длину, всегда входит по меньшей мере одна ациклическая ориентация^[2].

Альтернативная формулировка той же теоремы утверждает, что любая ориентация графа с хроматическим числом k содержит простой ориентированный путь с k вершинами^[3]. Можно наложить условия, чтобы путь начинался в любой вершине, и чтобы из этой вершины можно было достичь любую другую вершину ориентированного графа^[4][5].

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

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

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

Чтобы доказать, что хроматическое число меньше либо равно минимальной длине максимального пути, допустим, что граф имеет ориентацию, в которой не более k вершин в любом ориентированном пути для некоторого k. Вершины графа можно раскрасить в k цветов путём выбора максимального ацикличного подграфа ориентации с последующей раскраской каждой вершины цветом с индексом, равным длине максимального по длине пути, идущего в данную вершину. При такой раскраске каждое ребро подграфа ориентировано из вершины с меньшим индексом в вершину с большим индексом, а потому раскраска будет правильной. Для каждого ребра, не принадлежащего подграфу, должен существовать ориентированный путь внутри подграфа, соединяющий эти две вершины в противоположном направлении, в противном случае ребро попало бы в подграф. Таким образом, ребро ориентировано от большего номера к меньшему и не нарушает правильности раскраски^[6].

Доказательство этой теоремы использовал Юрий Владимирович Матиясевич в качестве тестового случая для предлагаемой схемы доказательства в дискретной математике^[7].

Теорема имеет естественную интерпретацию в категориях ориентированных графов и гомоморфизмах графов. Гомоморфизм — это отображение вершин одного графа в вершины другого графа, при котором смежные вершины остаются смежными в образе. Тогда k-раскраска неориентированного графа G может быть описана гомоморфизмом графа G в полный граф K_k. Если в полном графе задать ориентацию, он становится турниром, и эту ориентацию можно использовать для задания ориентации в графе G. В частности, раскраска, заданная длиной наибольшего пути, соответствует гомоморфизму в транзитивный турнир (ациклически ориентированный полный граф), и любая раскраска может быть описана таким гомоморфизмом в транзитивный турнир.

Если рассматривать гомоморфизмы в другом направлении, в G, не из G, ориентированный граф G ацикличен и имеет не более k вершин в самом длинном пути тогда и только тогда, когда не существует гомоморфизма пути P_k + 1 в граф G.

Таким образом, теорема Галлаи – Хассе – Роя – Витавера эквивалентна теореме, что для любого ориентированного графа G тогда и только тогда существует гомоморфизм в транзитивный турнир с k вершинами, когда не существует гомоморфизма из пути с (k + 1) вершинами^[2]. В случае, когда граф G ацикличен, утверждение можно рассматривать как форму теоремы Мирского, что самая длинная цепочка в частично упорядоченном множестве равно минимальному числу антицепочек, на которые можно разбить множество^[8]. Утверждение можно обобщить от путей к другим ориентированным графам — для любого полидерева^[англ.] P существует двойственный ориентированный граф D, такой, что для любого ориентированного графа G существует гомоморфизм из G в D тогда и только тогда, когда не существует изоморфизма из P в G^[9].

Теорема Галлаи – Хассе – Роя – Витавера неоднократно переоткрывалась^[2]. Название теорема получила от отдельных публикаций Т. Галлаи^{[англ.][10]}, М. Хассе^[11], Б. Роя^[12] и Л. М. Витавера^[13]. Рой приписывает формулировку теоремы Клоду Бержу^[англ.], высказавшему её в виде гипотезы в книге по теории графов в 1958^[12].