Lorsque l'IG polynomial implique l'IG de couleur polynomiale (bord)?

Crossposted de MO .

l'isomorphisme du graphique coloré (bord) est GI qui préserve les couleurs (des bords s'il est coloré).

Il existe plusieurs réductions utilisant des transformations / gadgets de GI (bord) coloré en GI. Pour l'IG de couleur de bord, le plus simple est de remplacer le bord de couleur par un gadget préservant l'IG codant la couleur (la subdivision du bord suffisamment de fois est le cas le plus simple). Pour les GI de couleur vertex, attachez un gadget à un sommet.

On suppose que GI est polynomiale pour une classe graphique . $C$

Q1 Pour quel IG polynomial implique un IG polynomial (bord)? $C$

En utilisant une réduction des gadgets pourrait faire les graphiques non membres de . $C$

D'un autre côté, certains gadgets / transformations pourraient faire des graphiques des membres d'une autre classe GI polynomiale.

Exemple de réduction de couleur de bord . $G \to G'$

Faites une clique de . Colorez les bords en avec et les non-bords avec . C'est la fonction colorante qui préserve et pour récupérer de suffit de prendre les bords colorés . est clique, cograph, permutation graph et presque sûr dans de nombreuses autres classes sympas. Subdiviser les bords un nombre impair de fois (distinct pour supprime les couleurs et rend graphique bipartite parfait de , préservant l'isomorphisme). $V(G)$ $E(G)$ $1$ $0$ $G$ $G$ $G'$ $1$ $G'$ $0,1$ $G'$

Une autre approche consiste peut-être à prendre le graphe linéaire de et à ajouter des sommets pendants (universels) connectés à des sommets correspondant à . $G'$ $E(G')$

Q2 Existe-t-il de bons gadgets / transformations pour des constructions similaires?

Pensé à planariser en choisissant un dessin universel de la clique et en remplaçant le croisement des bords par des gadgets plans préservant les couleurs, disons pour des couleurs égales et autre chose pour des couleurs distinctes. Je ne sais pas si cela préserve l'isomorphisme. $G'$ $C_4,C_6$

Une autre approche possible pourrait être l'automorphisme préservant la coloration ou la subdivision de chaque bord de , utiliser 3 couleurs pour les sommets et essayer de reconnaître des graphes auto-complémentaires par automorphisme échange de et . $K_n$ ${0,1,2}$ $V(G),E(G),E(\overline{G})$ $E(G)$ $E(\overline{G})$

Q3 Le groupe d'automorphisme de la subdivision de calculé? $K_n$

Les commandes après les quelques termes initiaux sont qui est A052565 $12 , 24 , 120 , 720 , 5040 , 40320 , 362880$

Dima suggère que cela pourrait être facile pour assez grand et les termes initiaux sont des exceptions. $n$

$K_n$ $n > 4$ $0$ $2$ $1$ $2$ $1$ $2$

Ajouté l'article sur la reconnaissance des graphiques de Cayley, p 86 :

Étant donné une classe C de graphes de Cayley, et étant donné un graphe de couleur d'arête G de n sommets et m arêtes, nous nous intéressons au problème de vérifier s'il existe un isomorphisme φ en préservant les couleurs telles que G est isomorphe par φ à un graphique en C coloré par les éléments de son groupe électrogène. Dans cet article, nous donnons un algorithme de temps O (m log n) pour vérifier si G est isomorphe de couleur à un graphe de Cayley.

Cela semble proche de la question, est-ce pertinent?

graph-theory graph-isomorphism automorphism joro
la source

Il y a une relation avec les hypergraphes. Le bord coloré (u, v, c) peut être traité comme un hyperedge et il y a un hypergraphe de réduction sur le graphique.

joro

Lorsque l'IG polynomial implique l'IG de couleur polynomiale (bord)?

Réponses: