Когда под полиномом GI подразумевается полиномиальный (ребро) цветной GI?

10

Кросспост из МО .

Изоморфизм цветного графа (ребро) - это GI, который сохраняет цвета (ребер, если он окрашен ребром).

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

Пусть GI полиномиальное для некоторого графа класса .C

Q1 Для какого полином GI подразумевает полином (ребро) окрашенного GI?C

Использование сокращения с гаджетами может сделать графики не членами .C

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

Пример уменьшения цвета краев .GG

Сделайте клику из V(G) . Цветные ребра в E(G) с 1 и не ребра с 0 . Это функция раскраски, которая сохраняет G и чтобы восстановить G из G просто возьмите края, окрашенные в 1 . G это клика, cograph, граф перестановок и почти наверняка во многих других хороших классах. Подразделение ребер нечетное число раз (отличное от 0,1 удаляет цвета и делает G идеальным двудольным графом, сохраняя изоморфизм).

Возможно, другой подход состоит в том, чтобы взять линейный граф и добавить подвесные (универсальные) вершины, связанные с вершинами, соответствующими . E ( G )GE(G)

Q2 Есть ли хорошие гаджеты / преобразования для подобных конструкций?

Мысль о планаризации , выбрав какой-то универсальный рисунок клики и заменив пересечение ребер планарными гаджетами, сохранив цвета, скажем, для одинаковых цветов и что-то еще для разных цветов. Не знаю, сохраняет ли это изоморфизм.C 4 , C 6GC4,C6

Другим возможным подходом может быть автоморфизм, сохраняющий раскраску, или подразделить каждое ребро , использовать 3 цвета для вершин и попытаться распознать себя дополнительные графы путем автоморфизма, обменивающие и .0 , 1 , 2 V ( G ) , Е ( G ) , Е ( ¯ С ) Е ( О ) Е ( ¯ G )Kn0,1,2V(G),E(G),E(G¯)E(G)E(G¯)

Q3 Можно ли вычислить группу автоморфизмов подразделения ?Kn

Заказы после нескольких первоначальных сроков: есть A05256512,24,120,720,5040,40320,362880

Дима предполагает, что это может быть легко достаточно большим, и начальные условия являются исключениями.n

Q4 Учитывая вершинный окрашенное подразделение для и его группы автоморфизмов , где высокой степень вершина окрашенная , в некоторой степени являются и другими являются , какова сложность найти автоморфизм обмен и ? n > 4 0 2 1 2 1 2Knn>4021212

Добавлена статья « О распознавании графов Кейли», стр. 86 утверждений:

Для класса C графов Кэли и графа G с ребрами из n вершин и m ребер нас интересует проблема проверки того, существует ли изоморфизм φ, сохраняющий цвета так, что G изоморфен φ графу в C окрашены элементами его порождающего множества. В этой статье мы даем алгоритм времени O (m log n), чтобы проверить, является ли G изоморфным по цвету графу Кэли.

Это похоже на вопрос, это актуально?

Joro
источник
Есть связь с гиперграфами. Цветное ребро (u, v, c) можно рассматривать как гиперчувствительность, а гиперграф приведен к графу.
Joro

Ответы:

4

Q2: хороший пример - гаджет для маркировки графиков, используемый для доказательства того, что:

Теорема : плоская 3-связная цветная GI плоская 3-связная GITL

См. Томас Тирауф, Фабиан Вагнер: Проблема изоморфизма плоских 3-связных графов находится в однозначном логическом пространстве. Теория вычислений. Сист. 47 (3): 655-673 (2010)

Используемый «маркерный гаджет» сохраняет ограничения 3-связности и плоскостности.

Марцио де Биаси
источник
Спасибо. А как насчет других вопросов?
Joro
@joro: я подумаю о Q3, Q4; для Q1 я думаю, что - возможно - более интересно спросить "Для какого C полиномиальный GI не подразумевает (или неизвестно, подразумевает ли он ...) GI полиномиального (ребристого) цвета?" (потому что для многих классов графов, для которых GI разрешается за полиномиальное время, простые маркировки вершин / ребер не выводят графы из )C
Марцио Де Биаси,
По вопросу 1: если вы найдете интересный вопрос, задайте его. Или, возможно, отредактируйте этот вопрос с помощью Q1.1 . Некоторые мысли, когда есть пиво :). (край) цветной граф тривиально представляется мне гиперграфом. HGI так же легко, как GI через сокращение IIRC. Некоторые случаи ограниченных автоморфизмов являются NP-полными, а некоторые - полиномиальными IIRC.
Жоро
В вопрос добавлена ​​статья, которая может быть актуальной.
Joro
1

Частичный ответ, недостаточно разбираюсь в теории групп, но две статьи дают частичные результаты.

гг'

В(г)еЕ(г')1еЕ(г)0гг'1

гЧАСг'ЧАС'

г'

Эта статья утверждает:

О(N2(журналN)6)N

Точное определение «краевого цвета» мне не ясно.

Бумага, доказывающая циркулянт Г. И., является полиномиальной в сноске по п.1 формулы изобретения:

Под графом мы понимаем обычный граф, орграф или даже графа с краями.

Спросил на МО, каковы ограничения на окраски.

Joro
источник