The Complexity of Choosing an H-Coloring (Nearly) Uniformly at Random

DOI10.1137/S0097539702408363zbMath1105.68114OpenAlexW1966994937MaRDI QIDQ4651471

Steven Kelk, Leslie Ann Goldberg, Mike S. Paterson

Publication date: 21 February 2005

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/s0097539702408363

zbMATH Keywords

computational complexitygraph coloringgraph homomorphismrandom sampling

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Coloring of graphs and hypergraphs (05C15) Randomized algorithms (68W20)

Related Items (8)

Approximately Counting H-Colourings is $$\#\mathrm {BIS}$$-Hard ⋮ The Complexity of Approximately Counting Tree Homomorphisms ⋮ Counting Constraint Satisfaction Problems. ⋮ Systematic scan for sampling colorings ⋮ Unnamed Item ⋮ On systematic scan for sampling H-colorings of the path ⋮ Sharp thresholds for constraint satisfaction problems and homomorphisms ⋮ Approximately Counting $H$-Colorings is $\#\mathrm{BIS}$-Hard

This page was built for publication: The Complexity of Choosing an H-Coloring (Nearly) Uniformly at Random