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

The bb-chromatic number of a graph GG, denoted by φ(G)φ(G), is the largest integer kk for which GG admits a proper coloring by kk 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 dd-regular graph GG which contains no 4-cycle, φ(G)≥⌊d+32⌋; and besides, if GG has a triangle, then φ(G)≥⌊d+42⌋. Also, if GG is a dd-regular graph that contains no 4-cycle and diam(G)≥6diam(G)≥6, then φ(G)=d+1φ(G)=d+1. Finally, we show that, for any dd-regular graph GG which does not contain 4-cycle and has vertex connectivity less than or equal to d+12, φ(G)=d+1φ(G)=d+1. Moreover, when the vertex connectivity is less than 3d−34, we introduce a lower bound for the bb-chromatic number in terms of the vertex connectivity.