{
  "id": "1302.4209",
  "version": "v1",
  "published": "2013-02-18T10:17:29.000Z",
  "updated": "2013-02-18T10:17:29.000Z",
  "title": "On The b-Chromatic Number of Regular Bounded Graphs",
  "authors": [
    "Amine El Sahili",
    "Mekkia Kouider",
    "Maidoun Mortada"
  ],
  "categories": [
    "math.CO"
  ],
  "abstract": "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 $b(G)$, is the maximum integer $k$ such that $G$ admits a $b$-coloring with $k$ colors. El Sahili and Kouider conjectured that $b(G)=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 $b(G)=d+$1 for $d$-regular graph with at least $d^3+d$ vertices and containing no cycle of order 4. We also prove that $b(G)=d+1$ for $d$-regular graphs with at least $2d^3+2d-2d^2$ vertices improving Cabello and Jakovac bound.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2013-02-18T10:17:29.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "regular bounded graphs",
      "regular graph",
      "b-chromatic number",
      "color class contains",
      "vertex adjacent"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2013arXiv1302.4209E"
    }
  }
}