Acyclic edge coloring through the Lovász local lemma
From MaRDI portal
Publication:507595
DOI10.1016/j.tcs.2016.12.011zbMath1357.05042arXiv1407.5374OpenAlexW2962835057WikidataQ124839505 ScholiaQ124839505MaRDI QIDQ507595
Ioannis Giotis, Kostas I. Psaromiligkos, Dimitrios M. Thilikos, Lefteris M. Kirousis
Publication date: 6 February 2017
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1407.5374
Extremal problems in graph theory (05C35) Coloring of graphs and hypergraphs (05C15) Graph algorithms (graph-theoretic aspects) (05C85) Vertex degrees (05C07)
Related Items (15)
Commutativity in the Algorithmic Lovász Local Lemma ⋮ Acyclic chromatic index of triangle-free 1-planar graphs ⋮ Acyclic chromatic index of chordless graphs ⋮ Acyclic edge coloring of 1-planar graphs without 4-cycles ⋮ A new bound on the acyclic edge chromatic number ⋮ Moser-Tardos resampling algorithm, entropy compression method and the subset gas ⋮ Further result on acyclic chromatic index of planar graphs ⋮ Unnamed Item ⋮ Entropy compression versus Lovász local lemma ⋮ On acyclic edge-coloring of complete bipartite graphs ⋮ Acyclic edge coloring conjecture is true on planar graphs without intersecting triangles ⋮ Acyclic edge coloring conjecture is true on planar graphs without intersecting triangles ⋮ An Algorithmic Proof of the Lovász Local Lemma via Resampling Oracles ⋮ Acyclic edge coloring of chordal graphs with bounded degree ⋮ A Local Lemma for Focused Stochastic Algorithms
Uses Software
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- NIST digital library of mathematical functions
- Acyclic edge-coloring using entropy compression
- Acyclic edge colorings of graphs
- A constructive proof of the general lovász local lemma
- A constructive proof of the Lovász local lemma
- On the Algorithmic Lovász Local Lemma and Acyclic Edge Coloring
This page was built for publication: Acyclic edge coloring through the Lovász local lemma
