Title:
On the chromatic number of powers of subdivisions of graphs
Author(s):
Anastos, Michael; Boyadzhiyska, Simona; Rathke, Silas; Rué, Juanjo
Year of publication:
2024
Available Date:
2024-12-05T12:02:00Z
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.
Part of Identifier:
e-ISSN (online): 1872-6771
Keywords:
graphs
subdivisions
chromatic number of powers
DDC-Classification:
510 Mathematik
Publication Type:
Wissenschaftlicher Artikel
URL of the Original Publication:
DOI of the Original Publication:
Journaltitle:
Discrete Applied Mathematics
Department/institution:
Mathematik und Informatik
Institut für Mathematik