{
  "id": "2411.09095",
  "version": "v1",
  "published": "2024-11-13T23:59:27.000Z",
  "updated": "2024-11-13T23:59:27.000Z",
  "title": "Tight minimum colored degree condition for rainbow connectivity",
  "authors": [
    "Andrzej Czygrinow",
    "Xiaofan Yuan"
  ],
  "categories": [
    "math.CO"
  ],
  "abstract": "Let $G = (V, E)$ be a graph on $n$ vertices, and let $c: E \\to P$, where $P$ is a set of colors. Let $\\delta^c(G) = \\min_{v \\in V} \\{ d^{c}(v) \\}$ where $d^c(v)$ is the number of colors on edges incident to a vertex $v$ of $G$. In 2011, Fujita and Magnant showed that if $G$ is a graph on $n$ vertices that satisfies $\\delta^c(G)\\geq n/2$, then for every two vertices $u, v$ there is a properly-colored $u,v$-path in $G$. In this paper, we show that the same bound for $\\delta^c(G)$ implies that any two vertices are connected by a rainbow path.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2024-11-13T23:59:27.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "05C35",
      "05C15"
    ],
    "keywords": [
      "tight minimum colored degree condition",
      "rainbow connectivity",
      "rainbow path",
      "edges incident"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}