Goldberg's Conjecture is true for random multigraphs

Abstract

In the 70s, Goldberg, and independently Seymour, conjectured that for any multigraph $G$, the chromatic index ${\chi }^{\prime }(G)$ satisfies ${\chi }^{\prime }(G)\le \max \{\Delta (G)+1,\lceil \rho (G)\rceil \}$, where $\rho (G)=\max \{\frac{e(G[S])}{\lfloor |S|/2\rfloor }\mid S\subseteq V\}$. We show that their conjecture (in a stronger form) is true for random multigraphs. Let $M(n,m)$ be the probability space consisting of all loopless multigraphs with $n$ vertices and $m$ edges, in which $m$ pairs from $[n]$ are chosen independently at random with repetitions. Our result states that, for a given $m:=m(n)$, $M\sim M(n,m)$ typically satisfies ${\chi }^{\prime }(G)=\max \{\Delta (G),\lceil \rho (G)\rceil \}$. In particular, we show that if $n$ is even and $m:=m(n)$, then ${\chi }^{\prime }(M)=\Delta (M)$ for a typical $M\sim M(n,m)$. Furthermore, for a fixed $\epsilon >0$, if $n$ is odd, then a typical $M\sim M(n,m)$ has ${\chi }^{\prime }(M)=\Delta (M)$ for $m\le (1-\epsilon )n^3\log n$, and ${\chi }^{\prime }(M)=\lceil \rho (M)\rceil$ for $m\ge (1+\epsilon )n^3\log n$.

26 pages