论文标题
5平面图的色彩重新配置，没有短奇数循环
5-Coloring Reconfiguration of Planar Graphs with No Short Odd Cycles
论文作者
论文摘要
着色重新配置图$ \ MATHCAL {C} _K（g）$作为顶点设置$ g $的所有合适的$ k $ - 颜色，而在$ \ Mathcal {c} _k（g）中，如果其相应的$ k $ -colorings在单个vertex上有所不同，则$ \ Mathcal {c} _k（g）$均相邻。 Cereceda猜想，如果$ n $ vertex Graph $ g $是$ d $ - degenerate和$ k \ geq d+2 $，则$ \ Mathcal {c} _k（g）$的直径为$ O（n^2）$。 Bousquet和Heinrich证明，如果$ g $是平面和两部分，则$ \ Mathcal {C} _5（g）$的直径为$ O（n^2）$。 （这证明了Cereceda对使用Demeneracy的每个此类图的猜想。）当$ G $是平面并且没有3个Cycles时，他们还强调了Cereceda猜想的特殊情况。作为解决此问题的部分解决方案，我们表明$ \ Mathcal {C} _5（g）的直径为$ O（n^2）$对于每个平面图$ g $，没有3个循环，没有3个循环。
The coloring reconfiguration graph $\mathcal{C}_k(G)$ has as its vertex set all the proper $k$-colorings of $G$, and two vertices in $\mathcal{C}_k(G)$ are adjacent if their corresponding $k$-colorings differ on a single vertex. Cereceda conjectured that if an $n$-vertex graph $G$ is $d$-degenerate and $k\geq d+2$, then the diameter of $\mathcal{C}_k(G)$ is $O(n^2)$. Bousquet and Heinrich proved that if $G$ is planar and bipartite, then the diameter of $\mathcal{C}_5(G)$ is $O(n^2)$. (This proves Cereceda's Conjecture for every such graph with degeneracy 3.) They also highlighted the particular case of Cereceda's Conjecture when $G$ is planar and has no 3-cycles. As a partial solution to this problem, we show that the diameter of $\mathcal{C}_5(G)$ is $O(n^2)$ for every planar graph $G$ with no 3-cycles and no 5-cycles.
