Число Туэ
Число Туэ — характеристика графа, особый вариант хроматического индекса. Определяется как минимальное число цветов, необходимое для неповторяющейся раскраски, то есть такого назначения цветов рёбрам графа, что не существует какого-либо простого пути чётной длины в графе, в котором цвета рёбер в первой половине пути образуют ту же последовательность, что и цвета рёбер во второй половине пути.
Введена в 2002 году группой математиков во главе с Нога Алоном[1], название получила по имени Акселя Туэ, который изучал бесквадратные слова, необходимые для строгого определения числа.
Также изучались вариации этой характеристики, использующие раскраску вершин, и, более общо, маршрутов[2][3][4][5].
Пример
Рассмотрим пятиугольник, то есть цикл с пятью вершинами. Если мы раскрасим рёбра двумя цветами, некоторые из двух смежных рёбер будет иметь тот же самый цвет . Путь, формированный этими двумя рёбрами, будет иметь повторяющуюся последовательность цветов . Если выкрасить рёбра тремя цветами, один из трёх цветов будет использован только раз. Путь из четырёх рёбер, образованный другими двумя цветами, либо будет иметь последовательные ребра с одним цветом, либо образуют повторяющуюся последовательность . С четырьмя же цветами нетрудно избежать повторений, поэтому число Туэ цикла равно четырём.
Результаты
Алон с соавторами использовали локальную лемму Ловаса для доказательства, что число Туэ любого графа не больше квадрата его максимальной степени. Они дали пример, показывающий, что для некоторых графов эта квадратичная зависимость необходима. Кроме того, они показали, что число Туэ пути из четырёх и более вершин равно в точности трём, число Туэ любого цикла не превосходит четырёх, а число Туэ графа Петерсена равна в точности пяти.
Известные циклы с числом Туэ четыре — это , , ', , , . Алон с соавторами высказали гипотезу, что число Туэ любого большего цикла равно трём. Путём вычислительной проверки они убедились, что перечисленные выше циклы являются единственными с числом Туэ четыре среди циклов длины . В 2002 году показано, что все циклы длиной 18 и более имеют число Туэ 3[6].
Вычислительная сложность
Проверка, имеет ли раскраска повторяющийся путь, NP-полна, так что проверка, является ли раскраска неповторяющейся, содержится в классе co-NP и Фёдор Манин показал, что она co-NP-полна. Задача нахождения такой раскраски принадлежит в полиномиальной иерархии, и также Маниным доказано, что она полна для этого уровня.
Примечания
Литература
- Noga Alon, Jaroslaw Grytczuk, Mariusz Hałuszczak, Oliver Riordan. Nonrepetitive colorings of graphs // Random Structures & Algorithms. — 2002. — Т. 21, вып. 3–4. — С. 336–346. — doi:10.1002/rsa.10057.
- János Barát, Varjú P. P. On square-free edge colorings of graphs // Ars Combinatoria. — 2008. — Т. 87. — С. 377–383.
- János Barát, David Wood. Notes on nonrepetitive graph colouring // Electronic Journal of Combinatorics. — 2005. — Т. 15, вып. 1. — arXiv:math.CO/0509608.
- Boštjan Brešar, Sandi Klavžar. Square-free coloring of graphs // Ars Combin.. — 2004. — Т. 70. — С. 3–13.
- James D. Currie. There are ternary circular square-free words of length n for n ≥ 18 // Electronic Journal of Combinatorics. — 2002. — Т. 9, вып. 1.
- Jarosław Grytczuk. Nonrepetitive colorings of graphs—a survey // International Journal of Mathematics and Mathematical Sciences. — 2007.
- André Kündgen, Michael J. Pelsmajer. Nonrepetitive colorings of graphs of bounded tree-width // Discrete Mathematics. — 2008. — Т. 308, вып. 19. — С. 4473–4478. — doi:10.1016/j.disc.2007.08.043.
- Fedor Manin. The complexity of nonrepetitive edge coloring of graphs. — 2007. — . — arXiv:0709.4497.
- Marcus Schaefer, Christopher Umans. Completeness in the polynomial-time hierarchy: a compendium. — 2005. Архивировано 3 марта 2016 года.