Le nombre b-chromatique de quelques classes de graphes généralisant les arbres

A vertex colouring of a graph G is called a b-colouring if each colour class contains at least one vertex that has a neighbour in all other colour classes. The b-chromatic number b(G) of G is the largest integer k for which G has a b-colouring with k colours. These concepts have been introduced by Irving and Manlove in 1999. They allow the analisys of the performance of some algorithms for colouring. Irving and Manlove showed that finding the b-chromatic number is NPhard for general graphs, while it can be found in polynomial time for trees. A question that naturally arises is to investigate the graphs that have a "tree structure", for instance: cactus, chordal graphs, series-parallel graphs, block graphs, etc. In this thesis, we generalize the result of Irving and Manlove for cacti with "m-degree" at least 7 and for outerplanar graphs with girth at least 8. (The m-degree m(G) is the largest integer d such that G has at least d vertices of degree at least d − 1.) We prove a similar result for the cartesian product of a tree by a path, a cycle or a star. Regarding graphs whose blocks are cliques, we show that the fixed-parameter problem can be solved in polynomial time and we present cases where the decision problem can be solved. However, we found that the difference m(G)−b(G) can be arbitrarily large for block graphs, which shows that the tree structure is not sufficient for having b(G)>= m(G) − 1.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 b(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 certains 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. Une question qui se pose naturellement est donc d'enquêter sur les graphes qui ont une structure proche des arbres: cactus, graphes triangulés, graphes série-parallèles, "block" graphes, etc. 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 graphes planaires 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ésultat 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 que le problème avec un nombre de couleurs fixé peut être résolu en temps polynomial et nous 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)−b(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 b(G)>= m(G) − 1