Thue number

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

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

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

• 1 Пример
• 2 Результаты
• 3 Вычислительная сложность
• 4 Ссылки
• 5 Внешние ссылки

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

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

Известные циклы с четвертым номером: C 5, C 7, C 9, C 10, C 14 и C 17. Алон и др. предположить, что число Туэ любого большего цикла равно трем; они проверили с помощью вычислений, что перечисленные выше циклы являются единственными циклами длины ≤ 2001 с числом Туэ четыре. Карри решил эту проблему в статье 2002 года, показав, что все циклы с 18 или более вершинами имеют число Туэ 3.

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

• Алон, Нога ; Грычук, Ярослав; Халущак, Мариуш; Риордан, Оливер (2002). «Разовые раскраски графиков» (PDF). Случайные структуры и алгоритмы. 21 (3–4): 336–346. дои : 10.1002 / rsa.10057. MR 1945373.
• Барат, Янош; Варжу, П. П. (2008). «О бесквадратной раскраске ребер графов». Ars Combinatoria. 87 : 377–383. MR 2414029.
• Барат, Янош; Вуд, Дэвид (2005). «Замечания о неповторяющейся раскраске графов». Электронный журнал комбинаторики. 15 (1). R99. arXiv : math.CO/0509608. MR 2426162.
• Брешар, Боштьян; Клавжар, Санди (2004). «Бесквадратная раскраска графов». Ars Combin. 70 : 3–13. MR 2023057.
• Карри, Джеймс Д. (2002). «Существуют троичные круговые слова без квадратов длины n для n ≥ 18». Электронный журнал комбинаторики. 9 (1). N10. MR 1936865.
• Грычук, Ярослав (2007). «Неповторяющиеся раскраски графиков - обзор». Международный журнал математики и математических наук. Изобразительное искусство. ID 74639. MR 2272338.
• Кюндген, Андре; Пельсмайер, Майкл Дж. (2008). «Неповторяющиеся раскраски графов ограниченной древовидной ширины». Дискретная математика. 308 (19): 4473–4478. doi : 10.1016 / j.disc.2007.08.043. MR 2433774.
• Манин, Федор (2007). «Сложность неповторяющейся раскраски ребер графов». arXiv : 0709.4497. Bibcode : 2007arXiv0709.4497M. Для цитирования журнала требуется | journal =()
• Шефер, Маркус; Уманс, Кристофер (2005). «Полнота в иерархии полиномиального времени: сборник». Для цитирования журнала требуется | journal =()

• СМИ относится к номер Ту на Wikimedia Commons