Problems1

Ainsi l'algorithme fonctionne en O*(n^{2^k}).

L'index chromatique d'un graphe G, noté X'(G), est le plus petit nombre de couleurs nécessaire à une coloration propre des arêtes de G, deux arêtes devant recevoir une couleur différente lorsqu'ellesd sont adjacentes.

Calculer cet index pour les graphes complets est un problème résolu de longue date :

• Les graphes K_2n sont de nombre chromatique Delta(G)
• Les graphes K_{2n+1} sont de nombre chromatique Delta(G)+1

Beaucoup de conjectures tournent autour de colorations des arêtes des graphes complets ayant certaines proprietes (par exemple, celle l'union de toute paire de classes de couleur définit un cycle hamiltonien : perfect 1-factorization conjecture)... En général, elles semblent indiquer que quantité de colorations (en oubliant les colorations isomorphes) existent, mais jusqu'a présent il n'est possible d'en trouver qu'une seule dans la littérature : celle des tournois de round-Robin ( http://en.wikipedia.org/wiki/Round-robin_tournament ).

En résumé :

• Les graphes complets sont des graphes --tres-- simples.
• Les conjectures autour de ses colorations d'arête ne manquent pas.
• Il serait tres agréable de pouvoir exhiber la structure de plus d'une seule coloration

Le problème consiste à trouverle meilleur algorithme qui étant donnés un graphe d'intervalles G et une assignation de listes L répond s'il existe une L-coloration de G ou pas. Le meilleur algorithme actuel fonctionne en O*(2ⁿ). Existe-t-il un algorithme en O*(cⁿ) pour un c<1 ?

Par l'algorithme général de coloration de Bjorklund-Husfeld et Koivisto appliqué au line-graphe de G, cela peut se décider en temps O*(2^|E(G)|). Peut-on cependant faire mieux? Dans le cas ou G est cubique, il existe un algorithme en ???. Quid dans le cas des graphes 4-réguliers?

Ainsi l'algorithme fonctionne en O*(n^2k).

Peut-on trouver un algorithme exact meilleur que celui donné ci-dessus en O*(n^{2^k})?

L' indice chromatique d'un graphe est le plus petit nombre de couleurs d'une coloration des arêtes. D'après le théorème de Vizing, l'indice chromatique est égal au degré maximum ou au degré maximum plus un. Il est cependant NP-complet [Hol81] de décider à laquelle de ces deux valeurs il est égal.

[Hol81] I. Holyer. The NP-completeness of edge-coloring. SIAM J. Computing 2:225–231, 1981.

Le meilleur algorithme actuel fonctionne en O*(2ⁿ). Existe-t-il un algorithme en O^*(cⁿ) pour un c<1 ?

Il suffit pour cela de tester si G contient un des graphes appelés k-atomes comme sous-graphe induit. Voir [Zak06].

Il suffit pour cela de tester si G contient un des graphes appelés k-atomes comme sous-graphe induit. Voir [Zak06]

Il suffit pour cela de tester si G contient un des graphes appelés k-atomes comme sous-graphe induit. Voir

[Zak06] M. Zaker. Results on the Grundy chromatic number of graphs. Discrete Math. 306(23):3166–3173, 2006.

Peut-on trouver un algorithme exact meilleur que celui donné ci-dessus en O^*(n^{2^k})?

Le cop-number d'un graphe G, noté cn(G), est

Le meilleur algorithme actuel fonctionne en O^*(2ⁿ). Existe-t-il un algorithme en O^*(cⁿ) pour un c<1 ?

De plus, on sait que trouver le cop-number d'un graphe est un problème NP-hard. Mais appartient-il à NP ?

Enfin, il existe des versions où les gendarmes et le voleur peuvent se déplacer à des vitesses différentes. Par exemple, si le voleur a vitesse 2 (il se déplace à chaque tour vers des sommets à distance au plus 2) et les gendarmes ont vitesse 1 que peu-on dire sur le nombre minimum de gendarmes nécessaires? Dans le cas où G est une grille par exemple?

On sait que cn(G)≤1,5g+3.

Si G est planaire on sait que cn(G) ≤ 3. Cela peut-il se généraliser à cn(G) ≤ g+3 pour les graphes de genre g ? On sait que cn(G)≤1,5g+3

Le cop-number d'un graphe G, noté cn(G) est

Est-ce que cn(G)=O(n^1/2) pour tout graphe G? La meilleure borne supérieure connue est cn(G)=O(n/log(n)).

Si G est planaire on sait que cn(G) ≤ 3 pour les planaires.

Ainsi l'algorithme fonctionne en O^*(n^2k).

Peut-on trouver un algorithme exact meilleur que celui donn'e ci-dessus en O^*(n^{2^k})?

Ainsi l'algorithme fonctionne en O^*(n^{2'^k}^').

Ainsi l'algorithme fonctionne en O^*(n^{2^k}).

En considérant un graphe ayant deux sommets u et v reliés par n/3 chemins indépendants de longueur (nombre d'arêtes) 4, on obtient une borne inférieure de 3^n/3. Si S est un séparateur minimal alors l'un des enembles S, C et D est de taille au plus n/3. On a donc une borne supérieure simple en \Sum_{i=1}^{n/3} C(i,n). La meilleure borne supérieure actuelle due à Fomin et Villanger est de 1.6181ⁿ

Le joueur 1 place ses k gendarmes, le joueur 2 place le voleur. Chacun à son tour, le joueur 1 bouge chaque gendarme (il reste sur place ou va sur un sommet voisin) puis le joueur 2 bouge le voleur. Le but pour le joueur 1 est de capturer le voleur (i.e. mettre un gendarme sur la même case que le voleur) et le but du voleur est d'échapper indéfiniment aux gendarmes.

Etant donné un graphe G, le problème consiste à trouver le cop-number cn(G) qui est le nombre minimum de gendarmes nécessaires pour capturer le voleur.

Problème 4 : Algorithme exact de coloration des arêtes.

Une coloration gloutonne est une coloration obtenue à partir d'un ordre (v₁, v₂, ... , v_n) en appliquant l'algorithme glouton.

Le problème du nombre Grundy est donc dans XP (avec la paramétrisation canonique). Mais est-il FPT? Est-il W[i]-hard?

Peut-on trouver un algorithme exact meilleur que celui donn'e ci-dessus en O^*(n'^2^k'^)?

Ainsi l'algorithme fonctionne en O^*(n'^2^k'^).

Ainsi l'algorithme fonctionne en O^*(n^{2'^k'}^).

Le nombre Grundy est le nombre maximum de couleurs d'une coloration gloutonne.

Pour tout k fixé, décider si le nombre Grundy d'un graphe est au plus k est polynomial. Il suffit pour cela de tester si G contient un des graphes appelés k-atomes comme sous-graphe induit. Il y a un nombre borné f(k) de k-atomes et ils sont tous de taille au plus 2^k. Ainsi l'algorithme fonctionne en O^*(n^'2^'k'^'^).

Une coloration gloutonne est une coloration obtenue à partir d'un ordre (v₁, v₂, ... , v_1n) en appliquant l'algorithme glouton. (i.e. pour i de 1 à n, on colore v_i avec le plus petit entier non attribué à ses voisins). Le nombre de Grundy est le nombre maximum de couleurs d'une coloration gloutonne.

Le joueur 1 place ses k gendarmes, le joueur 2 place le voleur. Le but pour le joueur 1 est de capturer le voleur et le but du voleur est d'échapper indéfinimenet aux gendarmes.

Soit G=(V,E). Un sous-ensemble S de V est un séparateur minimal, s'il existe 2 composantes connexes C,D de G-S telles que N(C)=N(D)=S.

En considérant un graphe ayant deux sommets u et v reliés par n/3 chemins indépendants de longueur (nombre d'aretes) 4, on obtient une borne inférieure de 3^n/3. Si S est un s'eparateur minimal alors l'un des enembles S, C et D est de taille au plus n/3. On a donc une borne supérieure simple en \Sum_{i=1}^{n/3} C(i,n). La meilleure borne supérieure actuelle due à Fomin et Villanger est de 1.6181ⁿ

En considérant un graphe ayant deux sommets u et v reliés par n/3 chemins indépendants de longueur (nombre d'aretes) 4, on obtient une borne inférieure simple est 3^n/3.

Une borne inférieure simple est 3^n/3.

Une borne inférieure simple est 3^(n/3)).

Une borne supérieure simple est 3.C(n/3,n). La meilleure borne supérieure actuelle due à Fomin et Villanger est de 1.6181ⁿ

Problème 4 : Algorithme exact de coloration des aretes.

Problème 6 : Coloration des aretes d'un graphe complet.

Problème 4 : Algorithme exact de coloration des aretes.

Problème 5 : Coloration par listes des graphes d'intervalles.

Le problème consiste à trouverle meilleur algorithme qui etant donnes un graphe d'intervalles G et une assignation de listes L repond s'il existe une L-coloration de G ou pas. Le meilleur algorithme actuel fonctionne en O*(2^n). Existe-t-il un algorithme en O^*(c^n) pour un c<1 ?

---

Problème 3 : Gendarmes et voleur :

Soit G=(V,E). Un sous-ensemble S de V est un "séparateur minimal", s'il existe 2 composantes connexes C,D de G-S telles que N(C)=N(D)=S.

Quel est le nombre maximum de séparateurs minimaux dans un graphe d'ordre n ?

Une borne inférieure simple est (3^(1/3))^n. Une borne supérieure simple est 3.C(n/3,n). La meilleure borne supérieure actuelle due à Fomin et Villanger est de 1.6181^n

Problème 2 : Coloration gloutonne.

Le nombre de Grundy est le nombre maximum de couleurs utilisées parmi tous les ordres possibles.

Problème 1 : Nombre de séparateurs minimaux.

(:notitle:)

(:notitle)

Nombre de séparateurs minimaux dans G ?

Une borne supérieure simple est 3.C(n/3,n). Fomin et Villanger ont un algorithme en 1.6181^n

Problème 5 : Coloration (encore et encore) :

List coloring pour les graphes d'intervalle : algorithme en 2^n, existe-t-il un algorithme en c^n (c<1) ????

Problème 6 : Coloration (trop) :

X'(K_n) : existe-t-il une coloration optimale autre que prendre les arêtes deux à deux et faire des rotations ????

Problème 4 : Coloration (encore) :

Problème 2 : Coloration gloutonne :

Le grundy number est le nombre maximum de couleurs utilisées parmi tous les ordres possibles.

A quelle classe de complexité appartient ce problème ???? Peut-on trouver un algorithme exact meilleur que N^(2^k) ????

Problème 3 : Gendarmes et voleur :

Soit G=(V,E). Jeu à tour de rôle (deux joueurs). Le joueur 1 place ses k gendarmes, le joueur 2 place le voleur. Le but pour le joueur 1 est de capturer le voleur et le but du voleur est d'échappe indéfinimenet aux gendarmes.

Trouver le nombre minimum de gendarmes nécessaires pour capturer le voleur est le cop-number cn(G).

Est-ce que cn(G)=O(n^(1/2)) ????

On sait que cn(G)=O(n/log(n)), cn(G)<=3 pour les planaires.

Est-ce que cn(G)<=g+3 pour les graphes de genre g ????

On sait que cn(G)<=1.5g+3

De plus, on sait que le problème est NP-hard mais appartient-il à NP ?

Pour les grilles si le voleur a vitesse 2 et les gendarmes ont vitesse 1, cn(G) ????

Combien existe-t-il de séparateurs minimaux dans G ?

Une borne inférieure simple est (3^(1/3))^n (avec n=|V|). Une borne supérieure simple est 3.C(n/3,n).

Problème 1 : Séparateurs minimaux :

Soit G=(V,E). Un sous-ensemble S de V est séparateur minimal, s'il existe 2 composantes connexes C,D de G-S telles que N(C)=N(D)=S.