Colorability implies bounded-degree disconnectedness of graph homomorphism spaces

From papers

Let HH be a graph that is kk-colorable. For a finite graph GG, let Hom(G,H){\rm Hom}(G,H) denote the space of graph homomorphisms from GG to HH, with adjacency given by changing one vertex image at a time. Colorability-disconnectedness conjecture. There is some finite graph GG of maximum degree less than kk such that

Hom(G,H) is disconnected.{\rm Hom}(G,H)\text{ is disconnected}.

This proposed analogue of the preceding long-range-action theorem would connect the chromatic number of HH 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

No solutions have been posted yet.