A Random Recolouring Method for Graphs and Hypergraphs

DOI10.1017/S0963548300000730zbMath0794.05031OpenAlexW2003464009MaRDI QIDQ4289300

Colin J. H. McDiarmid

Publication date: 28 April 1994

Published in: Combinatorics, Probability and Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1017/s0963548300000730

zbMATH Keywords

hypergraphcolouringrandomized algorithmchromatic numbersymmetric random walkrandom recolouring

Mathematics Subject Classification ID

Sums of independent random variables; random walks (60G50) Hypergraphs (05C65) Coloring of graphs and hypergraphs (05C15)

Related Items (6)

Superpolynomial lower bounds for the \((1+1)\) EA on some easy combinatorial problems ⋮ Coloring bipartite hypergraphs ⋮ Rainbow Coloring Hardness via Low Sensitivity Polymorphisms ⋮ The Quest for Strong Inapproximability Results with Perfect Completeness ⋮ Rainbow Coloring Hardness via Low Sensitivity Polymorphisms ⋮ Reachability and recurrence in a modular generalization of annihilating random walks (and Lights-Out games) to hypergraphs

Cites Work

• Unnamed Item
• A randomised 3-colouring algorithm
• Finite particle systems and infection models

This page was built for publication: A Random Recolouring Method for Graphs and Hypergraphs