Recoloration de homomorphisme de graphes

4 novembre 2016
Marcin Wrochna
Université de Varsovie,
Pologne

3-Recoloration

Input:  [$G$],    [$\alpha,\beta$]: 3-colorations ,   [$\mathcal{l}$]
Question:  Peut-on recolorer [$\alpha$] en [$\beta$]?
en  [$\leq\mathcal{l}$]  étapes?

3-Recoloration est dans P.
(Bonsma et al. 2007)

4-Recoloration est PSPACE-complet.
(Bonsma et Cereceda 2009)

Plus Courte 3-Recoloration est dans P. (Johnson et al. 2014)

Morphisme de graphes

[$H$]-coloration de [$G$] =
  [$\alpha : V(G)\to V(H) $]   tel que
  [$uv$]   est une arête   [$\implies$] [$\alpha(u)\alpha(v)$]   est une arête

[$k$]-coloration = morphisme dans [$K_k$]

On écrit aussi
[$\alpha : G \to H$]

[$H$]-Recoloration

Input:  [$G$],    [$\alpha,\beta$]: [$H$]-coloration de [$G$]
Question:  Peut-on recolorer [$\alpha$] en [$\beta$]?

Hom[$(G,H)$]

sommets = [$H$]-coloration de [$G$]
arêtes = entre [$\alpha$] et [$\alpha'$] qui ne diffèrent que sur un sommet de [$G$]

Question = Y a t-il une promenade entre [$\alpha$] et [$\beta$] dans Hom[$(G,H)$]?

Hom[$(G,H)$] a été utilisé pour borner [$\chi$], comme dans la preuve de la conjecture de Kneser
[$\chi(G_{n,k})=n-2k+2$]       (Lovász 1978)
[$H^G$] a été utilisé pour montrer un cas de la conjecture d'Hedetniemi
[$\chi(G\times H) = \min(\chi(G), \chi(H)) $]       (pour [$\chi(G\times H)=3$], El-Zahar, Sauer 1985)

[$H$]-Recoloration

Input:  [$G$],    [$\alpha,\beta$]: [$H$]-colorations of [$G$]
Question:  Peut-on recolorer [$\alpha$] en [$\beta$]?

[$K_3$]-Recoloration est dans P.
[$K_4$]-Recoloration est PSPACE-complet.

Mes résultats

  • Pour [$H$] sans [$C_4$] comme sous-graphe, [$H$]-Recoloration est dans P.
  • Algorithme pour trouver une solution en temps [$\mathcal{O}(|G|^2+|H|)$].
  • Pour [$H$] sans [$C_4$] comme sous-graphe, Plus Courte [$H$]-Recoloration est dans P.
  • Une caractérisation de l'ensemble des solutions…

Pourquoi sans [$C_4$]?

[$H$] ne contient aucun [$C_4$] comme sous-subgraphe si et seulement si:
Pour chaque paire de couleurs dans [$V(H)$], il y a [$\leq 1$] couleur compatible avec les deux.

ou: Quand un sommet change de couleur, son voisinage est monochromatique.

Exemple

Une [$H$]-coloration de [$G$]:

Exemple

Une [$H$]-recoloration de [$G$]:

Exemple

Supposition: Quand un sommet est recoloré, son voisinage est monochromatique.

 

Homotopie

Supposition: Quand un sommet est recoloré, son voisinage est monochromatique.

Dans ce cas, on peut voir la recoloration comme une transformation continue (une homotopie) de [$G$] dedans [$H$]:

Homotopie

Supposition: Si un sommet est recoloré, ses voisins ont tous une couleur.

Si [$\alpha$] peut être recoloré en [$\beta$],
alors les applications continues qui correspondent à [$\alpha$] et à [$\beta$] sont homotopes
(peuvent être déformées de façon continue l'une dans l'autre):

Homotopie – invariant

Supposition: Si un sommet est recoloré, ses voisins ont tous une couleur.

Si [$\alpha$] peut être recoloré en [$\beta$],
alors les applications continues qui leur correspondent sont homotopes
Par exemple, ce cycle de [$G$] tournera toujours autour du cycle gauche dans [$H$]!

Description d'une promenade à homotopie près

Description d'une promenade à homotopie près

Description d'une promenade à homotopie près

(Groupoid multiplication example)

reduire = supprimer [$(u,v) (v,u)$] gloutonnement
[$\pi(H)$] =

(groupoïde)

Promenades

[$\alpha:G\to H$],   [$W$] – une promenade dans [$G$].
Alors [$\alpha(W)$] est une promenade dans [$H$].

[$S=\alpha_1,\dots,\alpha_{\ell}$]  –  une [$H$]-recoloration de [$G$].
Pour un [$v\in V(G)$],
[$S(v) = (\alpha_1(v), \_)\ \ (\_, \alpha_2(v))\ \ (\alpha_2(v), \_)\ \ \dots\ \ (\_, \alpha_{\ell}(v))$] définit une promenade unique dans [$H$].

Question: Soit [$v \in V(G)$] et [$Q\in\pi(H)$],
y a t-il une solution de [$\alpha$] en [$\beta$]
telle que [$\overline{S(v)}=Q$]?

[$S(v)$] est de longueur paire et ceci est stable par réduction.
Donc il n'y a pas de solution où [$|Q|$] est impair.

Exemple

Une promenade [$W$] de [$u$] a [$v$] (dans [$G$]) est [$H$]-recoloré.

Un lemme important

[$S=\alpha,\dots,\beta$] – une [$H$]-recoloration de [$G$].
[$W$] – une promenade de [$u$] à [$v$] dans [$G$].     $$\overline{\alpha(W)} \cdot \overline{S(v)} \cdot \overline{\beta(W)}^{-1} \cdot \overline{S(u)}^{-1} = \varepsilon$$

Illustration of the lemma.

Un lemme important

[$S=\alpha,\dots,\beta$] – une [$H$]-recoloration de [$G$].
[$W$] – une promenade de [$u$] à [$v$] dans [$G$].     Alors $$\overline{S(u)} = \overline{\alpha(W)} \cdot \overline{S(v)} \cdot \overline{\beta(W)}^{-1}$$

Donc, si on connaît [$\alpha,\beta$] et [$S(v)$], on connaît [$S$] en entier.

Pour chaque promenade fermée [$C$] (de [$v$] à [$v$]) dans [$G$],
$$\overline{S(v)}= \overline{\alpha(C)} \cdot \overline{S(v)} \cdot \overline{\beta(C)}^{-1}$$

Condition 2/3: topologiquement viable

Soit [$Q = \overline{S(v)}$] pour une solution [$S$].
Pour chaque promenade fermée [$C$] (de [$v$] à [$v$]) dans [$G$], $$\overline{\beta(C)} = Q^{-1} \cdot \overline{\alpha(C)} \cdot Q$$

On dira que [$Q$] est topologiquement viable (pour [$v$]).
Étonnamment, si on trouve une telle promenade réduite [$Q$],
ça donne presque déjà une recoloration correspondante.

Condition 3/3: cycles tendus

(a cycle in G winding twice around a cycle in H)

Un cycle [$C = e_1 \dots e_n$] dans est [$G$]   tendu   si
  [$\alpha(C)$] est réduit et aussi [$e_n\neq e_1^{-1}$].

(Il ne revient jamais sur ses pas.)

Aucun sommet de [$C$] ne peut être recoloré!

Soit [$S$] une solution avec [$\overline{S(v)} = Q$].
Si [$v$] est sur un cycle tendu,
alors [$Q = \varepsilon$] est la seule possibilité.

Similairement, si un autre sommet [$u$] est sur un cycle tendu,
alors [$Q = \overline{\alpha(W)}\cdot\overline{\beta(W)}^{-1}$] est la seule possibilité.

Condition 3/3: cycles tendus

(a cycle in G winding twice around a cycle in H)

Caractérisation

Soit [$v\in V(G)$] et [$Q\in\pi(H)$].
Il existe une solution [$S$] de [$\alpha$] à [$\beta$] telle que [$\overline{S(v)}=Q$] si et seulement si
  • [$Q$] est de longueur paire
  • [$Q$] est topologiquement viable pour [$v$], et
  • [$Q = \overline{\alpha(W)}\cdot\overline{\beta(W)}^{-1}$] pour une promenade [$W$] vers un sommet sur un cycle tendu.
De plus, étant donné une telle promenade [$Q$], on peut trouver une recoloration [$S$]
telle que [$S(v)=Q$] et que [$S(u)$] sont tous réduit,
en temps [$\mathcal{O}(|G|^2+|G|\cdot|Q|+\|H\|)$].

Exemple

[$G = C_8$]. On peut glisser [$v$] autour du premier cycle de [$H$] autant de fois qu'on veut.
(mais le trajet est toujours impair).

Exemple

[$G = C_8$]. Les trajets qui vont autour du second cycle ne sont pas topologiquement viables.

Preuve de la caractérisation

Soit [$Q \in \pi(H)$] pair et topologiquement viable pour [$\alpha,\beta,v$].
Soit [$S_u := \overline{\alpha(W)} \cdot Q \cdot \overline{\beta(W)}^{-1} $] pour une/chaque promenade [$W$] de [$u$] à [$v$].
Nous allons construire une solution telle que [$S(u)=S_u$].

Soit [$S_u = (u^0, u^1) (u^1, u^2) \dots $]
Le sommet [$u$] doit être recolorer de [$\alpha(u)=u^0$] à [$u^2$], de [$u^2$] à [$u^4, \dots$]

Soit [$xy\in E(G)$]
Alors [$ S_x = \alpha((x,y)) \cdot S_y \cdot \beta((y,x)) $].

Preuve de la caractérisation

Soit [$xy\in E(G)$]. Alors [$ S_x = \alpha((x,y)) \cdot S_y \cdot \beta((y,x)) $].

[$\alpha((x,y))=(x^0,y^0)$] va reduire [$S_y$] ou non.

C'est-à-dire, soit   [$S_y = (y^0,x^0) S_x \dots$],   soit   [$S_x = (x^0,y^0) S_y \dots$]
Conformément, [$x$] doit être recoloré après ou avant [$y$].
Ceci donne une orientation à chaque arête [$E(G)$].
Si il n'y a pas de cycle, l'ordre donne une solution correcte sur chaque arête!

Par exemple:
[$S_x = \hspace{3em} (x^0,y^2) (y^2,x^2) (x^2,y^4) \dots $]  et
[$S_y = (y^0,x^0) (x^0,y^2) (y^2,x^2) (x^2, y^4) \dots $]

Preuve de la caractérisation

Supposons qu'il y a un cycle [$x_1,x_2,\dots$]
tel que [$S_{x_{i+1}} = (x_{i+1},x_i) S_{x_i} \dots $].

Alors [$S_{x_{i+1}} = (x_{i+1},x_i)(x_{i},x_{i-1}) S_{x_{i-1}} \dots $]  (et c'est réduit),
Donc le cycle est tendu et tous les [$S_{x_{i}}$] devraient être vides!

Ceci conclut la preuve
et donne un algorithme qui construit une solution [$S$], si possible,
étant donné la promenade [$Q=\overline{S(v)}$].

Toutes les solutions

Soit [$\alpha,\beta: G\to H$], [$v\in V(G)$].
L'ensemble des trajets dans [$\pi(H)$] qui sont topologiquement viable est égal à:
  • [$\emptyset$]
  • [$\{P\}$]                         où [$P\in\pi(H)$],
  • [$\{P\cdot R^n \mid n\in\mathbb{Z}\}$]   où [$P,R\in\pi(H)$],
  • l'ensemble de toutes les promenades [$\alpha(v)\to\beta(v)$] dans [$\pi(H)$].

De plus, on peut dire dans quel cas on est et renvoyer [$P,R$]
en temps [$\mathcal{O}(\|G\|\cdot|G|+\|H\|)$].

Toutes les solutions

Soit [$\alpha,\beta: G\to H$],   [$v\in V(G)$].
L'ensemble des trajets [$Q\in \pi(H)$] tels que [$Q=\overline{S(v)}$] pour certaine solution [$S$] est égal à:
  • [$\emptyset$]
  • [$\{P\}$]                         où [$P\in\pi(H)$],
  • [$\{P\cdot R^n \mid n\in\mathbb{Z}\}$]   où [$P,R\in\pi(H)$],
  • l'ensemble de toutes les promenades paires [$\alpha(v)\to\beta(v)$] dans [$\pi(H)$].

De plus, on peut dire dans quel cas on est et renvoyer [$P,R$]
en temps [$\mathcal{O}(\|G\|^2+\|H\|)$].

Questions ouvertes

Meilleures questions?

Soit [$\alpha, \beta: G \to H$].
Ils correspondent à des points (sommets) dans Hom[$(G,H)$].
Une recoloration est une courbe (promenade) dans Hom[$(G,H)$].

À un graphe [$G$] on associe un espace topologique Hom[$(K_2,G)$].
À un morphisme [$G \to H$] on associe une fonction continue de Hom[$(K_2,G)$] à Hom[$(K_2,H)$].
(Lovász 1978) a utilisé ces objets pour prouver la conjecture de Kneser (borner [$\chi$]).

Soit [$\alpha, \beta: G \to H$] pour un graphe [$H$] sans carré.
Il existe une recoloration entre [$\alpha,\beta$]   si et seulement si:
  • Les fonctions associées de Hom[$(K_2,G)$] à Hom[$(K_2,H)$] sont homotopes et
  • Les fonctions associées de Hom[$(C_\ell,G)$] à Hom[$(C_\ell,H)$] sont homotopes, pour chaque [$\ell\in\mathbb{N}$].

/