The lefthanded local lemma characterizes chordal dependency graphs

DOI10.1002/rsa.20439zbMath1255.68119arXiv1204.5922OpenAlexW2022565804WikidataQ124828530 ScholiaQ124828530MaRDI QIDQ3145842

Wesley Pegden

Publication date: 14 December 2012

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

Full work available at URL: https://arxiv.org/abs/1204.5922

zbMATH Keywords

chordal graphsdependency graphslefthanded local lemmalocal lema

Mathematics Subject Classification ID

Combinatorics on words (68R15) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Probability theory on algebraic and topological structures (60B99)

Related Items

Bears with hats and independence polynomials

Cites Work

• Lopsided Lovász Local lemma and Latin transversals
• On a problem of Spencer
• Highly nonrepetitive sequences: Winning strategies from the local lemma
• On Dependency Graphs and the Lattice Gas
• Two Erdős problems on lacunary sequences: Chromatic number and Diophantine approximation