On the b-coloring of P4-tidy graphs

BETANCUR VELASQUEZ, CLARA; BONOMO, FLAVIA; KOCH, IVO

DISCRETE APPLIED MATHEMATICS

ELSEVIER SCIENCE BV

Año: 2011 vol. 159 p. 60 - 68

0166-218X

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), and it is -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-tidy graphs (a generalization of many classes of graphs with few induced P_4s) are b-continuous and b-monotonic. Furthermore, we describe a polynomial time algorithm to compute the b-chromatic number for this class of graphs.