|
Publications
Réunions Problèmes Participants |
Problème 1 : Nombre de séparateurs minimaux.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 ? 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 3n/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.6181n Problème 2 : Coloration gloutonne.Une coloration gloutonne est une coloration obtenue à partir d'un ordre (v1, v2, ... , vn) en appliquant l'algorithme glouton. (i.e. pour i de 1 à n, on colore vi avec le plus petit entier non attribué à ses voisins). 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. Voir [Zak06]. Il y a un nombre borné f(k) de k-atomes et ils sont tous de taille au plus 2k. Ainsi l'algorithme fonctionne en O*(n2^k). 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é ci-dessus en O*(n2^k)? [Zak06] M. Zaker. Results on the Grundy chromatic number of graphs. Discrete Math. 306(23):3166–3173, 2006. 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. 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. Le cop-number d'un graphe G, noté cn(G), est le nombre minimum de gendarmes nécessaires pour capturer le voleur. Est-ce que cn(G)=O(n1/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. 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. 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? Problème 4 : Algorithme exact de coloration des arêtes.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. 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? [Hol81] I. Holyer. The NP-completeness of edge-coloring. SIAM J. Computing 2:225–231, 1981. Problème 5 : Coloration par listes des graphes d'intervalles.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*(2n). Existe-t-il un algorithme en O*(cn) pour un c<1 ? Problème 6 : Coloration des aretes d'un graphe complet.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 :
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é :
|