dc.contributor.author
Anastos, M.
dc.contributor.author
Boyadzhiyska, S.
dc.contributor.author
Rathke, S.
dc.contributor.author
Rué, J.
dc.date.accessioned
2024-10-29T08:33:40Z
dc.date.accessioned
2024-12-09T12:34:55Z
dc.date.available
2024-10-29T08:33:40Z
dc.date.available
2024-12-09T12:34:55Z
dc.date.issued
2025-01-15
dc.identifier.uri
http://hdl.handle.net/2072/537900
dc.description.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.
eng
dc.description.sponsorship
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).
dc.relation.ispartof
Discrete Applied Mathematics
dc.rights
L'accés als continguts d'aquest document queda condicionat a l'acceptació de les condicions d'ús establertes per la següent llicència Creative Commons: https://creativecommons.org/licenses/by/4.0/
dc.source
RECERCAT (Dipòsit de la Recerca de Catalunya)
dc.subject.other
Combinatronics
dc.title
On the chromatic number of powers of subdivisions of graphs
dc.type
info:eu-repo/semantics/article
dc.type
info:eu-repo/semantics/publishedVersion
dc.identifier.doi
10.1016/j.dam.2024.10.002
dc.rights.accessLevel
info:eu-repo/semantics/openAccess
