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

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

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

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

Примеры

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Вариации

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

Литература

• Шаблон:Статья
• Шаблон:Статья
• Шаблон:Статья If a graph has no nontrivial automorphisms its distinguishing number is 1. In other words, Шаблон:Math for asymmetric graphs.
• Шаблон:Статья
• Шаблон:Статья
• Шаблон:Статья Лал и Бхаттачарджия (Теоремы 4.3) приписывают этот результат К. С. Потанке (его неопубликованных тезисах к диссертации в Политехническом университете Виргинии, 1998).
• Шаблон:Статья
• Шаблон:Статья
• Шаблон:Статья
• Шаблон:Статья
• Шаблон:Статья
• Шаблон:Статья