A Random Recolouring Method for Graphs and Hypergraphs
From MaRDI portal
Publication:4289300
DOI10.1017/S0963548300000730zbMath0794.05031MaRDI QIDQ4289300
Publication date: 28 April 1994
Published in: Combinatorics, Probability and Computing (Search for Journal in Brave)
hypergraph; colouring; randomized algorithm; chromatic number; symmetric random walk; random recolouring
60G50: Sums of independent random variables; random walks
05C65: Hypergraphs
05C15: Coloring of graphs and hypergraphs
Related Items
Coloring bipartite hypergraphs, Unnamed Item, Rainbow Coloring Hardness via Low Sensitivity Polymorphisms, Superpolynomial lower bounds for the \((1+1)\) EA on some easy combinatorial problems, Reachability and recurrence in a modular generalization of annihilating random walks (and Lights-Out games) to hypergraphs
Cites Work