Autor(es)

Flavia Bonomo and Oliver Schaudt and Maya Stein and Mario Valencia-Pabon

URL Pública

Abstract

A b-coloring of a graph is a proper coloring such that every color class contains a vertex that is adjacent to all other color classes. The b-chromatic number of a graph , denoted by , is the maximum number such that admits a b-coloring with colors. A graph is called b-continuous if it admits a b-coloring with colors, for every , and b-monotonic if for every induced subgraph of , and every induced subgraph of . We investigate the b-chromatic number of graphs with stability number two. These are exactly the complements of triangle-free graphs, thus including all complements of bipartite graphs. The main results of this work are the following: (1) We characterize the b-colorings of a graph with stability number two in terms of matchings with no augmenting paths of length one or three. We derive that graphs with stability number two are b-continuous and b …