ProbXiv
Explorersign in
Problem archiveProblem record

Statement

For a finite simple undirected graph GG, the degeneracy of GG is the least integer dd such that every non-empty subgraph of GG has a vertex of degree at most dd. For a positive integer kk, a proper kk-colouring of GG is a map γ:V(G)→{1,…,k}\gamma : V(G) \to \{1,\dots,k\} with γ(u)≠γ(v)\gamma(u) \neq \gamma(v) for every edge uv∈E(G)uv \in E(G). Two proper kk-colourings γ,γ′\gamma, \gamma' of GG are adjacent if there is exactly one vertex v∈V(G)v \in V(G) with γ(v)≠γ′(v)\gamma(v) \neq \gamma'(v); the reconfiguration graph of proper kk-colourings of GG has as its vertices all proper kk-colourings of GG, with this adjacency.

For every integer d≥1d \ge 1 there exists a constant C=C(d)C = C(d) such that for every graph GG on nn vertices with degeneracy at most dd and every two proper (d+2)(d+2)-colourings α\alpha and β\beta of GG, there is a sequence of proper (d+2)(d+2)-colourings

α=γ0,γ1,…,γℓ=β\alpha = \gamma_0, \gamma_1, \dots, \gamma_\ell = \beta

such that γi−1\gamma_{i-1} and γi\gamma_i differ in the colour of exactly one vertex for each i∈{1,…,ℓ}i \in \{1,\dots,\ell\}, and

ℓ≤Cn2.\ell \le C n^2 .

Equivalently, the reconfiguration graph of proper (d+2)(d+2)-colourings of an nn-vertex graph of degeneracy at most dd is connected and has diameter O(n2)O(n^2), where the implied constant depends only on dd.

Record

Added
Links

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 in

Solve with an agent

Open the statement in a chat, with the problem and the ground rules already written into the prompt.

This opens a third-party site. Nothing is posted back to ProbXiv and nothing you write there is recorded here — what a model gives you is an attempt, which a person still has to check.