| Register
\(\newcommand{\Cat}{{\rm Cat}} \) \(\newcommand{\A}{\mathcal A} \) \(\newcommand{\freestar}{ \framebox[7pt]{$\star$} }\)

9. Coloring distance on planar graphs

    1. Coloring distance on planar graphs

          Fix a graph $G$ and an integer $k$, the distance between two proper $k$-colorings $c_1$ and $c_2$ (sharing the same color class $[k]$) is the minimum number of steps to transform $c_1$ to $c_2$, where each step one is allowed to change the color of one vertex (within $[k]$) while maintaining the properness of the coloring.

      Add remark

      Problem 9.1.

      [Dan Cranston] Fix a planar graph $G$ and $k=8$, is it true that the distance between any two proper $k$-colorings of $G$ is at most $O(n)$?
          Note: This statement is true for $k=10$.

      Reference: V. Bartier, N. Bousquet, C. Feghali, M. Heinrich, B. Moore, T. Pierron. Recolouring planar graphs of girth at least five. SIAM Journal on Discrete Mathematics 37(1) (2023): 10.1137.

          Cite this as: AimPL: Albertson conjecture and related problems, available at http://aimpl.org/albertson.