On the chromatic number of powers of subdivisions of graphs
| Autor: | Anastos, Michael, Boyadzhiyska, Simona, Rathke, Silas, Rué, Juanjo |
|---|---|
| Rok vydání: | 2024 |
| Předmět: | |
| Druh dokumentu: | Working Paper |
| Popis: | For a given graph $G=(V,E)$, we define its \emph{$n$th subdivision} as the graph obtained from $G$ by replacing every edge by a path of length $n$. We also define the \emph{$m$th 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. Comment: 10 pages |
| Databáze: | arXiv |
| Externí odkaz: |
|