A SYSTEMATIC SCAN FOR 7-COLOURINGS OF THE GRID

DOI10.1142/S012905410800639XzbMath1171.68625arXiv0704.1625OpenAlexW2127649527MaRDI QIDQ3606561

Markus Jalsenius, Kasper Selmar Pedersen

Publication date: 26 February 2009

Published in: International Journal of Foundations of Computer Science (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/0704.1625

zbMATH Keywords

graph colouringheuristic couplingsystematic scan Markov chain

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Markov chains (discrete-time Markov processes on discrete state spaces) (60J10) Coloring of graphs and hypergraphs (05C15)

Related Items (1)

Sampling colourings of the triangular lattice

Cites Work

• Absence of phase transition for antiferromagnetic Potts models via the Dobrushin uniqueness theorem
• Systematic scan for sampling colorings
• Markov Chain Algorithms for Planar Lattice Structures
• Improved Mixing Bounds for the Anti-Ferromagnetic Potts Model on Z²
• Dobrushin Conditions for Systematic Scan with Block Dynamics
• Random sampling of 3‐colorings in ℤ²
• Strong Spatial Mixing with Fewer Colors for Lattice Graphs
• Combinatorial criteria for uniqueness of Gibbs measures
• Dobrushin Conditions and Systematic Scan

This page was built for publication: A SYSTEMATIC SCAN FOR 7-COLOURINGS OF THE GRID