info:eu-repo/semantics/article
On the b-coloring of P4-tidy graphs
Fecha
2011-01Registro en:
Betancur Velásquez, Clara Inés; Bonomo, Flavia; Koch, Ivo Valerio; On the b-coloring of P4-tidy graphs; Elsevier Science; Discrete Applied Mathematics; 159; 1; 1-2011; 60-68
0166-218X
CONICET Digital
CONICET
Autor
Betancur Velásquez, Clara Inés
Bonomo, Flavia
Koch, Ivo Valerio
Resumen
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 χ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=χ(G),...,χb(G), and it is b-monotonic if χb(H1) ≥ χb(H2) for every induced subgraph H1 of G, and every induced subgraph H2 of H1. In this work, we prove that P-tidy graphs (a generalization of many classes of graphs with few induced P4s) are b-continuous and b-monotonic. Furthermore, we describe a polynomial time algorithm to compute the b-chromatic number for this class of graphs.