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

Перейти к навигацииПерейти к поиску

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

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

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

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

Ориентированное хроматическое число орграфа G — минимальное число цветов, необходимое в ориентированной раскраске. Это число обычно обозначается как . То же самое определение может быть распространено на неориентированные графы путём определения ориентированного хроматического числа неориентированного графа как максимального хроматического числа из всех его ориентаций[3][2].

Примеры

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

Свойства

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

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

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

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

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

Курсель[5] доказал, что для любого плоского графа, а Распуд и Соупина[6] улучшили результат до 80. Бородин с соавторами опубликовали следующую теорему[7]:

 Теорема: Пусть G — плоский граф обхвата g, тогда 
(1)
(2)
(3)
(4)

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

Примечания

  1. В статье под ориентированным графом понимается направленный граф. В английском варианте книги Дистеля "Теория графов" oriented graphs are directed graphs without loops or multiple edges, то есть ориентированные графы — это направленные графы без петель и кратных рёбер, в русском же переводе книги направленные графы суть ориентированные графы без петель и кратных рёбер. Это приводит к частой путанице понятий
  2. 1 2 БОРОДИН, ИВАНОВА, 2005, с. 239.
  3. 1 2 Kostochka, Sopena, Zhu, 1997, с. 331–340.
  4. БОРОДИН, ИВАНОВА, 2005, с. 240.
  5. Courselle, 1994.
  6. Raspaud, Sopena, 1994, pp. 171—174.
  7. Borodin, Kostochka, Nešetřil, Raspaud, Sopena, 1999, pp. 77—90.
  8. Borodin, Kim, Kostochka, West, 2004, pp. 147—159.

Литература

  • Kostochka A. V., Sopena E., Zhu X. Acyclic and oriented chromatic numbers of graphs // Journal of Graph Theory. — 1997. — Т. 24, вып. 4. — С. 331–340. — doi:10.1002/(SICI)1097-0118(199704)24:4<331::AID-JGT5>3.0.CO;2-P.
  • БОРОДИН О.В., ИВАНОВА А.О. ОРИЕНТИРОВАННАЯ РАСКРАСКА ПЛОСКИХ ГРАФОВ С ОБХВАТОМ НЕ МЕНЕЕ 4 // СИБИРСКИЕ ЭЛЕКТРОННЫЕ МАТЕМАТИЧЕСКИЕ ИЗВЕСТИЯ. — 2005. — С. 239–249. — ISSN 1813-3304.
  • Courselle B. The monadic second order logic of graphs VI: On several representations of graphs by relational structures // Discrete Appl. Math.. — 1994. — Вып. 54. — С. 117–149.
  • Raspaud A., Sopena E. Good and semi-strong colorings of oriented planar graphs // Inf. Processing Letters. — 1994. — Вып. 51.
  • Borodin O.V., Kostochka A.V., Nešetřil J., Raspaud A., Sopena E. On the maximum average degree and the oriented chromatic number of a graph // Discrete Mathematics. — 1999. — Вып. 206.
  • Borodin O.V., Kim S.-J., Kostochka A. V., West D.B. Homomorphisms from sparse graphs with large girth // Journal of Combinatorial Theory, Series B,. — 2004. — Вып. 90.