2013/02/18 by Amine El Sahili, Sahili, Amine El, Hamamache Kheddouci +5
Computer Science · Mathematics · #Advanced Graph Theory Research #Graph Labeling and Dimension Problems #Limits and Structures in Graph Theory #math.CO
paper · pdf · doi:10.48550/arxiv.1302.4214
arxiv created 2013/02/18 · arxiv updated 2013/02/19
The b-chromatic number of a graph G, denoted by b(G), is the largest positive integer k such that there exists a proper coloring for G with k colors in which every color class contains at least one vertex adjacent to some vertex in each of the other color classes, such a vertex is called a dominant vertex. The f-chromatic vertex number of a d-regular graph G, denoted by f(G), is the maximum number of dominant vertices of distinct colors in a proper coloring with d+1 colors. El Sahili and Kouider conjectured that b(G)=d+1 for any d-regular graph G of girth 5. We study this conjecture by giving some partial answers under supplementary conditions.