On the b b -chromatic number of regular graphs without 4-cycle
The b b -chromatic number of a graph G G , denoted by ?(G) ? ( G ) , is the largest integer k k for which G G admits a proper coloring by k 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 d -regular graph G G which contains no 4-cycle, ? ( G ) ? ? d + 3 2 ? ; and besides, if G G has a triangle, then ? ( G ) ? ? d + 4 2 ? . Also, if G G is a d d -regular graph that contains no 4-cycle and diam(G)?6 d i a m ( G ) ? 6 , then ?(G)=d+1 ? ( G ) = d + 1 . Finally, we show that, for any d d -regular graph G G which does not contain 4-cycle and has vertex connectivity less than or equal to d + 1 2 , ?(G)=d+1 ? ( G ) = d + 1 . Moreover, when the vertex connectivity is less than 3 d ? 3 4 , we introduce a lower bound for the b b -chromatic number in terms of the vertex connectivity.
vertex connectivity b b -chromatic number b b b b b girth diameter