Номер вторника

Число Туэ 5-го цикла — четыре.

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

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

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

Пример

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

Результаты

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

Известные циклы с номером Туэ четыре: C ₅ , C ₇ , C ₉ , C ₁₀ , C ₁₄ и C ₁₇ . Алон и др. догадайтесь, что число Туэ любого большего цикла равно трем; они вычислительным путем подтвердили, что перечисленные выше циклы являются единственными циклами длиной ≤ 2001 с номером Туэ четыре. Карри решил эту проблему в статье 2002 года, показав, что все циклы с 18 или более вершинами имеют номер Туэ 3.

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

Проверка того, имеет ли раскраска повторяющийся путь, находится в NP, поэтому проверка того, является ли раскраска неповторяющейся, находится в co-NP, и Манин показал, что она является co-NP-полной. Задача нахождения такой раскраски принадлежит $\Sigma _{2}^{P}$ в полиномиальной иерархии , и вновь Манин показал, что она полна для этого уровня. Манин (2007)

Ссылки

• Алон, Нога ; Гричук, Ярослав; Халущак, Мариуш; Риордан, Оливер (2002). «Неповторяющиеся раскраски графов» (PDF) . Случайные структуры и алгоритмы . 21 (3–4): 336–346. дои : 10.1002/rsa.10057 . МР   1945373 . S2CID   5724512 .
• Друг, Джон; Ворона, ПП (2008). «О бесквадратных раскрасках графов» . Арс Комбинатория . 87 : 377–383. МР   2414029 .
• Барат, Янош; Вуд, Дэвид (2005). «Заметки о неповторяющейся раскраске графов». Электронный журнал комбинаторики . 15 (1). 99 рэндов. arXiv : math.CO/0509608 . Бибкод : 2005math......9608B . МР   2426162 .
• Брешар, Боштян; Клавжар, Санди (2004). «Бесквадратная раскраска графов». Арс Комбин . 70 : 3–13. МР   2023057 .
• Карри, Джеймс Д. (2002). «Существуют троичные круглые слова без квадратов длины n для n ≥ 18» . Электронный журнал комбинаторики . 9 (1). №10. дои : 10.37236/1671 . МР   1936865 .
• Гричук, Ярослав (2007). «Неповторяющиеся раскраски графов — обзор» . Международный журнал математики и математических наук . 2007 . Искусство. ID 74639. doi : 10.1155/2007/74639 . МР   2272338 .
• Кюндген, Андре; Пелсмайер, Майкл Дж. (2008). «Неповторяющиеся раскраски графов ограниченной древовидной ширины». Дискретная математика . 308 (19): 4473–4478. дои : 10.1016/j.disc.2007.08.043 . МР   2433774 .
• Манин, Федор (2007). «Сложность неповторяющейся рёберной раскраски графов». arXiv : 0709.4497 [ cs.CC ].
• Шефер, Маркус; Уманс, Кристофер (2005). «Полнота в иерархии полиномиального времени: сборник» .

Внешние ссылки

• СМИ, связанные с числом Туэ, на Викискладе?