Name
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{e(G[S])⌊|S|/2⌋|S⊆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−ε)n3logn, and χ′(M)=⌈ρ(M)⌉ for m≥(1+ε)n3logn. To prove this result, we develop a new structural characterization of multigraphs with chromatic index larger than the maximum degree. |
Year | DOI | Venue |
|---|---|---|
2019 | 10.1016/j.jctb.2019.02.005 | Journal of Combinatorial Theory, Series B |
Keywords | Field | DocType |
Chromatic index,Edge colouring,Random graphs,Random multigraphs | Edge coloring,Discrete mathematics,Combinatorics,Multigraph,Vertex (geometry),Probability space,Conjecture,Mathematics | Journal |
Volume | ISSN | Citations |
138 | 0095-8956 | 0 |
PageRank | References | Authors |
0.34 | 13 | 3 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| P. E. Haxell | 1 | 212 | 26.40 |
| michael krivelevich | 2 | 1688 | 179.90 |
| Gal Kronenberg | 3 | 5 | 2.20 |