---
OA_place: publisher
OA_type: hybrid
_id: '18478'
abstract:
- lang: eng
  text: 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.
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.\r\nM.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
  .\r\nS.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.\r\nS.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).\r\nJ.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)."
article_processing_charge: Yes (in subscription journal)
article_type: original
arxiv: 1
author:
- first_name: Michael
  full_name: Anastos, Michael
  id: 0b2a4358-bb35-11ec-b7b9-e3279b593dbb
  last_name: Anastos
- first_name: Simona
  full_name: Boyadzhiyska, Simona
  last_name: Boyadzhiyska
- first_name: Silas
  full_name: Rathke, Silas
  last_name: Rathke
- first_name: Juanjo
  full_name: Rué, Juanjo
  last_name: Rué
citation:
  ama: 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>
  apa: 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>
  chicago: 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>.
  ieee: 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.
  ista: 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.
  mla: 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>.
  short: M. Anastos, S. Boyadzhiyska, S. Rathke, J. Rué, Discrete Applied Mathematics
    360 (2025) 506–511.
corr_author: '1'
date_created: 2024-10-27T23:01:44Z
date_published: 2025-01-15T00:00:00Z
date_updated: 2025-04-14T07:54:56Z
day: '15'
ddc:
- '510'
department:
- _id: MaKw
doi: 10.1016/j.dam.2024.10.002
ec_funded: 1
external_id:
  arxiv:
  - '2404.05542'
  isi:
  - '001343647000001'
file:
- access_level: open_access
  checksum: bd20a13e56b3ea01daf5e7aca5247c60
  content_type: application/pdf
  creator: dernst
  date_created: 2025-01-13T09:25:59Z
  date_updated: 2025-01-13T09:25:59Z
  file_id: '18836'
  file_name: 2025_DiscreteApplMath_Anastos.pdf
  file_size: 441060
  relation: main_file
  success: 1
file_date_updated: 2025-01-13T09:25:59Z
has_accepted_license: '1'
intvolume: '       360'
isi: 1
language:
- iso: eng
month: '01'
oa: 1
oa_version: Published Version
page: 506-511
project:
- _id: fc2ed2f7-9c52-11eb-aca3-c01059dda49c
  call_identifier: H2020
  grant_number: '101034413'
  name: 'IST-BRIDGE: International postdoctoral program'
publication: Discrete Applied Mathematics
publication_identifier:
  issn:
  - 0166-218X
publication_status: published
publisher: Elsevier
quality_controlled: '1'
scopus_import: '1'
status: public
title: On the chromatic number of powers of subdivisions of graphs
tmp:
  image: /images/cc_by.png
  legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode
  name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)
  short: CC BY (4.0)
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 360
year: '2025'
...