Раскраска диграфов

Раскраска вершин ориентированного графа

Ориентацией простого графа Н является диграф, полученный из Н заменой каждого ребра дугой любой ориентации. Диграф G будет ориентированным графом, если он является ориентацией какого-либо графа Н.

Ориентированной k-раскраской ориентированного графа G является разбиение V(G) на k классов раскраски, таких, что:

· нет двух смежных вершин, принадлежащих к одному и тому же классу раскраски;

·

Меры

все дуги, соединяющие два класса раскраски, имеют одну и ту же направленность.

Ориентированное хромаическое число ocn(G) ориентированного графа G – наименьшее число k, при котором G имеет ориентированную k-раскраску.

Задачи k-ориентированной раскраски ориентированного графа и нахождения ocn(G) являются NP-тяжелыми.