Connectedness and Hamiltonicity of graphs on vertex colorings

Abstract

Given a graph $H$, let $G_k^j(H)$ be the graph whose vertices are the proper $k$-colorings of $H$, with edges joining two colorings if $H$ contains a connected subgraph on at most $j$ vertices that includes all vertices where the colorings differ. Properties of $G_k^1(H)$ have been investigated before, including connectedness and Hamiltonicity. We introduce and study the parameters $g_k(H)$ and $h_k(H)$, which denote the minimum $j$ such that $G_k^j(H)$ is connected or Hamiltonian, respectively.

23 pages, 6 figures