Coloring graphs as complete graph invariants

Abstract

We investigate the extent to which the $k$-coloring graph ${\mathcal{C}}_k(G)$ uniquely determines the base graph $G$ and the number of colors $k$. The vertices of ${\mathcal{C}}_k(G)$ are the proper $k$-colorings of $G$, and edges connect colorings that differ on exactly one vertex. There are nonisomorphic graphs $G_1$ and $G_2$ with isomorphic coloring graphs, so ${\mathcal{C}}_k(G)$ is not a complete invariant in general. However, for color palettes with surplus colors (when the number of colors $k$ is greater than the chromatic number), we prove that the coloring graph is a complete invariant. Specifically, provided that $k_1>\ddot{I}‡(G_1)$, we show that ${\mathcal{C}}_{k_1}(G_1)\cong {\mathcal{C}}_{k_2}(G_2)$ implies $G_1\cong G_2$ and $k_1=k_2$. Thus, there is a natural bijection between pairs $(G,k)$ with $k>\ddot{I}‡(G)$ and their coloring graphs ${\mathcal{C}}_k(G)$. Furthermore, no coloring graph of the form ${\mathcal{C}}_{\ddot{I}‡(G)}(G)$ is isomorphic to a coloring graph with surplus colors. Our constructive proof provides a method to decide whether a coloring graph is generated with surplus colors, although the resulting algorithms are inefficient.

30 pages; final version, accepted for publication in Discrete Mathematics