On the chromatic number of powers of subdivisions of graphs

Abstract

For a given graph G = (V, E), we define its nth subdivision as the graph obtained from G by replacing every edge by a path of length n. We also define the mth power of G as the graph on vertex set V where we connect every pair of vertices at distance at most m in G. In this paper, we study the chromatic number of powers of subdivisions of graphs and resolve the case m = n asymptotically. In particular, our result confirms a conjecture of Mozafari-Nia and Iradmusa in the case m = n = 3 in a strong sense.

M.A.: This project has received funding from the European Union’s Horizon 2020 research and innovation programme under the Marie Skłodowska-Curie grant agreement No 101034413 . S.B.: The research leading to these results was supported by EPSRC, UK, grant no. EP/V048287/1. There are no additional data beyond that contained within the main manuscript. S.R.: Funded by the Deutsche Forschungsgemeinschaft (DFG, German Research Foundation) under Germany’s Excellence Strategy – The Berlin Mathematics Research Center MATH+ (EXC-2046/1, project ID: 390685689). J.R. acknowledges the support of the Grant PID2020-113082GB-I00 funded by MICIU/AEI/10.13039/501100011033, Spain, and the Severo Ochoa and María de Maeztu Program for Centers and Units of Excellence in R&D, Spain (CEX2020-001084-M).

Peer Reviewed

Postprint (author's final draft)