Отличительная окраска - Distinguishing coloring

Отличительная окраска 4-граф гиперкуба

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

Отличительные окраски и отличительные числа были введены Альбертсон и Коллинз (1996), который привел следующий мотивирующий пример, основанный на головоломке, ранее сформулированной Фрэнком Рубиным: «Предположим, у вас есть связка ключей от разных дверей; каждый ключ открывает только одну дверь, но все они кажутся вам неотличимыми. Как мало цветов вы нужно, чтобы раскрасить ручки ключей таким образом, чтобы можно было однозначно идентифицировать каждый ключ? "^[1] Этот пример решается с помощью отличительной раскраски для график цикла. При такой раскраске каждая клавиша будет однозначно идентифицироваться по цвету и последовательности цветов вокруг нее.^[2]

Примеры

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

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

В полный график, единственные отличительные цвета присваивают каждой вершине свой цвет. Ведь если бы двум вершинам был назначен один и тот же цвет, существовала бы симметрия, которая поменяла местами эти две вершины, оставив остальные на месте. Следовательно, отличительный номер полного графа K_п является п. Однако график, полученный из K_п присоединяя вершину степени один к каждой вершине K_п имеет значительно меньший отличительный номер, несмотря на ту же группу симметрии: он имеет отличительную окраску с ${\displaystyle \lceil {\sqrt {n}}\rceil }$ цвета, полученные с помощью другой упорядоченной пары цветов для каждой пары вершин K_п и его прикрепленный сосед.^[2]

Отличительная окраска кольца из шести клавиш в два цвета (красный и неокрашенный)

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

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

В Граф Петерсена имеет отличительный номер 3. Однако, кроме этого графа и полных графов, все Графы Кнезера имеют отличительный номер 2.^[5] Точно так же среди обобщенные графы Петерсена, только сам граф Петерсена и граф куба имеют отличительный номер 3; остальные имеют отличительный номер 2.^[6]

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

Отличительные числа деревья, планарные графы, и интервальные графики можно вычислить в полиномиальное время.^[7][8][9]

Точная сложность вычисления отличительных чисел неясна, потому что она тесно связана с до сих пор неизвестной сложностью изоморфизм графов. Однако было показано, что он принадлежит к классу сложности AM.^[10] Кроме того, проверка того, не превышает ли отличительное число трех, является NP-жесткий,^[9] и проверка того, не превышает ли оно двух, «по крайней мере так же сложно, как автоморфизм графа, но не сложнее, чем изоморфизм графа».^[11]

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

Раскраска данного графа является отличительной для этого графа тогда и только тогда, когда она различна для дополнительный граф. Следовательно, каждый граф имеет то же отличительное число, что и его дополнение.^[2]

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

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

Вариации

А правильная отличительная окраска это отличительная раскраска, которая также является правильной раскраской: каждые две соседние вершины имеют разные цвета. Минимальное количество цветов в правильной различающейся раскраске графа называется отличительное хроматическое число графа.^[12]

использованная литература

1. Рубин, Франк (1979), «Проблема 729: ключи слепого», Журнал развлекательной математики, 11: 128. Решение в т. 12, 1980. Цит. Альбертсон и Коллинз (1996). Вместо того чтобы использовать цвета, Рубин сформулировал проблему в терминах ручек клавиш, которые можно отличить друг от друга наощупь. Точнее, эта проблема предполагает, что каждый ключ является симметричным, так что ключи нельзя отличить друг от друга по их ориентации на связке ключей.
2. Альбертсон, Майкл О .; Коллинз, Карен Л. (1996), «Нарушение симметрии в графах», Электронный журнал комбинаторики, 3 (1): R18, Г-Н  1394549.
3. См., Например, Имрих, Вильфрид; Клавжар, Санди (2006), «Выявление декартовых степеней графов», Журнал теории графов, 53 (3): 250–260, CiteSeerX  10.1.1.59.9242, Дои:10.1002 / jgt.20190, Г-Н  2262268, Если граф не имеет нетривиальных автоморфизмов, его отличительное число равно 1. Другими словами, D(г) = 1 для асимметричных графов.
4. Богстад, Билл; Коуэн, Ленор Дж. (2004), «Отличительное число гиперкуба», Дискретная математика, 283 (1–3): 29–35, Дои:10.1016 / j.disc.2003.11.018, Г-Н  2061481.
5. Альбертсон, Майкл О .; Бутин, Дебра Л. (2007), «Использование определяющих множеств для различения графиков Кнезера», Электронный журнал комбинаторики, 14 (1): R20, Г-Н  2285824.
6. Lal, A. K .; Bhattacharjya, B. (2009), "Нарушение симметрии книжного графа и обобщенного графа Петерсена", Журнал SIAM по дискретной математике, 23 (3): 1200–1216, Дои:10.1137/080728640, Г-Н  2538646. Лал и Бхаттачарджа (теорема 4.3) приписывают этот результат неопубликованной магистерской диссертации К. С. Потанка (Политехнический университет Вирджинии, 1998 г.).
7. Ченг, Кристин Т. (2006), «О вычислении отличительного числа деревьев и лесов», Электронный журнал комбинаторики, 13 (1): R11, Г-Н  2200539.
8. Арвинд, В .; Cheng, Christine T .; Деванур, Нихил Р. (2008), "О вычислении различающих чисел плоских графов и за их пределами: метод подсчета", Журнал SIAM по дискретной математике, 22 (4): 1297–1324, arXiv:математика / 0703927, Дои:10.1137 / 07068686X, Г-Н  2443115.
9. Ченг, Кристин Т. (2009), «О вычислении различения и различения хроматических чисел интервальных графов и других результатов», Дискретная математика, 309 (16): 5169–5182, Дои:10.1016 / j.disc.2009.04.004, Г-Н  2548918.
10. Рассел, Александр; Сундарам, Рави (1998), «Заметка об асимптотике и вычислительной сложности различимости графов», Электронный журнал комбинаторики, 5: R23, Г-Н  1617449.
11. Эшен, Элейн М .; Hoàng, Chính T .; Sritharan, R .; Стюарт, Лорна (2011), «О сложности решения, является ли различающее хроматическое число графа не более чем двумя», Дискретная математика, 311 (6): 431–434, arXiv:0907.0691, Дои:10.1016 / j.disc.2010.12.013, Г-Н  2799894.
12. Коллинз, Карен Л.; Тренк, Энн Н. (2006), «Отличительное хроматическое число», Электронный журнал комбинаторики, 13 (1): R16, Г-Н  2200544.