Le nombre b-chromatique de quelques classes de graphes généralisant les arbres
Ana Silva · HAL (Le Centre pour la Communication Scientifique Directe) · 2010
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.