On the b-Coloring of Cographs and P-4-Sparse Graphs

摘要

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.