On the b-chromatic number of regular graphs without 4-cycle

AbstractThe b-chromatic number of a graph G, denoted by φ(G), is the largest integer k for which G admits a proper coloring by k colors, 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)≥⌊d+32⌋; and besides, if G has a triangle, then φ(G)≥⌊d+42⌋. Also, if G is a d-regular graph that 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 has vertex connectivity less than or equal to d+12, φ(G)=d+1. Moreover, when the vertex connectivity is less than 3d−34, we introduce a lower bound for the b-chromatic number in terms of the vertex connectivity