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

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

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

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

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

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

Примеры

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

Свойства

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

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

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

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

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

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

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

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

Литература

• Шаблон:Статья
• Шаблон:Статья
• Шаблон:Статья
• Шаблон:Статья
• Шаблон:Статья
• Шаблон:Статья