2021/09/27 by JD Nir, Nir, JD, Xavier Giménez +1
Computer Science · Mathematics · #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Graph Labeling and Dimension Problems #Limits and Structures in Graph Theory
paper · pdf · doi:10.48550/arxiv.2109.13347
openalex publication_date 2021/09/27 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
An n-lift of a graph G is a graph from which there is an n-to-1 covering map onto G. Amit, Linial, and Matou\v sek (2002) raised the question of whether the chromatic number of a random n-lift of K5 is concentrated on a single value. We consider this problem for G=Kd+1, and show that for fixed d≥ 3 the chromatic number of a random lift of Kd is (asymptotically almost surely) either k or k+1, where k is the smallest integer satisfying d < 2k log k. Moreover, we show that, for roughly half of the values of d, the chromatic number is concentrated on k. The argument for the upper-bound on the chromatic number uses the small subgraph conditioning method, and it can be extended to random n-lifts of G, for any fixed d-regular graph G.