Geodesic
Nonrepetitive colorings of graphs
Discrete mathematics & theoretical computer science, DMTCS Proceedings vol. AE, European Conference on Combinatorics, Graph Theory and Applications (EuroComb '05), DMTCS Proceedings vol. AE, European Conference on Combinatorics, Graph Theory and Applications (EuroComb '05) (2005).

Voir la notice de l'article provenant de la source Episciences

A vertex coloring of a graph $G$ is $k \textit{-nonrepetitive}$ if one cannot find a periodic sequence with $k$ blocks on any simple path of $G$. The minimum number of colors needed for such coloring is denoted by $\pi _k(G)$ . This idea combines graph colorings with Thue sequences introduced at the beginning of 20th century. In particular Thue proved that if $G$ is a simple path of any length greater than $4$ then $\pi _2(G)=3$ and $\pi_3(G)=2$. We investigate $\pi_k(G)$ for other classes of graphs. Particularly interesting open problem is to decide if there is, possibly huge, $k$ such that $\pi_k(G)$ is bounded for planar graphs. 
@article{DMTCS_2005_special_250_a24,
     author = {Alon, Noga and Grytczuk, Jaroslaw},
     title = {Nonrepetitive colorings of graphs},
     journal = {Discrete mathematics & theoretical computer science},
     publisher = {mathdoc},
     volume = {DMTCS Proceedings vol. AE, European Conference on Combinatorics, Graph Theory and Applications (EuroComb '05)},
     year = {2005},
     doi = {10.46298/dmtcs.3415},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.3415/}
}
TY  - JOUR
AU  - Alon, Noga
AU  - Grytczuk, Jaroslaw
TI  - Nonrepetitive colorings of graphs
JO  - Discrete mathematics & theoretical computer science
PY  - 2005
VL  - DMTCS Proceedings vol. AE, European Conference on Combinatorics, Graph Theory and Applications (EuroComb '05)
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.3415/
DO  - 10.46298/dmtcs.3415
LA  - en
ID  - DMTCS_2005_special_250_a24
ER  - 
%0 Journal Article
%A Alon, Noga
%A Grytczuk, Jaroslaw
%T Nonrepetitive colorings of graphs
%J Discrete mathematics & theoretical computer science
%D 2005
%V DMTCS Proceedings vol. AE, European Conference on Combinatorics, Graph Theory and Applications (EuroComb '05)
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.3415/
%R 10.46298/dmtcs.3415
%G en
%F DMTCS_2005_special_250_a24
Alon, Noga; Grytczuk, Jaroslaw. Nonrepetitive colorings of graphs. Discrete mathematics & theoretical computer science, DMTCS Proceedings vol. AE, European Conference on Combinatorics, Graph Theory and Applications (EuroComb '05), DMTCS Proceedings vol. AE, European Conference on Combinatorics, Graph Theory and Applications (EuroComb '05) (2005). doi : 10.46298/dmtcs.3415. http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.3415/

Cité par Sources :