2011/03/08 by Saeed Shaebani, Shaebani, Saeed
Mathematics · #Combinatorics (math.CO) #FOS: Mathematics #math.CO
paper · pdf · doi:10.48550/arxiv.1103.1521
arxiv created 2011/03/08 · arxiv updated 2011/03/09
The b-chromatic number of a graph G, denoted by ϕ(G), is the largest integer k that G admits a proper k-coloring such that each color class has a vertex that is adjacent to at least one vertex in each of the other color classes. We prove that for each d-regular graph G which contains no 4-cycle, ϕ(G)≥\lfloor(d+3)/(2)\rfloor and if G has a triangle, then ϕ(G)≥\lfloor(d+4)/(2)\rfloor. Also, if G is a d-regular graph which contains no 4-cycle and diam(G)≥6, then ϕ(G)=d+1. Finally, we show that for any d-regular graph G which does not contain 4-cycle and κ(G)≤(d+1)/(2), ϕ(G)=d+1.