Extremal diameters of 3-coloring graphs of trees
Shamil Asgarli, Sara Krehbiel, Simon MacLean, Gjergji Zaimi · 2025
Read Extremal diameters of 3-coloring graphs of trees by Shamil Asgarli, Sara Krehbiel, Simon MacLean, Gjergji Zaimi (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2512-03789.txt.
Description
Colour the vertices of a tree with three colours so neighbours always differ, then ask how many single-vertex changes separate the two most distant colourings. Shamil Asgarli, Sara Krehbiel, Simon MacLean, and Gjergji Zaimi study that distance in a 2025 combinatorics preprint. The colourings themselves become vertices of a new graph, with edges joining colourings that differ at exactly one vertex.
The diameter of that colouring graph measures the worst-case number of steps between two valid colourings. To compute it, the authors introduce balanced labellings of the tree and prove the diameter equals the largest L1 norm among them. That equivalence turns a hard graph problem into something tractable. With it, they find the maximum and minimum possible diameters across all trees on a given number of vertices. They also characterise exactly which trees achieve those extremes.
Catalog record
| CREATOR | Shamil Asgarli, Sara Krehbiel, Simon MacLean, Gjergji Zaimi |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 47 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2512-03789