{
  "id": "1109.2769",
  "version": "v2",
  "published": "2011-09-13T13:03:16.000Z",
  "updated": "2011-10-13T12:31:05.000Z",
  "title": "Upper bound for the rainbow connection number of bridgeless graphs with diameter 3",
  "authors": [
    "Hengzhe Li",
    "Xueliang Li",
    "Yuefang Sun"
  ],
  "comment": "17 pages",
  "categories": [
    "math.CO"
  ],
  "abstract": "A path in an edge-colored graph $G$, where adjacent edges may have the same color, is called rainbow if no two edges of the path are colored the same. The rainbow connection number $rc(G)$ of $G$ is the smallest integer $k$ for which there exists a $k$-edge-coloring of $G$ such that every pair of distinct vertices of $G$ is connected by a rainbow path. It is known that for every integer $k\\geq 2$ deciding if a graph $G$ has $rc(G)\\leq k$ is NP-Hard, and a graph $G$ with $rc(G)\\leq k$ has diameter $diam(G)\\leq k$. In foregoing papers, we showed that a bridgeless graph with diameter 2 has rainbow connection number at most 5. In this paper, we prove that a bridgeless graph with diameter 3 has rainbow connection number at most 9. We also prove that for any bridgeless graph $G$ with radius $r$, if every edge of $G$ is contained in a triangle, then $rc(G)\\leq 3r$. As an application, we get that for any graph $G$ with minimum degree at least 3, $rc(L(G))\\leq 3 rad(L(G))\\leq 3 (rad(G)+1)$.",
  "revisions": [
    {
      "version": "v2",
      "updated": "2011-10-13T12:31:05.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "05C15",
      "05C40"
    ],
    "keywords": [
      "rainbow connection number",
      "bridgeless graph",
      "upper bound",
      "adjacent edges",
      "smallest integer"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 17,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2011arXiv1109.2769L"
    }
  }
}