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

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

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

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

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

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

Примеры

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

Свойства

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

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

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

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

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

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

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

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