{
  "id": "2308.15588",
  "version": "v1",
  "published": "2023-08-29T19:32:21.000Z",
  "updated": "2023-08-29T19:32:21.000Z",
  "title": "On Edge Coloring of Multigraphs",
  "authors": [
    "Guangming Jing"
  ],
  "categories": [
    "math.CO"
  ],
  "abstract": "Let $\\Delta(G)$ and $\\chi'(G)$ be the maximum degree and chromatic index of a graph $G$, respectively. Appearing in different format, Gupta\\,(1967), Goldberg\\,(1973), Andersen\\,(1977), and Seymour\\,(1979) made the following conjecture: Every multigraph $G$ satisfies $\\chi'(G) \\le \\max\\{ \\Delta(G) + 1, \\Gamma(G) \\}$, where $\\Gamma(G) = \\max_{H \\subseteq G} \\left\\lceil \\frac{ |E(H)| }{ \\lfloor \\tfrac{1}{2} |V(H)| \\rfloor} \\right\\rceil$ is the density of $G$. In this paper, we present a polynomial-time algorithm for coloring any multigraph with $\\max\\{ \\Delta(G) + 1, \\Gamma(G) \\}$ many colors, confirming the conjecture. Since $\\chi'(G)\\geq \\max\\{ \\Delta(G), \\Gamma(G) \\}$, this algorithm gives a proper edge coloring that uses at most one more color than the optimum. As determining the chromatic index of an arbitrary graph is $NP$-hard, the $\\max\\{ \\Delta(G) + 1, \\Gamma(G) \\}$ bound is best possible for efficient proper edge coloring algorithms on general multigraphs, unless $P=NP$.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2023-08-29T19:32:21.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "chromatic index",
      "efficient proper edge coloring algorithms",
      "conjecture",
      "polynomial-time algorithm",
      "general multigraphs"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}