Goldberg's conjecture

Definitions and mathematical statement

Shared notation.

$\mathbb N=\{1,2,\ldots\}$, and $\mathbb Z,\mathbb Q,\mathbb R,\mathbb C$ denote the integers, rationals, reals and complex numbers. Any other conventions are specified locally.

For a finite loopless multigraph $G$ of maximum degree $\Delta(G)$ and chromatic index $\chi'(G)$, define \[w(G)=\max_{H\subseteq G,\ |V(H)|\ge2}\left\lceil\frac{|E(H)|}{\lfloor |V(H)|/2\rfloor}\right\rceil,\] taking $w(G)=0$ if no such subgraph exists. Restricting to at least two vertices makes the displayed denominator nonzero; even-order subgraphs give a value at most $\Delta(G)$.

Statement recorded in the supplied source.

The main recorded conjecture is \[\chi'(G)\le\max\{\Delta(G)+1,w(G)\}.\] The same source gives two related conjectural bounds, \[\chi'(G)\le\max\{\Delta(G),w(G)\}+1\quad\text{and}\quad\chi'(G)\le\max\{\Delta(G),w(G)+1\}.\] [S2]

Short English statement

Does maximum degree together with the densest subgraph obstruction determine the proposed edge-coloring bounds for multigraphs?

Sources

• S1 ULAM.AI and the UnsolvedMath Contributors, UnsolvedMath: A Curated Collection of Open Mathematics Problems, record 3204 (OPG-2242). CC BY 4.0. https://huggingface.co/datasets/ulamai/UnsolvedMath.
• S2 Open Problem Garden, Goldberg's conjecture, original node 2242, statement and mathematical discussion. https://www.openproblemgarden.org/op/goldbergs_conjecture.