论文标题
加强Meyniel定理
Strengthening a theorem of Meyniel
论文作者
论文摘要
对于整数$ k \ geq 1 $和图$ g $，让$ \ mathcal {k} _k（g）$是$ g $的顶点的图形，并将两个co $α$α$和〜$β$之间的$ g $的$ g $ $ g $ a $ a $ a $ a $ a $ a $ a $ n change thange the Change the Change中。 1978年的Meyniel定理指出，每个平面图$ g $的$ \ Mathcal {k} _5（g）$与直径$ o（5^{| v（g）|}）$连接。我们通过表明有一个正常数的$ c $，使每个平面图$ g $都有直径$ o（| v（g）|^c）$。
For an integer $k \geq 1$ and a graph $G$, let $\mathcal{K}_k(G)$ be the graph that has vertex set all proper $k$-colorings of $G$, and an edge between two vertices $α$ and~$β$ whenever the coloring~$β$ can be obtained from $α$ by a single Kempe change. A theorem of Meyniel from 1978 states that $\mathcal{K}_5(G)$ is connected with diameter $O(5^{|V(G)|})$ for every planar graph $G$. We significantly strengthen this result, by showing that there is a positive constant $c$ such that $\mathcal{K}_5(G)$ has diameter $O(|V(G)|^c)$ for every planar graph $G$.
