{
  "id": "1105.2909",
  "version": "v1",
  "published": "2011-05-14T18:23:26.000Z",
  "updated": "2011-05-14T18:23:26.000Z",
  "title": "The b-Chromatic Number of Regular Graphs via The Edge Connectivity",
  "authors": [
    "Saeed Shaebani"
  ],
  "categories": [
    "math.CO"
  ],
  "abstract": "\\noindent The b-chromatic number of a graph $G$, denoted by $\\phi(G)$, is the largest integer $k$ that $G$ admits a proper coloring by $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. El Sahili and Kouider [About b-colorings of regular graphs, Res. Rep. 1432, LRI, Univ. Orsay, France, 2006] asked whether it is true that every $d$-regular graph $G$ of girth at least 5 satisfies $\\phi(G)=d+1$. Blidia, Maffray, and Zemir [On b-colorings in regular graphs, Discrete Appl. Math. 157 (2009), 1787-1793] showed that the Petersen graph provides a negative answer to this question, and then conjectured that the Petersen graph is the only exception. In this paper, we investigate a strengthened form of the question. The edge connectivity of a graph $G$, denoted by $\\lambda(G)$, is the minimum cardinality of a subset $U$ of $E(G)$ such that $G\\setminus U$ is either disconnected or a graph with only one vertex. A $d$-regular graph $G$ is called super-edge-connected if every minimum edge-cut is the set of all edges incident with a vertex in $G$, i.e., $\\lambda(G)=d$ and every minimum edge-cut of $G$ isolates a vertex. We show that if $G$ is a $d$-regular graph that contains no 4-cycle, then $\\phi(G)=d+1$ whenever $G$ is not super-edge-connected.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2011-05-14T18:23:26.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "regular graph",
      "edge connectivity",
      "b-chromatic number",
      "petersen graph",
      "minimum edge-cut"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2011arXiv1105.2909S"
    }
  }
}