A general framework for hypergraph colouring
From MaRDI portal
Abstract: The Lov'asz Local Lemma is a powerful probabilistic technique for proving the existence of combinatorial objects. It is especially useful for colouring graphs and hypergraphs with bounded maximum degree. This paper presents a general theorem for colouring hypergraphs that in many instances matches or slightly improves upon the bounds obtained using the Lov'asz Local Lemma. Moreover, the theorem directly shows that there are exponentially many colourings. The elementary and self-contained proof is inspired by a recent result for nonrepetitive colourings by Rosenfeld [2020]. We apply our general theorem in the setting of proper hypergraph colouring, proper graph colouring, independent transversals, star colouring, nonrepetitive colouring, frugal colouring, Ramsey number lower bounds, and for -SAT.
This page was built for publication: A general framework for hypergraph colouring
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6346364)
