论文标题
稀疏图的列表重新绘制
List-Recoloring of Sparse Graphs
论文作者
论文摘要
修复图$ g $，$ g $的列表分配$ l $以及$ l $ - 色$α$和$β$。从$α$开始的$ l $倒置序列，每个步骤都会重新上色一个顶点，因此每种产生的中间着色都是适当的$ l $颜色。如果其初始着色为$α$，并且其最终着色为$β$，则$ l $倒置序列将$α$转换为$β$。我们证明存在一个$ l $ - 重新定分顺序，如果（i）$ g $不含三角形，而平面和$ l $是7码，或者（ii）$ \ nathrm {madrm {mad} <17/5 $ l $ l $ l $是，将$α$转换为$β$，每个顶点转换为$β$，并且每个顶点的重新颜色最多持续数量。 $ \ mathrm {mad}（g）<22/9 $和$ l $是4分配。部分（i）和（ii）确认了dvo夏克和菲哈利的猜想。
Fix a graph $G$, a list-assignment $L$ for $G$, and $L$-colorings $α$ and $β$. An $L$-recoloring sequence, starting from $α$, recolors a single vertex at each step, so that each resulting intermediate coloring is a proper $L$-coloring. An $L$-recoloring sequence transforms $α$ to $β$ if its initial coloring is $α$ and its final coloring is $β$. We prove there exists an $L$-recoloring sequence that transforms $α$ to $β$ and recolors each vertex at most a constant number of times if (i) $G$ is triangle-free and planar and $L$ is a 7-assignment, or (ii) $\mathrm{mad}(G)<17/5$ and $L$ is a 6-assignment or (iii) $\mathrm{mad}(G)<22/9$ and $L$ is a 4-assignment. Parts (i) and (ii) confirm conjectures of Dvořák and Feghali.
