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 χ′(G) satisfies χ′(G) ≤ max{∆(G)+1,⌈ρ(G)⌉}, where ρ(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 ∼ M(n,m) typically satisfies χ′(G) = max{∆(G),⌈ρ(G)⌉}. In particular, we show that if n is even and m := m(n), then χ′(M) = ∆(M) for a typical M ∼ M(n,m). Furthermore, for a fixed ε > 0, if n is odd, then a typical M ∼ M(n,m) has χ′(M) = ∆(M) for m ≤ (1−ε)n3 logn, and χ′ (M ) = ⌈ρ(M )⌉ for m ≥ (1 + ε)n3 log n. To prove this result, we develop a new structural characterization of multigraphs with chromatic index larger than the maximum degree.
Collections
Cite this version of the work
Penny Haxell, Michael Krivelevich, Gal Kronenberg
(2019).
Goldberg's conjecture is true for random multigraphs. UWSpace.
http://hdl.handle.net/10012/16046
Other formats
The following license files are associated with this item: