Goldberg's conjecture is true for random multigraphs

DOI10.1016/j.jctb.2019.02.005zbMath1415.05165arXiv1803.00908OpenAlexW2963637355WikidataQ128355318 ScholiaQ128355318MaRDI QIDQ2312622

Michael Krivelevich, Gal Kronenberg, Penny E. Haxell

Publication date: 17 July 2019

Published in: Journal of Combinatorial Theory. Series B (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1803.00908

zbMATH Keywords

random graphschromatic indexedge colouringrandom multigraphs

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Coloring of graphs and hypergraphs (05C15)

Related Items (1)

Graph edge coloring: a survey

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Approximating the chromatic index of multigraphs
• Graph edge colouring: Tashkinov trees and Goldberg's conjecture
• Edge-colouring random graphs
• Asymptotics of the chromatic index for multigraphs
• On the chromatic index of almost all graphs
• An extension of Vizing's adjacency lemma of edge chromatic critical graphs
• List edge and list total colourings of multigraphs
• Chromatic index determined by fractional chromatic index
• The list chromatic index of a bipartite multigraph
• Asymptotically good list-colorings
• Edge coloring multigraphs without small dense subsets
• Edge-coloring of multigraphs: Recoloring technique
• The NP-Completeness of Edge-Coloring
• On edge-colorings of graphs.
• On Multi-Colourings of Cubic Graphs, and Conjectures of Fulkerson and Tutte
• On a Correlation Inequality of Farr
• Paths in graphs
• A Combined Logarithmic Bound on the Chromatic Index of Multigraphs
• A Theorem on Coloring the Lines of a Network

This page was built for publication: Goldberg's conjecture is true for random multigraphs