Extremal diameters of 3-coloring graphs of trees

Abstract

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 the notion of balanced labelings of $T$ and show that the 3-coloring diameter equals the maximum $L_1$-norm of a balanced labeling. Using this equivalence, we determine the maximum and minimum values of the 3-coloring diameter over all trees on $n$ vertices and characterize the extremal trees.

17 pages