论文标题
平面图重新上色的Thomassen型方法
A Thomassen-type method for planar graph recoloring
论文作者
论文摘要
$ k $ g $的$ k $颜色的重新配置图$ r_k（g）$具有$ g $ $ g $的所有可能的$ k $ - 颜色，如果它们的颜色完全不同，则两种颜色是相邻的。我们使用灵感来自Thomassen启发的列表着色技术，以证明对于带有$ n $ vertices的平面图$ g $，$ r_ {10}（g）$的直径最多为$ 8n $，并且如果$ g $是三角形的，则是$ r_7（g）$，最多为7n $。
The reconfiguration graph $R_k(G)$ for the $k$-colorings of a graph $G$ has as vertices all possible $k$-colorings of $G$ and two colorings are adjacent if they differ in the color of exactly one vertex. We use a list coloring technique inspired by results of Thomassen to prove that for a planar graph $G$ with $n$ vertices, $R_{10}(G)$ has diameter at most $8n$, and if $G$ is triangle-free, then $R_7(G)$ has diameter at most $7n$.
