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

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

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

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

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

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

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

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

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

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