{
  "id": "2407.09403",
  "version": "v1",
  "published": "2024-07-12T16:30:03.000Z",
  "updated": "2024-07-12T16:30:03.000Z",
  "title": "A short proof of the Goldberg-Seymour conjecture",
  "authors": [
    "Guantao Chen",
    "Yanli Hao",
    "Xingxing Yu",
    "Wenan Zang"
  ],
  "categories": [
    "math.CO"
  ],
  "abstract": "For a multigraph $G$, $\\chi'(G)$ denotes the chromatic index of $G$, $\\Delta(G)$ the maximum degree of $G$, and $\\Gamma(G) = \\max\\left\\{\\left\\lceil \\frac{2|E(H)|}{|V(H)|-1} \\right\\rceil: H \\subseteq G \\text{ and } |V(H)| \\text{ odd}\\right\\}$. As a generalization of Vizing's classical coloring result for simple graphs, the Goldberg-Seymour conjecture, posed in the 1970s, states that $\\chi'(G)=\\max\\{\\Delta(G), \\Gamma(G)\\}$ or $\\chi'(G)=\\max\\{\\Delta(G) + 1, \\Gamma(G)\\}$. Hochbaum, Nishizeki, and Shmoys further conjectured in 1986 that such a coloring can be found in polynomial time. A long proof of the Goldberg-Seymour conjecture was announced in 2019 by Chen, Jing, and Zang, and one case in that proof was eliminated recently by Jing (but the proof is still long); and neither proof has been verified. In this paper, we give a proof of the Goldberg-Seymour conjecture that is significantly shorter and confirm the Hochbaum-Nishizeki-Shmoys conjecture by providing an $O(|V|^5|E|^3)$ time algorithm for finding a $\\max\\{\\Delta(G) + 1, \\Gamma(G)\\}$-edge-coloring of $G$.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2024-07-12T16:30:03.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "goldberg-seymour conjecture",
      "short proof",
      "maximum degree",
      "vizings classical coloring result",
      "time algorithm"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}