2025/04/29 by Shamil Asgarli, Asgarli, Shamil, Sara Krehbiel +4 · 2 citations
Computer Science · Mathematics · #05C85 #Combinatorics (math.CO) #FOS: Mathematics #Primary: 05C15 #Secondary: 05C60
paper · doi:10.48550/arxiv.2504.20978
We investigate the extent to which the k-coloring graph Ck(G) uniquely determines the base graph G and the number of colors k. The vertices of Ck(G) are the proper k-colorings of G, and edges connect colorings that differ on exactly one vertex. There are nonisomorphic graphs G1 and G2 with isomorphic coloring graphs, so Ck(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 k1 > χ(G1), we show that Ck1(G1)≅ Ck2(G2) implies G1≅ G2 and k1=k2. Thus, there is a natural bijection between pairs (G, k) with k > χ(G) and their coloring graphs Ck(G). Furthermore, no coloring graph of the form Cχ(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.