Colorability implies bounded-degree disconnectedness of graph homomorphism spaces
Colorability implies bounded-degree disconnectedness of graph homomorphism spaces
Let be a graph that is -colorable. For a finite graph , let denote the space of graph homomorphisms from to , with adjacency given by changing one vertex image at a time. Colorability-disconnectedness conjecture. There is some finite graph of maximum degree less than such that
This proposed analogue of the preceding long-range-action theorem would connect the chromatic number of with disconnection of homomorphism spaces on boards of bounded degree. The source gives no proof or status beyond presenting the assertion as something one should perhaps be able to prove.
Progress summary
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Sources & referencesView supporting material
Primary source
Graham R. Brightwell and Peter Winkler, “Hard constraints and the bethe lattice: adventures at the interface of combinatorics and statistical physics”, arXiv:math/0304468 (2003).
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.