Efficiently list‐edge coloring multigraphs asymptotically optimally

DOI10.1002/rsa.21074OpenAlexW4210692625MaRDI QIDQ6052475

Fotis Iliopoulos, Alistair Sinclair

Publication date: 17 October 2023

Published in: Random Structures & Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1002/rsa.21074

zbMATH Keywords

edge coloringmultigraphsGoldberg-Seymour conjecturelist-edge-coloring conjecture

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Graph theory (including graph drawing) in computer science (68R10) Coloring of graphs and hypergraphs (05C15) Randomized algorithms (68W20)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Rainbow Hamilton cycles in uniform hypergraphs
• Approximating the chromatic index of multigraphs
• Lopsided Lovász Local lemma and Latin transversals
• Graph edge colouring: Tashkinov trees and Goldberg's conjecture
• Asymptotics of the chromatic index for multigraphs
• On the stochastic independence properties of hard-core distributions
• A bound on the total chromatic number
• A sublinear bound on the chromatic index of multigraphs
• The list chromatic number of graphs with small clique number
• Multicoloured Hamilton cycles
• Asymptotically good list-colorings
• What can be sampled locally?
• Random Walks That Find Perfect Objects and the Lovász Local Lemma
• Approximating the Permanent
• On the $1.1$ Edge-Coloring of Multigraphs
• A constructive proof of the general lovász local lemma
• Odd Minimum Cut-Sets and b-Matchings
• Commutativity in the Algorithmic Lovász Local Lemma
• On Brooks' Theorem for Sparse Graphs
• An Algorithmic Proof of the Lovász Local Lemma via Resampling Oracles
• An asymptotic approximation scheme for multigraph edge coloring
• Stochastic Control via Entropy Compression
• A constructive proof of the Lovász local lemma
• A Local Lemma for Focused Stochastic Algorithms
• Entropy, optimization and counting
• New Constructive Aspects of the Lovász Local Lemma
• Maximum matching and a polyhedron with 0,1-vertices
• Graph colouring and the probabilistic method
• A New Notion of Commutativity for the Algorithmic Lovász Local Lemma

This page was built for publication: Efficiently list‐edge coloring multigraphs asymptotically optimally