В математической области теории графов число Туэ графа представляет собой вариацию хроматического индекса , определенного Алоном и др. (2002) и назван в честь математика Акселя Туэ , который изучал слова без квадратов, используемые для определения этого числа.
Алон и др. определим неповторяющуюся раскраску графа как присвоение цветов ребрам графа так, что в графе не существует простого пути четной длины , в котором цвета ребер в первой половине пути образуют та же последовательность, что и цвета ребер во второй половине пути. Число Туэ графа — это минимальное количество цветов, необходимое для любой неповторяющейся раскраски. [1]
Вариации этой концепции, включающие раскраску вершин или более общие обходы графа, изучались несколькими авторами, включая Барата и Варью, Барата и Вуда (2005), Брешара и Клавжара (2004), а также Кюндгена и Пельсмайера.
Рассмотрим пятиугольник , то есть цикл из пяти вершин. Если мы раскрасим ребра в два цвета, некоторые два соседних ребра будут иметь один и тот же цвет x; путь, образованный этими двумя краями, будет иметь повторяющуюся последовательность цветов xx. Если мы раскрасим края тремя цветами, один из трех цветов будет использован только один раз; путь четырех ребер, образованный двумя другими цветами, будет либо иметь два последовательных ребра, либо будет формировать повторяющуюся цветовую последовательность xyxy. Однако при четырех цветах избежать всех повторов несложно. Следовательно, число Туэ C 5 равно четырем. [1]
Алон и др. используйте локальную лемму Ловаса, чтобы доказать, что число Туэ любого графа не более чем квадратично в максимальной степени; они приводят пример, показывающий, что для некоторых графов необходима эта квадратичная зависимость. Кроме того, они показывают, что число Туэ пути из четырех или более вершин равно ровно трем, что число Туэ любого цикла не превосходит четырех и что число Туэ графа Петерсена равно ровно пяти. [1]
Известные циклы с номером Туэ четыре: C 5 , C 7 , C 9 , C 10 , C 14 и C 17 . Алон и др. догадайтесь, что число Туэ любого большего цикла равно трем; вычислительно они подтвердили, что перечисленные выше циклы являются единственными циклами длиной ≤ 2001 с номером Туэ четыре. Карри решил эту проблему в статье 2002 года, показав, что все циклы с 18 или более вершинами имеют номер Туэ 3.
Проверка того, имеет ли раскраска повторяющийся путь, находится в NP, поэтому проверка того, является ли раскраска неповторяющейся, находится в co-NP, и Манин показал, что она является co-NP-полной. Задача нахождения такой раскраски принадлежит полиномиальной иерархии , и Манин снова показал, что она полна для этого уровня. Манин (2007)
СМИ, связанные с числом Туэ, на Викискладе?