Auteur : Ana Shirley FERREIRA DA SILVA
Directeur de thèse : Frédéric MAFFRAY
Date : 24 novembre 2010
"Une coloration des sommets de G s'appelle une b-coloration si chaque classe de couleur contient au moins un sommet qui a un voisin dans toutes les autres classes de couleur. Le nombre b-chromatique Xb(G) de G est le plus grand entier k pour lequel G a une b-coloration avec k couleurs. Ces notions ont été introduites par Irving et Manlove en 1999. Elles permettent d'évaluer les performances de certaines algorithmes de coloration.
Irving et Manlove ont montré que le calcul du nombre b-chromatique d'un graphe est un problème NP-difficile et qu'il peut être résolu en temps polynomial pour les arbres.
Dans cette thèse, nous généralisons le résultat d'Irving et Manlove pour les cactus dont le ""m-degrè"" est au moins 7 et pour les graphesplanaires extérieurs dont la maille est au moins 8. (Le m-degré m(G) est le plus grand entier d tel que G a au moins d sommets de degré au moins d-1) Nous démontrons un résultats semblable pour le produit cartésien d'un arbre par une chaîne, un cycle ou une étoile.Pour ce qui concerne les graphes dont les blocs sont des cliques, nous montrons quel le problème avec un nombre de couleurs fixé peut être résolu en temps polynomial et nus présentons des cas où le problème de décision peut être résolu. Toutefois, nous avons constaté que la différence m(G) - Xb(G) peut être arbitrairement grande pour les graphes blocs, ce qui montre qu'avoir une structure arborescence n'est pas suffisant pour que le graphe satisfasse xb(g) >m(G)-1"
Mots clés : nombre b-chromatique, m-degré, arbres, cactus, graphe planaire exterieure, graph bloc, produit cartésien.
Directeur de thèse : Frédéric MAFFRAY
Date : 24 novembre 2010
Le nombre B-chromatique de quelques classe de graphes
généralisant les arbres.
généralisant les arbres.
"Une coloration des sommets de G s'appelle une b-coloration si chaque classe de couleur contient au moins un sommet qui a un voisin dans toutes les autres classes de couleur. Le nombre b-chromatique Xb(G) de G est le plus grand entier k pour lequel G a une b-coloration avec k couleurs. Ces notions ont été introduites par Irving et Manlove en 1999. Elles permettent d'évaluer les performances de certaines algorithmes de coloration.
Irving et Manlove ont montré que le calcul du nombre b-chromatique d'un graphe est un problème NP-difficile et qu'il peut être résolu en temps polynomial pour les arbres.
Dans cette thèse, nous généralisons le résultat d'Irving et Manlove pour les cactus dont le ""m-degrè"" est au moins 7 et pour les graphesplanaires extérieurs dont la maille est au moins 8. (Le m-degré m(G) est le plus grand entier d tel que G a au moins d sommets de degré au moins d-1) Nous démontrons un résultats semblable pour le produit cartésien d'un arbre par une chaîne, un cycle ou une étoile.Pour ce qui concerne les graphes dont les blocs sont des cliques, nous montrons quel le problème avec un nombre de couleurs fixé peut être résolu en temps polynomial et nus présentons des cas où le problème de décision peut être résolu. Toutefois, nous avons constaté que la différence m(G) - Xb(G) peut être arbitrairement grande pour les graphes blocs, ce qui montre qu'avoir une structure arborescence n'est pas suffisant pour que le graphe satisfasse xb(g) >m(G)-1"
Mots clés : nombre b-chromatique, m-degré, arbres, cactus, graphe planaire exterieure, graph bloc, produit cartésien.