On the chromatic number of powers of subdivisions of graphs
Fuente:
arXiv
Guardado en:
| Autores principales: | , , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2024
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866914982550044672 |
|---|---|
| author | Anastos, Michael Boyadzhiyska, Simona Rathke, Silas Rué, Juanjo |
| author_facet | Anastos, Michael Boyadzhiyska, Simona Rathke, Silas Rué, Juanjo |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2404_05542 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | On the chromatic number of powers of subdivisions of graphs Anastos, Michael Boyadzhiyska, Simona Rathke, Silas Rué, Juanjo Combinatorics 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. |
| title | On the chromatic number of powers of subdivisions of graphs |
| topic | Combinatorics |
| url | https://arxiv.org/abs/2404.05542 |