Efficiently list‐edge coloring multigraphs asymptotically optimally. Issue 4 (6th February 2022)

• Record Type: Journal Article
• Authors: Iliopoulos, Fotis; Sinclair, Alistair
• Is Part Of: Random structures & algorithms. Volume 61:Issue 4(2022)
• Page Start: 724
• Page End: 753
• Publication Date: 2022-02-06
• Subjects: edge coloring -- Goldberg–Seymour conjecture -- list‐edge‐coloring conjecture -- multigraphs; Random graphs -- Periodicals; Mathematical analysis -- Periodicals; 519
• DOI: 10.1002/rsa.21074
• Languages: English
• ISSNs: 1042-9832

Abstract

Abstract: We give polynomial time algorithms for the seminal results of Kahn, who showed that the Goldberg–Seymour and list‐coloring conjectures for (list‐)edge coloring multigraphs hold asymptotically. Kahn's arguments are based on the probabilistic method and are non‐constructive. Our key insight is that we can combine sophisticated techniques due to Achlioptas, Iliopoulos, and Kolmogorov for the analysis of local search algorithms with correlation decay properties of the probability spaces on matchings used by Kahn in order to construct efficient edge‐coloring algorithms.