On The b-Chromatic Number of Regular Bounded GraphsReport as inadecuate



 On The b-Chromatic Number of Regular Bounded Graphs


On The b-Chromatic Number of Regular Bounded Graphs - Download this document for free, or read online. Document in PDF available to download.

Download or read this book online for free in PDF: On The b-Chromatic Number of Regular Bounded Graphs
A $b$-coloring of a graph is a proper coloring such that every color class contains a vertex adjacent to at least one vertex in each of the other color classes. The $b$-chromatic number of a graph $G$, denoted by $bG$, is the maximum integer $k$ such that $G$ admits a $b$-coloring with $k$ colors. El Sahili and Kouider conjectured that $bG=d+1$ for $d$-regular graph with girth 5, $d\geq4$. In this paper, we prove that this conjecture holds for $d$-regular graph with at least $d^3+d$ vertices. More precisely we show that $bG=d+$1 for $d$-regular graph with at least $d^3+d$ vertices and containing no cycle of order 4. We also prove that $bG=d+1$ for $d$-regular graphs with at least $2d^3+2d-2d^2$ vertices improving Cabello and Jakovac bound.



Author: Amine El Sahili; Mekkia Kouider; Maidoun Mortada

Source: https://archive.org/







Related documents