2025/12/03 by Asgarli, Shamil, Krehbiel, Sara, MacLean, Simon +1
#05C12 #05C35 #Combinatorics (math.CO) #FOS: Mathematics #Primary 05C15 #Secondary 05C05
paper · doi:10.48550/arxiv.2512.03789
Given a tree T, its 3-coloring graph C3(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 C3(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 L1-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.