article published yes Michael Anastos author 0b2a4358-bb35-11ec-b7b9-e3279b593dbb Simona Boyadzhiyska author Silas Rathke author Juanjo Rué author MaKw department IST-BRIDGE: International postdoctoral program project For a given graph G=(V,E), we define its \emph{nth subdivision} as the graph obtained from G by replacing every edge by a path of length n. We also define the \emph{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. https://research-explorer.ista.ac.at/download/18478/18836/2025_DiscreteApplMath_Anastos.pdf application/pdfno https://creativecommons.org/licenses/by/4.0/ Elsevier2025 eng 0166-218X 2404.05542 00134364700000110.1016/j.dam.2024.10.002 360506-511 M. Anastos, S. Boyadzhiyska, S. Rathke, and J. Rué, “On the chromatic number of powers of subdivisions of graphs,” <i>Discrete Applied Mathematics</i>, vol. 360. Elsevier, pp. 506–511, 2025. Anastos, Michael, et al. “On the Chromatic Number of Powers of Subdivisions of Graphs.” <i>Discrete Applied Mathematics</i>, vol. 360, Elsevier, 2025, pp. 506–11, doi:<a href="https://doi.org/10.1016/j.dam.2024.10.002">10.1016/j.dam.2024.10.002</a>. Anastos, M., Boyadzhiyska, S., Rathke, S., &#38; Rué, J. (2025). On the chromatic number of powers of subdivisions of graphs. <i>Discrete Applied Mathematics</i>. Elsevier. <a href="https://doi.org/10.1016/j.dam.2024.10.002">https://doi.org/10.1016/j.dam.2024.10.002</a> Anastos M, Boyadzhiyska S, Rathke S, Rué J. On the chromatic number of powers of subdivisions of graphs. <i>Discrete Applied Mathematics</i>. 2025;360:506-511. doi:<a href="https://doi.org/10.1016/j.dam.2024.10.002">10.1016/j.dam.2024.10.002</a> M. Anastos, S. Boyadzhiyska, S. Rathke, J. Rué, Discrete Applied Mathematics 360 (2025) 506–511. Anastos M, Boyadzhiyska S, Rathke S, Rué J. 2025. On the chromatic number of powers of subdivisions of graphs. Discrete Applied Mathematics. 360, 506–511. Anastos, Michael, Simona Boyadzhiyska, Silas Rathke, and Juanjo Rué. “On the Chromatic Number of Powers of Subdivisions of Graphs.” <i>Discrete Applied Mathematics</i>. Elsevier, 2025. <a href="https://doi.org/10.1016/j.dam.2024.10.002">https://doi.org/10.1016/j.dam.2024.10.002</a>. 184782024-10-27T23:01:44Z2025-04-14T07:54:56Z