2026-04-18T02:21:32Zhttps://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é Universitat Politècnica de Catalunya. Departament de Matemàtiques Universitat Politècnica de Catalunya. GAPCOMB - Geometric, Algebraic and Probabilistic Combinatorics À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 Anastos, M. [et al.]. On the chromatic number of powers of subdivisions of graphs. "Discrete applied mathematics", 15 Març 2025, vol. 360, p. 506-511. 0166-218X https://arxiv.org/abs/2404.05542 https://hdl.handle.net/2117/427204 10.1016/j.dam.2024.10.002 eng 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 6 p. application/pdf Elsevier