Geodesic
Nonrepetitively 3-colorable subdivisions of graphs with a logarithmic number of subdivisions per edge
Matthieu Rosenfeld1
1Aix-Marseille Universitée
The electronic journal of combinatorics, Tome 28 (2021) no. 4
Cet article a éte moissonné depuis la source The Electronic Journal of Combinatorics website

Voir la notice de l'article

We show that for every graph $G$ and every graph $H$ obtained by subdividing each edge of $G$ at least $\Omega(\log |V(G)|)$ times, $H$ is nonrepetitively 3-colorable. In fact, we show that $\Omega(\log \pi'(G))$ subdivisions per edge are enough, where $\pi'(G)$ is the nonrepetitive chromatic index of $G$. This answers a question of Wood and improves a similar result of Pezarski and Zmarz that stated the existence of at least one 3-colorable subdivision with a linear number of subdivision vertices per edge.
DOI : 10.37236/10370
Classification : 05C15, 68R15
Mots-clés : nonrepetitive chromatic index, nonrepetitively 3-colourable subdivision

Matthieu Rosenfeld  1

1 Aix-Marseille Universitée 
@article{10_37236_10370,
     author = {Matthieu Rosenfeld},
     title = {Nonrepetitively 3-colorable subdivisions of graphs with a logarithmic number of subdivisions per edge},
     journal = {The electronic journal of combinatorics},
     year = {2021},
     volume = {28},
     number = {4},
     doi = {10.37236/10370},
     zbl = {1478.05057},
     url = {http://geodesic.mathdoc.fr/articles/10.37236/10370/}
}
TY  - JOUR
AU  - Matthieu Rosenfeld
TI  - Nonrepetitively 3-colorable subdivisions of graphs with a logarithmic number of subdivisions per edge
JO  - The electronic journal of combinatorics
PY  - 2021
VL  - 28
IS  - 4
UR  - http://geodesic.mathdoc.fr/articles/10.37236/10370/
DO  - 10.37236/10370
ID  - 10_37236_10370
ER  - 
%0 Journal Article
%A Matthieu Rosenfeld
%T Nonrepetitively 3-colorable subdivisions of graphs with a logarithmic number of subdivisions per edge
%J The electronic journal of combinatorics
%D 2021
%V 28
%N 4
%U http://geodesic.mathdoc.fr/articles/10.37236/10370/
%R 10.37236/10370
%F 10_37236_10370
Matthieu Rosenfeld. Nonrepetitively 3-colorable subdivisions of graphs with a logarithmic number of subdivisions per edge. The electronic journal of combinatorics, Tome 28 (2021) no. 4. doi: 10.37236/10370

Cité par Sources :