Радужная раскраска

В теории графов путь , в графе с раскрашенными ребрами называется радужным если ни один цвет на нем не повторяется. Граф называется радужно-связным (или радужным ), если между каждой парой его вершин существует радужный путь . Если между каждой парой вершин существует кратчайший путь радуги , граф называется сильно радужным (или сильно радужным ). ^[1]

Определения и границы

Число радужных связей графа $G$ минимальное количество цветов, необходимое для соединения радуги $G$ , и обозначается ${\text{rc}}(G)$ . Аналогично, число сильной радужной связности графа $G$ минимальное количество цветов, необходимое для прочного соединения радуги $G$ , и обозначается ${\text{src}}(G)$ . Ясно, что каждая сильная радужная раскраска также является радужной раскраской, а обратное, вообще говоря, неверно.

Легко заметить, что для радужной связи любого связного графа $G$ , нам нужно как минимум ${\text{diam}}(G)$ цвета, где ${\text{diam}}(G)$ это диаметр $G$ (т.е. длина самого длинного кратчайшего пути). С другой стороны, мы никогда не сможем использовать больше, чем $m$ цвета, где $m$ обозначает количество ребер в $G$ . Наконец, поскольку каждый сильно радужно-связный граф является радужно-связным, мы имеем ${\text{diam}}(G)\leq {\text{rc}}(G)\leq {\text{src}}(G)\leq m$ .

Ниже приведены крайние случаи: ^[1]

${\text{rc}}(G)={\text{src}}(G)=1$ тогда и только тогда, когда $G$ представляет собой полный граф .
${\text{rc}}(G)={\text{src}}(G)=m$ тогда и только тогда, когда $G$ это дерево .

Из вышеизложенного видно, что по числу вершин верхняя граница ${\text{rc}}(G)\leq n-1$ вообще лучшее из возможного. На самом деле, раскраска радуги с помощью $n-1$ цвета можно получить, раскрасив ребра остовного дерева $G$ в разных цветах. Остальные неокрашенные края раскрашиваются произвольно, без введения новых цветов. Когда $G$ 2-связен, мы имеем это ${\text{rc}}(G)\leq \lceil n/2\rceil$ . ^[2] Более того, это жестко, о чем свидетельствуют, например, нечетные циклы.

Точные номера соединений радуги или сильной радуги.

Число радужных или сильных радужных связей было определено для некоторых классов структурированных графов:

${\text{rc}}(C_{n})={\text{src}}(C_{n})=\lceil n/2\rceil$ , для каждого целого числа $n\geq 4$ , где $C_{n}$ это граф цикла . ^[1]
${\text{rc}}(W_{n})=3$ , для каждого целого числа $n\geq 7$ , и ${\text{src}}(W_{n})=\lceil n/3\rceil$ , для $n\geq 3$ , где $W_{n}$ это график колеса . ^[1]

Сложность

Проблема принятия решения о том, ${\text{rc}}(G)=2$ для данного графа $G$ является NP-полной . ^[3] Потому что ${\text{rc}}(G)=2$ тогда и только тогда, когда ${\text{src}}(G)=2$ , ^[1] из этого следует, что решение, если ${\text{src}}(G)=2$ является NP-полным для данного графа $G$ .

Варианты и обобщения

Шартран, Окамото и Чжан ^[4] обобщил число радужных связей следующим образом. Позволять $G$ — нетривиальный связный граф с раскрашенными ребрами порядка $n$ . Дерево $T$ является радужным деревом , если у него нет двух ребер $T$ присвоены одинаковые цвета. Позволять $k$ быть фиксированным целым числом с $2\leq k\leq n$ . Краевая окраска $G$ называется $k$ -радужная раскраска, если для каждого набора $S$ из $k$ вершины $G$ , там есть радужное дерево $G$ содержащие вершины $S$ . $k$ -индекс радуги ${\text{rx}}_{k}(G)$ из $G$ минимальное количество цветов, необходимое в $k$ -радужная раскраска $G$ . А $k$ -раскраска радугой с помощью ${\text{rx}}_{k}(G)$ цвета называется минимумом $k$ -радужная раскраска . Таким образом ${\text{rx}}_{2}(G)$ это число радужных соединений $G$ .

Радужная связь также изучалась в графах, раскрашенных вершинами. Это понятие было введено Кривелевичем и Юстером. ^[5]Здесь радужное число связностей вершин графа $G$ , обозначенный ${\text{rvc}}(G)$ , — минимальное количество цветов, необходимое для раскрашивания $G$ так, что для каждой пары вершин существует соединяющий их путь, внутренним вершинам которого присвоены разные цвета.

См. также

Радужное соответствие

Примечания

Ссылки

Шартран, Гэри ; Джонс, Гарри Л.; МакКеон, Кэтлин А.; Чжан, Пин (2008), «Радужная связь в графах», Mathematica Bohemica , 133 (1): 85–98, doi : 10.21136/MB.2008.133947 .
Шартран, Гэри ; Окамото, Футаба; Чжан, Пинг (2010), «Радужные деревья в графах и обобщенная связность», Networks , 55 (4): NA, doi : 10.1002/net.20339 , S2CID 7505197 .
Чакраборти, Сурав; Фишер, Эльдар; Матслия, Арье; Юстер, Рафаэль (2011), «Твердость и алгоритмы радужного соединения», Journal of Combinatorial Optimization , 21 (3): 330–347, arXiv : 0809.2493 , doi : 10.1007/s10878-009-9250-9 , S2CID 10874392 .
Кривелевич Михаил ; Юстер, Рафаэль (2010), «Радужная связь графа (в большинстве случаев) обратна его минимальной степени», Journal of Graph Theory , 63 (3): 185–191, doi : 10.1002/jgt.20418 .
Ли, Сюэлян; Ши, Юнтан; Сунь, Юэфан (2013), «Радужные связи графов: обзор», Graphs and Combinatorics , 29 (1): 1–38, arXiv : 1101.5747 , doi : 10.1007/s00373-012-1243-2 , S2CID 253898232 .
Ли, Сюэлян; Сунь, Юефан (2012), Радужные связи графов , Springer, стр. 103, ISBN 978-1-4614-3119-0 .
Экстайн, Ян; Голуб, Перемышль; Кайзер, Томас; Кох, Мария; Камачо, Стефан Матос; Рыячек, Зденек; Ширмейер, Инго (2013), «Радужное число связностей 2-связных графов», Discrete Mathematics , 313 (19): 1884–1892, arXiv : 1110.5736 , doi : 10.1016/j.disc.2012.04.022 , S2CID 16596310 .

[FOOTNOTEChartrandJohnsMcKeonZhang2008-1] Jump up to: ^а ^б ^с ^д ^и Чартран и др. (2008) .

[FOOTNOTEEksteinHolubKaiserKoch2013-2] Экстайн и др. (2013) .

[FOOTNOTEChakrabortyFischerMatsliahYuster2011-3] Чакраборти и др. (2011) .

[FOOTNOTEChartrandOkamotoZhang2010-4] Чартран, Окамото и Чжан (2010) .

[FOOTNOTEKrivelevichYuster2010-5] Кривелевич и Юстер (2010) .

[1]

[2]

[3]

[4]

[5]