{
  "id": "2210.12291",
  "version": "v1",
  "published": "2022-10-21T22:55:28.000Z",
  "updated": "2022-10-21T22:55:28.000Z",
  "title": "Rainbow Connection for Complete Multipartite Graphs",
  "authors": [
    "Igor Araujo",
    "Kareem Beniassa",
    "Richard Bi",
    "Sean English",
    "Shengan Wu",
    "Pai Zheng"
  ],
  "comment": "10 pages, 4 figures",
  "categories": [
    "math.CO"
  ],
  "abstract": "A path in an edge-colored graph is said to be rainbow if no color repeats on it. An edge-colored graph is said to be rainbow $k$-connected if every pair of vertices is connected by $k$ internally disjoint rainbow paths. The rainbow $k$-connection number $\\mathrm{rc}_k(G)$ is the minimum number of colors $\\ell$ such that there exists a coloring with $\\ell$ colors that makes $G$ rainbow $k$-connected. Let $f(k,t)$ be the minimum integer such that every $t$-partite graph with part sizes at least $f(k,t)$ has $\\mathrm{rc}_k(G) \\le 4$ if $t=2$ and $\\mathrm{rc}_k(G) \\le 3$ if $t \\ge 3$. Answering a question of Fujita, Liu and Magnant, we show that \\[ f(k,t) = \\left\\lceil \\frac{2k}{t-1} \\right\\rceil \\] for all $k\\geq 2$, $t\\geq 2$. We also give some conditions for which $\\mathrm{rc}_k(G) \\le 3$ if $t=2$ and $\\mathrm{rc}_k(G) \\le 2$ if $t \\ge 3$.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2022-10-21T22:55:28.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "05C15",
      "05C38",
      "05C40"
    ],
    "keywords": [
      "complete multipartite graphs",
      "rainbow connection",
      "internally disjoint rainbow paths",
      "edge-colored graph",
      "part sizes"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 10,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}