Efficiently list‐edge coloring multigraphs asymptotically optimally
From MaRDI portal
Publication:6052475
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
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