标题： 列表着色的重新配置 显示英文标题

标题： Reconfiguration of List Colourings

摘要： 给定图$G$的一个适当的（列表）着色，一次重新着色步骤会改变单个顶点的颜色为其邻域当前未使用的另一种允许颜色，从而保持适当的着色。 假设每个顶点$v$都有自己的私有允许颜色列表$L(v)$满足$|L(v)|\ge \mbox{deg}(v)+1$。 我们证明了如果$G$是连通的且其最大度$\Delta$至少为$3$，那么对于任意两种可以重新着色的正常$L$着色，可以通过一系列$O(|V(G)|^2)$次重新着色步骤将其中一个转化为另一个。 我们还表明，将单个顶点$w$的列表大小减少到$\mbox{deg}(w)$可能会导致适当$L$着色的空间被“打碎”。 我们的结果可以被解释为展示了图的适当$L$着色的 Glauber 动力学中的一个尖锐相变。 这构成了 Feghali、Johnson 和 Paulusma 结果的一个“局部”加强和推广，他们考虑了所有列表都与$\{1,\ldots,\Delta+1\}$相同的情况。 显示英文摘要

摘要： Given a proper (list) colouring of a graph $G$, a recolouring step changes the colour at a single vertex to another colour (in its list) that is currently unused on its neighbours, hence maintaining a proper colouring. Suppose that each vertex $v$ has its own private list $L(v)$ of allowed colours such that $|L(v)|\ge \mbox{deg}(v)+1$. We prove that if $G$ is connected and its maximum degree $\Delta$ is at least $3$, then for any two proper $L$-colourings in which at least one vertex can be recoloured, one can be transformed to the other by a sequence of $O(|V(G)|^2)$ recolouring steps. We also show that reducing the list-size of a single vertex $w$ to $\mbox{deg}(w)$ can lead to situations where the space of proper $L$-colourings is `shattered'. Our results can be interpreted as showing a sharp phase transition in the Glauber dynamics of proper $L$-colourings of graphs. This constitutes a `local' strengthening and generalisation of a result of Feghali, Johnson, and Paulusma, which considered the situation where the lists are all identical to $\{1,\ldots,\Delta+1\}$.