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

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

2011-03-08

arxiv.org/abs/1103.1521v1

Mathematics

Combinatorics

Scientific paper

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

Affiliated with

Also associated with

No associations

Rating

On The b-Chromatic Number of Regular Graphs Without 4-Cycle does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with On The b-Chromatic Number of Regular Graphs Without 4-Cycle, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and On The b-Chromatic Number of Regular Graphs Without 4-Cycle will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-82596