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

10. Coloring distance and matching number

    1. Coloring distance and matching number

          The definition of coloring distance is described in the previous question. Let $\Delta(G)$ denote the maximum degree and $\mu(G)$ denote the matching number.

      Add remark

      Problem 10.1.

      [Dan Cranston] For a fixed graph $G$ with $n$ vertices and $k = \Delta(G) + 2$, is it true that the distance between any two proper $k$-colorings of $G$ is at most $n + \mu(G)$?
          Note: The statement is known to be true for $n + 2\mu(G)$.

      Reference: S. Cambie, W.C. van Batenburg, D.W. Cranston. Optimally Reconfiguring List and Correspondence Colourings. European Journal of Combinatorics 115 (2024): 103798.

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