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

В теории графов ориентированная раскраска графов представляет собой особый тип раскраски графов . А именно, этоприсвоение цветов вершинам ориентированного графа , которое

правильно и : никакие две соседние вершины не имеют одинакового цвета,
: последовательно ориентирован если вершины $u$ и $u'$ имеют одинаковый цвет, а вершины $v$ и $v'$ иметь одинаковый цвет, то $(u,v)$ и $(v',u')$ не могут оба быть ребрами графа.

Эквивалентно, раскраска ориентированного графа графа G — это ориентированный граф H (вершины которого представляют цвета, а дуги представляют действительные ориентации между цветами) такой, что существует гомоморфизм из G в H .

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

Примеры

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

Характеристики

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

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

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

См. также

Сопена написал обзорную статью об ориентированной раскраске графов. ^[2]
Страница «Ориентированная раскраска» (поддерживается Sopena)

Ссылки

^ Jump up to: ^а ^б Косточка, А.В.; Сопена, Э.; Чжу, X. (1997), «Ациклические и ориентированные хроматические числа графов» (PDF) , Journal of Graph Theory , 24 (4): 331–340, doi : 10.1002/(SICI)1097-0118(199704)24: 4<331::AID-JGT5>3,0.CO;2-P , MR 1437294 .
^ Сопена, Эрик (2001), «Ориентированная раскраска графов», Дискретная математика , 229 (1–3): 359–369, doi : 10.1016/S0012-365X(00)00216-8 , hdl : 10338.dmlcz/119751 , MR 1815613 .

[ksz97-1] Jump up to: ^а ^б Косточка, А.В.; Сопена, Э.; Чжу, X. (1997), «Ациклические и ориентированные хроматические числа графов» (PDF) , Journal of Graph Theory , 24 (4): 331–340, doi : 10.1002/(SICI)1097-0118(199704)24: 4<331::AID-JGT5>3,0.CO;2-P , MR 1437294 .

[sop01-2] Сопена, Эрик (2001), «Ориентированная раскраска графов», Дискретная математика , 229 (1–3): 359–369, doi : 10.1016/S0012-365X(00)00216-8 , hdl : 10338.dmlcz/119751 , MR 1815613 .

[1]

[2]