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.