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.