On the chromatic number of powers of subdivisions of graphs
Anastos M, Boyadzhiyska S, Rathke S, Rué J. 2024. On the chromatic number of powers of subdivisions of graphs. Discrete Applied Mathematics. 360, 506–511.
Download (ext.)
Journal Article
| Epub ahead of print
| English
Scopus indexed
Author
Anastos, MichaelISTA;
Boyadzhiyska, Simona;
Rathke, Silas;
Rué, Juanjo
Corresponding author has ISTA affiliation
Department
Abstract
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.
Publishing Year
Date Published
2024-10-23
Journal Title
Discrete Applied Mathematics
Publisher
Elsevier
Acknowledgement
This work was initiated at the annual workshop of the Combinatorics and Graph Theory group of Freie Universität Berlin in Wilhelmsaue in September 2023. The authors would like to thank the institution for enabling this research. Finally, the fourth author would like to thank Tibor Szabó and the Combinatorics and Graph Theory group at Freie Universität Berlin for their hospitality during the research visit. Additionally, we thank Moharram Iradmusa for bringing the papers [5], [7] to our attention. Finally, we thank the anonymous referees for their suggestions on the manuscript, which have improved the quality of the document.
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).
Volume
360
Page
506-511
ISSN
IST-REx-ID
Cite this
Anastos M, Boyadzhiyska S, Rathke S, Rué J. On the chromatic number of powers of subdivisions of graphs. Discrete Applied Mathematics. 2024;360:506-511. doi:10.1016/j.dam.2024.10.002
Anastos, M., Boyadzhiyska, S., Rathke, S., & Rué, J. (2024). On the chromatic number of powers of subdivisions of graphs. Discrete Applied Mathematics. Elsevier. https://doi.org/10.1016/j.dam.2024.10.002
Anastos, Michael, Simona Boyadzhiyska, Silas Rathke, and Juanjo Rué. “On the Chromatic Number of Powers of Subdivisions of Graphs.” Discrete Applied Mathematics. Elsevier, 2024. https://doi.org/10.1016/j.dam.2024.10.002.
M. Anastos, S. Boyadzhiyska, S. Rathke, and J. Rué, “On the chromatic number of powers of subdivisions of graphs,” Discrete Applied Mathematics, vol. 360. Elsevier, pp. 506–511, 2024.
Anastos M, Boyadzhiyska S, Rathke S, Rué J. 2024. On the chromatic number of powers of subdivisions of graphs. Discrete Applied Mathematics. 360, 506–511.
Anastos, Michael, et al. “On the Chromatic Number of Powers of Subdivisions of Graphs.” Discrete Applied Mathematics, vol. 360, Elsevier, 2024, pp. 506–11, doi:10.1016/j.dam.2024.10.002.
All files available under the following license(s):
Copyright Statement:
This Item is protected by copyright and/or related rights. [...]
Link(s) to Main File(s)
Access Level
Open Access
Export
Marked PublicationsOpen Data ISTA Research Explorer
Sources
arXiv 2404.05542
Google Scholar