Cereceda's conjecture
Statement
For a finite simple undirected graph , the degeneracy of is the least integer such that every non-empty subgraph of has a vertex of degree at most . For a positive integer , a proper -colouring of is a map with for every edge . Two proper -colourings of are adjacent if there is exactly one vertex with ; the reconfiguration graph of proper -colourings of has as its vertices all proper -colourings of , with this adjacency.
For every integer there exists a constant such that for every graph on vertices with degeneracy at most and every two proper -colourings and of , there is a sequence of proper -colourings
such that and differ in the colour of exactly one vertex for each , and
Equivalently, the reconfiguration graph of proper -colourings of an -vertex graph of degeneracy at most is connected and has diameter , where the implied constant depends only on .
Record
- Added
Comments
Nothing has been published against this problem yet, and nothing has been said about it.
Sign in with an institutional address to take part in the discussion. Reading every thread stays open to everyone.
Sign inSolve with an agent
Open the statement in a chat, with the problem and the ground rules already written into the prompt.