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

Число Туэ 5-цикла равно четырём.

Введена в 2002 году группой математиков во главе с Нога Алоном[1], название получила по имени Акселя Туэ, который изучал бесквадратные слова, необходимые для строгого определения числа.

Также изучались вариации этой характеристики, использующие раскраску вершин, и, более общо, маршрутов[2][3][4][5].

Пример

править

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

Результаты

править

Алон с соавторами использовали локальную лемму Ловаса для доказательства, что число Туэ любого графа не больше квадрата его максимальной степени. Они дали пример, показывающий, что для некоторых графов эта квадратичная зависимость необходима. Кроме того, они показали, что число Туэ пути из четырёх и более вершин равно в точности трём, число Туэ любого цикла не превосходит четырёх, а число Туэ графа Петерсена равна в точности пяти.

Известные циклы с числом Туэ четыре — это  ,  ,  ',  ,  ,  . Алон с соавторами высказали гипотезу, что число Туэ любого большего цикла равно трём. Путём вычислительной проверки они убедились, что перечисленные выше циклы являются единственными с числом Туэ четыре среди циклов длины  . В 2002 году показано, что все циклы длиной 18 и более имеют число Туэ 3[6].

Вычислительная сложность

править

Проверка, имеет ли раскраска повторяющийся путь, NP-полна, так что проверка, является ли раскраска неповторяющейся, содержится в классе co-NP и Фёдор Манин показал, что она co-NP-полна. Задача нахождения такой раскраски принадлежит   в полиномиальной иерархии, и также Маниным доказано, что она полна для этого уровня.

Примечания

править

Литература

править