{
  "id": "2207.04254",
  "version": "v1",
  "published": "2022-07-09T11:45:27.000Z",
  "updated": "2022-07-09T11:45:27.000Z",
  "title": "The $\\!{}\\bmod k$ chromatic index of random graphs",
  "authors": [
    "Fábio Botler",
    "Lucas Colucci",
    "Yoshiharu Kohayakawa"
  ],
  "comment": "12 pages, 1 figure",
  "categories": [
    "math.CO"
  ],
  "abstract": "The $\\!{}\\bmod k$ chromatic index of a graph $G$ is the minimum number of colors needed to color the edges of $G$ in a way that the subgraph spanned by the edges of each color has all degrees congruent to $1\\!\\!\\pmod k$. Recently, the authors proved that the $\\!{}\\bmod k$ chromatic index of every graph is at most $198k-101$, improving, for large $k$, a result of Scott [Discrete Math. 175, 1-3 (1997), 289-291]. Here we study the $\\!{}\\bmod k$ chromatic index of random graphs. We prove that for every integer $k\\geq2$, there is $C_k>0$ such that if $p\\geq C_kn^{-1}\\log{n}$ and $n(1-p) \\rightarrow\\infty$ as $n\\to\\infty$, then the following holds: if $k$ is odd, then the $\\!{}\\bmod k$ chromatic index of $G(n,p)$ is asymptotically almost surely equal to $k$, while if $k$ is even, then the $\\!{}\\bmod k$ chromatic index of $G(2n,p)$ (respectively $G(2n+1,p)$) is asymptotically almost surely equal to $k$ (respectively $k+1$).",
  "revisions": [
    {
      "version": "v1",
      "updated": "2022-07-09T11:45:27.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "05C80",
      "05C15"
    ],
    "keywords": [
      "chromatic index",
      "random graphs",
      "surely equal",
      "discrete math",
      "minimum number"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 12,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}