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

Ориентированная раскраска графа — это специальный вид раскраски графов. А именно, это назначение цветов вершинам ориентированного графа, которое

• правильное — никакие две смежные вершины не получают один и тот же цвет,
• сохраняется ориентация — если (x, y) и (u, v) являются дугами в графе, то недопустимо, чтобы цвета вершин x и v, а также цвета вершин y и u совпадали.

Другое определение: Ориентированная k-раскраска орграфа H есть ориентированный гомоморфизм в k-вершинный орграф H*.

Ориентированное хроматическое число

Ориентированное хроматическое число орграфа G — минимальное число цветов, необходимое в ориентированной раскраске. Это число обычно обозначается как $\scriptstyle \chi _{o}(G)$. То же самое определение может быть распространено на неориентированные графы путём определения ориентированного хроматического числа неориентированного графа как максимального хроматического числа из всех его ориентаций.

Примеры

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

Свойства

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

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

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

Оценки ориентированного хроматического числа

Ориентированное хроматическое число графа может существенно отличаться от его (обычного) хроматического числа. Например, существуют двудольные графы с произвольно большим ориентированным хроматическим числом, достаточно заменить каждое ребро графа $K_{n}$ на путь длиной 2, и тогда концы каждого такого пути в полученном графе $K_{n}^{*}$ обязаны краситься в разные цвета.

Курсель доказал, что $o(G)\leqslant 3^{63}$ для любого плоского графа, а Распуд и Соупина улучшили результат до 80. Бородин с соавторами опубликовали следующую теорему:

 Теорема: Пусть G — плоский граф обхвата g, тогда 
 (1) $g(G)\geqslant 14\Rightarrow o(G)\leqslant 5$ 
 (2) $g(G)\geqslant 8\Rightarrow o(G)\leqslant 7$ 
 (3) $g(G)\geqslant 6\Rightarrow o(G)\leqslant 11$ 
 (4) $g(G)\geqslant 5\Rightarrow o(G)\leqslant 19$ 

В другой статье Бородина ограничение в (1) теоремы было ослаблено до 13.