论文标题
重新配置$ 10 $颜色的平面图的更新
An update on reconfiguring $10$-colorings of planar graphs
论文作者
论文摘要
$ k $ g $的$ k $颜色的重新配置图$ r_k（g）$具有顶点，因为顶点套装$ g $的所有可能的$ k $ - 颜色的集合，如果恰好的一个顶点的颜色不同，则两种颜色相邻。 Bousquet and Perarnau（2016）的结果是有界变性图的结果，这意味着，如果$ g $是带有$ n $ vertices的平面图，则$ r_ {12}（g）$的直径最多为$ 6n $。我们改善了颜色的数量，表明$ r_ {10}（g）$的直径最多为$ 8n $，每个平面图$ g $带有$ n $ vertices。
The reconfiguration graph $R_k(G)$ for the $k$-colorings of a graph $G$ has as vertex set the set of all possible proper $k$-colorings of $G$ and two colorings are adjacent if they differ in the color of exactly one vertex. A result of Bousquet and Perarnau (2016) regarding graphs of bounded degeneracy implies that if $G$ is a planar graph with $n$ vertices, then $R_{12}(G)$ has diameter at most $6n$. We improve on the number of colors, showing that $R_{10}(G)$ has diameter at most $8n$ for every planar graph $G$ with $n$ vertices.
