On The b-Chromatic Number of Regular Graphs Without 4-Cycle

Abstract

The b-chromatic number of a graph $G$, denoted by $\varphi (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, $\varphi (G)\ge \lfloor \frac{d+3}{2}\rfloor$ and if $G$ has a triangle, then $\varphi (G)\ge \lfloor \frac{d+4}{2}\rfloor$. Also, if $G$ is a $d$-regular graph which contains no 4-cycle and $diam(G)\ge 6$, then $\varphi (G)=d+1$. Finally, we show that for any $d$-regular graph $G$ which does not contain 4-cycle and $\kappa (G)\le \frac{d+1}{2}$, $\varphi (G)=d+1$.

References in corpus (1)

• Bounds for the $b$-chromatic number of some families of graphs