Ориентированная окраска - 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)

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