Кросспост из МО .
Изоморфизм цветного графа (ребро) - это GI, который сохраняет цвета (ребер, если он окрашен ребром).
Есть несколько сокращений, использующих преобразования / гаджеты (краевого) GI в GI. Для GI с цветным краем самый простой способ - заменить цветной край на гаджет, сохраняющий GI, кодирующий цвет (простейший случай - подразделение края на достаточное количество раз). Для GI, окрашенного в вершину, прикрепите гаджет к вершине.
Пусть GI полиномиальное для некоторого графа класса .
Q1 Для какого полином GI подразумевает полином (ребро) окрашенного GI?
Использование сокращения с гаджетами может сделать графики не членами .
С другой стороны, некоторые гаджеты / преобразования могут сделать графы членами некоторого другого полиномиального класса GI.
Пример уменьшения цвета краев .
Сделайте клику из . Цветные ребра в с и не ребра с . Это функция раскраски, которая сохраняет и чтобы восстановить из просто возьмите края, окрашенные в . это клика, cograph, граф перестановок и почти наверняка во многих других хороших классах. Подразделение ребер нечетное число раз (отличное от удаляет цвета и делает идеальным двудольным графом, сохраняя изоморфизм).
Возможно, другой подход состоит в том, чтобы взять линейный граф и добавить подвесные (универсальные) вершины, связанные с вершинами, соответствующими . E ( G ′ )
Q2 Есть ли хорошие гаджеты / преобразования для подобных конструкций?
Мысль о планаризации , выбрав какой-то универсальный рисунок клики и заменив пересечение ребер планарными гаджетами, сохранив цвета, скажем, для одинаковых цветов и что-то еще для разных цветов. Не знаю, сохраняет ли это изоморфизм.C 4 , C 6
Другим возможным подходом может быть автоморфизм, сохраняющий раскраску, или подразделить каждое ребро , использовать 3 цвета для вершин и попытаться распознать себя дополнительные графы путем автоморфизма, обменивающие и .0 , 1 , 2 V ( G ) , Е ( G ) , Е ( ¯ С ) Е ( О ) Е ( ¯ G )
Q3 Можно ли вычислить группу автоморфизмов подразделения ?
Заказы после нескольких первоначальных сроков: есть A052565
Дима предполагает, что это может быть легко достаточно большим, и начальные условия являются исключениями.
Q4 Учитывая вершинный окрашенное подразделение для и его группы автоморфизмов , где высокой степень вершина окрашенная , в некоторой степени являются и другими являются , какова сложность найти автоморфизм обмен и ? n > 4 0 2 1 2 1 2
Добавлена статья « О распознавании графов Кейли», стр. 86 утверждений:
Для класса C графов Кэли и графа G с ребрами из n вершин и m ребер нас интересует проблема проверки того, существует ли изоморфизм φ, сохраняющий цвета так, что G изоморфен φ графу в C окрашены элементами его порождающего множества. В этой статье мы даем алгоритм времени O (m log n), чтобы проверить, является ли G изоморфным по цвету графу Кэли.
Это похоже на вопрос, это актуально?
Ответы:
Q2: хороший пример - гаджет для маркировки графиков, используемый для доказательства того, что:
Теорема : плоская 3-связная цветная GI плоская 3-связная GI≤LT
См. Томас Тирауф, Фабиан Вагнер: Проблема изоморфизма плоских 3-связных графов находится в однозначном логическом пространстве. Теория вычислений. Сист. 47 (3): 655-673 (2010)
Используемый «маркерный гаджет» сохраняет ограничения 3-связности и плоскостности.
источник
Частичный ответ, недостаточно разбираюсь в теории групп, но две статьи дают частичные результаты.
Эта статья утверждает:
Точное определение «краевого цвета» мне не ясно.
Бумага, доказывающая циркулянт Г. И., является полиномиальной в сноске по п.1 формулы изобретения:
Спросил на МО, каковы ограничения на окраски.
источник