Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4653414 | European Journal of Combinatorics | 2015 | 11 Pages |
Abstract
A b-coloring of a graph is a proper coloring of its vertices such that every color class contains a vertex that has neighbors in all other color classes. The b-chromatic number of a graph is the largest integer b(G) such that the graph has a b-coloring with b(G) colors. This metric is upper bounded by the largest integer m(G) for which G has at least m(G) vertices with degree at least m(G)â1. There are a number of results reporting that graphs with high girth have high b-chromatic number when compared to m(G). Here, we prove that every graph with girth at least 7 has b-chromatic number at least m(G)â1. Our proof also yields a polynomial algorithm that produces an optimal b-coloring of these graphs.
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
V. Campos, C. Lima, A. Silva,