2021/12/31 by Melissa M. Fuentes, Fuentes, Melissa M
Mathematics · #Analytic Number Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Graph theory and applications #Limits and Structures in Graph Theory
paper · pdf · doi:10.48550/arxiv.2201.00036
openalex publication_date 2021/12/31 · openalex created_date 2022/05/05 · openalex updated_date 2026/07/28
We consider a problem proposed by Linial and Wilf to determine the structure of graphs that allows the maximum number of q-colorings among graphs with n vertices and m edges. Let Tr(n) denote the Turán graph - the complete r-partite graph on n vertices with partition sizes as equal as possible. We prove that for all odd integers q≥ 5 and sufficiently large n, the Turán graph T2(n) has at least as many q-colorings as any other graph G with the same number of vertices and edges as T2(n), with equality holding if and only if G=T2(n). Our proof builds on methods by Norine and by Loh, Pikhurko, and Sudakov, which reduces the problem to a quadratic program.