Ориентированная окраска - Oriented coloring

В теория графов, раскраска ориентированного графа это особый вид раскраска графика. А именно, это присвоение цветов вершинам ориентированный граф который

• является правильный: никакие две соседние вершины не имеют одинаковый цвет, и
• является последовательно ориентированный: если вершины ${displaystyle u}$ и ${displaystyle u'}$ одного цвета, а вершины ${displaystyle v}$ и ${displaystyle v'}$ того же цвета, тогда ${displaystyle (u,v)}$ и ${displaystyle (v',u')}$ оба не могут быть ребрами в графе.

Эквивалентно ориентированная раскраска графа графа грамм ориентированный граф ЧАС (чьи вершины представляют цвета, а чьи дуги представляют допустимые ориентации между цветами) такая, что существует гомоморфизм из грамм к ЧАС.

An ориентированное хроматическое число графа грамм - наименьшее количество цветов, необходимых для ориентированной раскраски; обычно его обозначают ${displaystyle scriptstyle chi _{o}(G)}$. То же определение можно распространить и на неориентированные графы, определив ориентированное хроматическое число неориентированного графа как наибольшее ориентированное хроматическое число любого из его графов. ориентации.^[1]

Примеры

Ориентированное хроматическое число направленного 5-цикла равно пяти. Если цикл окрашен в четыре или меньше цветов, то либо две соседние вершины имеют одинаковый цвет, либо две вершины, разнесенные на два шага, имеют одинаковый цвет. В последнем случае ребра, соединяющие эти две вершины с вершиной между ними, ориентированы непоследовательно: оба имеют одну и ту же пару цветов, но с противоположной ориентацией. Таким образом, окраска в четыре или меньшее количество цветов невозможна. Однако присвоение каждой вершине собственного уникального цвета приводит к правильной ориентированной окраске.

Характеристики

Ориентированная раскраска может существовать только для ориентированного графа без петель или ориентированных 2-циклов. Ибо цикл не может иметь разные цвета на концах, а 2-цикл не может иметь оба края, последовательно ориентированные между одними и теми же двумя цветами. Если эти условия выполнены, то всегда существует ориентированная раскраска, например раскраска, которая присваивает разный цвет каждой вершине.

Если ориентированная раскраска полный в том смысле, что никакие два цвета нельзя объединить для получения окраски с меньшим количеством цветов, тогда это однозначно соответствует гомоморфизм графов в турнир. В турнире есть по одной вершине для каждого цвета раскраски. Для каждой пары цветов в цветном графе есть ребро с этими двумя цветами на концах, что придает ориентацию ребру в турнире между вершинами, соответствующими двум цветам. Неполные раскраски также могут быть представлены гомоморфизмами в турниры, но в этом случае соответствие между раскрасками и гомоморфизмами не взаимно однозначно.

Неориентированные графы ограниченного род, ограниченный степень, или ограниченный ациклическое хроматическое число также имеют ограниченное ориентированное хроматическое число.^[1]

Смотрите также

• Сопена написал обзорную статью о раскраске ориентированных графов.^[2]
• Ориентированная раскраска (поддерживается Sopena)

Рекомендации

1. Косточка, А.В .; Sopena, E .; Чжу, X. (1997), «Ациклические и ориентированные хроматические числа графов» (PDF), Журнал теории графов, 24 (4): 331–340, Дои:10.1002 / (SICI) 1097-0118 (199704) 24: 4 <331 :: AID-JGT5> 3.0.CO; 2-P, МИСТЕР  1437294.
2. Сопена, Эрик (2001), «Раскраска ориентированного графа», Дискретная математика, 229 (1–3): 359–369, Дои:10.1016 / S0012-365X (00) 00216-8, HDL:10338.dmlcz / 119751, МИСТЕР  1815613.