A Random Recolouring Method for Graphs and Hypergraphs

DOI10.1017/S0963548300000730MaRDI QIDQ4289300zbMATH OpenOpenAlexFDO

Authors Colin 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

chromatic numbercolouringhypergraphrandom recolouringrandomized algorithmsymmetric random walk

Mathematics Subject Classification ID

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

Recommendations

• Random hypergraph coloring algorithms and the weak chromatic number
• Algorithms for Colouring Random k-colourable Graphs
• scientific article; zbMATH DE number 1962838
• Coloring random graphs
• On the 2-colorability of random hypergraphs

Cites work

• A randomised 3-colouring algorithm
• Finite particle systems and infection models
• scientific article; zbMATH DE number 3249395 (Why is no real title available?)

Cited in

(10)

• Reachability and recurrence in a modular generalization of annihilating random walks (and Lights-Out games) to hypergraphs
• Superpolynomial lower bounds for the \((1+1)\) EA on some easy combinatorial problems
• Random hypergraph coloring algorithms and the weak chromatic number
• Hypergraph coloring and reconfigured RAM testing
• Coloring bipartite hypergraphs
• scientific article; zbMATH DE number 858004 (Why is no real title available?)
• The quest for strong inapproximability results with perfect completeness
• Rainbow coloring hardness via low sensitivity polymorphisms
• A recolouring problem on undirected graphs
• Rainbow Coloring Hardness via Low Sensitivity Polymorphisms

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4289300)