2026-04-17T02:51:47Zhttps://recercat.cat/oai/request

oai:recercat.cat:2117/4272042026-01-27T04:16:22Zcom_2072_1033col_2072_452950

On the chromatic number of powers of subdivisions of graphs Anastos, Michael Boyadzhiyska, Simona Rathke, Silas Rué Perna, Juan José Àrees temàtiques de la UPC::Matemàtiques i estadística::Matemàtica discreta::Teoria de grafs Teoria de grafs Graph theory Classificació AMS::05 Combinatorics::05C Graph theory 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) 2025-03-15 Article https://www.sciencedirect.com/science/article/pii/S0166218X24004323 info:eu-repo/grantAgreement/AEI/Plan Estatal de Investigación Científica y Técnica y de Innovación 2017-2020/PID2020-113082GB-I00/ES/COMBINATORIA: NUEVAS TENDENCIAS Y APLICACIONES/ http://creativecommons.org/licenses/by/4.0/ Open Access Attribution 4.0 International Elsevier