Randomly coloring simple hypergraphs
From MaRDI portal
Publication:1944148
DOI10.1016/j.ipl.2011.06.001zbMath1260.05058OpenAlexW2115314646WikidataQ57401453 ScholiaQ57401453MaRDI QIDQ1944148
Publication date: 4 April 2013
Published in: Information Processing Letters (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.ipl.2011.06.001
Analysis of algorithms (68W40) Hypergraphs (05C65) Coloring of graphs and hypergraphs (05C15) Graph algorithms (graph-theoretic aspects) (05C85)
Related Items
Randomly coloring simple hypergraphs with fewer colors, List coloring triangle-free hypergraphs, Asymptotic enumeration of sparse uniform linear hypergraphs with given degrees, Defective coloring of hypergraphs, Counting Hypergraph Colorings in the Local Lemma Regime
Cites Work
- Unnamed Item
- Unnamed Item
- Absence of phase transition for antiferromagnetic Potts models via the Dobrushin uniqueness theorem
- Improved bounds for sampling colorings
- A polynomial-time approximation algorithm for the permanent of a matrix with nonnegative entries
- A random polynomial-time algorithm for approximating the volume of convex bodies
- Random walks and anO*(n5) volume algorithm for convex bodies
- A very simple algorithm for estimating the number of k‐colorings of a low‐degree graph