Характерная раскраска

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

Характерная раскраска графа 4-мерного гиперкуба

Характерные раскраски и характерные числа ввели Альбертсон и Коллинз, которые дали следующий пример для объяснения введения такой раскраски, основанный на головоломке, которую до этого сформулировал Франк Рубин: «Пусть у вас имеется связка ключей (на кольце) от различных дверей. Каждый ключ открывает только одну дверь, но все ключи выглядят одинаково (вы не можете их различить по внешнему виду). Сколько цветов вам нужно, чтобы раскрасить ключи и вы после этого могли полностью идентифицировать каждый ключ?» Этот пример решается с помощью характерной раскраски для графа-цикла. С помощью такой раскраски каждый ключ может быть однозначно идентифицирован по его цвету и цвету окружающих его ключей.

Примеры

Восемь асимметричных графов, для каждого дана характерная раскраска всего с одним цветом (красным)

Граф имеет число характерной раскраски равное единице тогда и только тогда, когда он асимметричен. Например, граф Фрухта имеет характерную раскраску всего в один цвет.

В полном графе единственная возможная характерная раскраска назначает различные цвета всем вершинам. Если двум вершинам был бы назначен один и тот же цвет, существовала бы симметрия, которая переставляет эти две вершины, оставляя остальные на месте. По этой причине число характерной раскраски полного графа K_n равно n. Однако граф, полученный из K_n путём присоединения вершины со степенью единица к каждой вершине графа K_n, имеет существенно меньшее число характерной раскраски, хотя имеет ту же самую группу симметрии — он имеет характерную раскраску с $\lceil {\sqrt {n}}\rceil$ цветами, полученную путём использования различных упорядоченных пар цветов для каждой пары — вершины K_n и присоединённой к ней вершины.

Характерная раскраска связки из шести ключей с помощью двух цветов (красный цвет и отсутствие окраски)

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

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

Число характерной раскраски графа Петерсена равно 3. Однако все другие кнезеровские графы, отличные от этого графа и полного графа, имеют число характерной раскраски 2. Аналогично, среди обобщённых графов Петерсена, только сам граф Петерсена и граф куба имеют число характерной раскраски 3. Остальные имеют число характерной раскраски 2.

Вычислительная сложность

Числа характерной раскраски деревьев, планарных графов и интервальных графов могут быть вычислены за полиномиальное время.

Точная вычислительная сложность нахождения числа характерной раскраски неясна, поскольку она тесно связана с остающейся неизвестной сложностью установления изоморфизма графов. Однако было показано, что она принадлежит классу сложности AM. Кроме того, проверка, что число характерной раскраски не превосходит трёх, является NP-трудной, а проверка того, что оно не превосходит двух, по меньшей мере так же трудна, как проверка автоморфизма графов, но не сложнее, чем проверка изоморфизма графов.

Дополнительные свойства

Раскраска заданного графа является характерной для этого графа тогда и только тогда, когда она является характерной для дополнения графа. Поэтому любой граф имеет то же самое число характерной раскраски, что и его дополнение.

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

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

Вариации

Правильная характерная раскраска — это характерная раскраска, которая является также правильной раскраской — любые две смежные вершины имеют различные цвета. Минимальное число цветов в правильной характерной раскраске графа называется хроматическим числом характерной раскраски графа.

Литература

• Frank Rubin. Problem 729: the blind man's keys // Journal of Recreational Mathematics. — 1979. — Т. 11.
• Michael O. Albertson, Karen L. Collins. Symmetry breaking in graphs // Electronic Journal of Combinatorics. — 1996. — Т. 3, вып. 1.
• Wilfried Imrich, Sandi Klavžar. Distinguishing Cartesian powers of graphs // Journal of Graph Theory. — 2006. — Т. 53, вып. 3. — doi:10.1002/jgt.20190. If a graph has no nontrivial automorphisms its distinguishing number is 1. In other words, D(G)=1 for asymmetric graphs.
• Bill Bogstad, Lenore J. Cowen. The distinguishing number of the hypercube // Discrete Mathematics. — 2004. — Т. 283, вып. 1—3. — С. 29—35. — doi:10.1016/j.disc.2003.11.018.
• Michael O. Albertson, Debra L. Boutin. Using determining sets to distinguish Kneser graphs // Electronic Journal of Combinatorics. — 2007. — Т. 14, вып. 1. — С. R20.
• Lal A. K., Bhattacharjya B. Breaking the symmetries of the book graph and the generalized Petersen graph // SIAM Journal on Discrete Mathematics. — 2009. — Т. 23, вып. 3. — С. 1200—1216. — doi:10.1137/080728640. Лал и Бхаттачарджия (Теоремы 4.3) приписывают этот результат К. С. Потанке (его неопубликованных тезисах к диссертации в Политехническом университете Виргинии, 1998).
• Christine T. Cheng. On computing the distinguishing numbers of trees and forests // Electronic Journal of Combinatorics. — 2006. — Т. 13, вып. 1. — С. R11.
• Arvind V., Christine T. Cheng, Nikhil R. Devanur. On computing the distinguishing numbers of planar graphs and beyond: a counting approach // SIAM Journal on Discrete Mathematics. — 2008. — Т. 22, вып. 4. — С. 1297—1324. — doi:10.1137/07068686X. — arXiv:math/0703927.
• Christine T. Cheng. On computing the distinguishing and distinguishing chromatic numbers of interval graphs and other results // Discrete Mathematics. — 2009. — Т. 309, вып. 16. — С. 5169—5182. — doi:10.1016/j.disc.2009.04.004.
• Alexander Russell, Ravi Sundaram. A note on the asymptotics and computational complexity of graph distinguishability // Electronic Journal of Combinatorics. — 1998. — Т. 5. — С. R23.
• Elaine M. Eschen, Chính T. Hoàng, Sritharan R., Lorna Stewart. On the complexity of deciding whether the distinguishing chromatic number of a graph is at most two // Discrete Mathematics. — 2011. — Т. 311, вып. 6. — С. 431—434. — doi:10.1016/j.disc.2010.12.013.
• Karen L. Collins, Ann N. Trenk. The distinguishing chromatic number // Electronic Journal of Combinatorics. — 2006. — Т. 13, вып. 1. — С. R16.