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

Ориентированная раскраска графа — это специальный вид раскраски графов. А именно, это назначение цветов вершинам ориентированного графа^[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.

У этой статьи есть несколько проблем, помогите их исправить: Необходимо проверить качество перевода c неуказанного языка, исправить содержательные и стилистические ошибки. Вы можете помочь улучшить эту статью (см. также рекомендации по переводу). Оригинал не указан. Пожалуйста, укажите его. (2 февраля 2019) Стиль этой статьи неэнциклопедичен или нарушает нормы литературного русского языка. Статью следует исправить согласно стилистическим правилам Википедии. (2 февраля 2019) Пожалуйста, после исправления проблемы исключите её из списка параметров. После устранения всех недостатков этот шаблон может быть удалён любым участником.