WikiDer > Ориентированная окраска

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

• является правильный: никакие две соседние вершины не имеют одинаковый цвет, и
• является последовательно ориентированный: если вершины ${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)

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