On the b-coloring of cographs and P_4-sparse graphs

BONOMO, FLAVIA; DURÁN, GUILLERMO; MAFFRAY, FRÉDÉRIC; MARENCO, JAVIER; VALENCIA-PABON, MARIO

GRAPHS AND COMBINATORICS

Springer

Año: 2009 vol. 25 p. 153 - 167

0911-0119

A b-coloring of a graph is a coloring such that every color class admits a vertex adjacent to at least one vertex receiving each of the colors not assigned to it. The b-chromatic number of a graph G, denoted by chi_b(G), is the maximum number t such that G admits a b-coloring with t colors. A graph G is b-continuous if it admits a b-coloring with t colors, for every t=chi(G), ..., chi_b(G). We define a graph G to be  b-monotonic if chi_b(H_1) >= chi_b(H_2) for every induced subgraph H_1 of G, and every induced subgraph H_2 of H_1. In this work, we prove that P_4-sparse graphs (and, in particular, cographs) are b-continuous and b-monotonic. Besides, we describe a dynamic programming algorithm to compute the b-chromatic number in polynomial time within these graph classes.