Journal articleAnnals of Combinatorics · January 1, 2026
Given a graph G, the k-coloring graph Ck(G) is constructed by selecting proper k-colorings of G as vertices, with an edge between two colorings if they differ in the color of exactly one vertex. The number of vertices in Ck(G) is the famous chromatic polyn ...
Full textOpen AccessCite
Preprint · December 10, 2025
Given a graph $G$, the Bell $k$-coloring graph $\mathcal{B}_k(G)$ has vertices given by partitions of $V(G)$ into $k$ independent sets (allowing empty parts), with two partitions adjacent if they differ only in the placement of a single vertex. We first gi ...
Link to itemCite
Preprint · December 3, 2025
Given a tree $T$, its 3-coloring graph $\mathcal{C}_3(T)$ has as vertices the proper 3-colorings of $T$, with edges joining colorings that differ at exactly one vertex. We call the diameter of $\mathcal{C}_3(T)$ the 3-coloring diameter of $T$. We introduce ...
Link to itemCite
