Geodesic
Colorful paths in vertex coloring of graphs
The electronic journal of combinatorics, Tome 18 (2011) no. 1
Cet article a éte moissonné depuis la source The Electronic Journal of Combinatorics website

Voir la notice de l'article

A colorful path in a graph $G$ is a path with $\chi(G)$ vertices whose colors are different. A $v$-colorful path is such a path, starting from $v$. Let $G\neq C_7$ be a connected graph with maximum degree $\Delta(G)$. We show that there exists a $(\Delta(G)+1)$-coloring of $G$ with a $v$-colorful path for every $v\in V(G)$. We also prove that this result is true if one replaces $(\Delta(G)+1)$ colors with $2\chi(G)$ colors. If $\chi(G)=\omega(G)$, then the result still holds for $\chi(G)$ colors. For every graph $G$, we show that there exists a $\chi(G)$-coloring of $G$ with a rainbow path of length $\lfloor\chi(G)/2\rfloor$ starting from each $v \in V(G)$.
DOI : 10.37236/504
Classification : 05C15, 05C38
Mots-clés : vertex-coloring, colorful path, rainbow path 
@article{10_37236_504,
     author = {Saieed Akbari and Vahid Liaghat and Afshin Nikzad},
     title = {Colorful paths in vertex coloring of graphs},
     journal = {The electronic journal of combinatorics},
     year = {2011},
     volume = {18},
     number = {1},
     doi = {10.37236/504},
     zbl = {1290.05070},
     url = {http://geodesic.mathdoc.fr/articles/10.37236/504/}
}
TY  - JOUR
AU  - Saieed Akbari
AU  - Vahid Liaghat
AU  - Afshin Nikzad
TI  - Colorful paths in vertex coloring of graphs
JO  - The electronic journal of combinatorics
PY  - 2011
VL  - 18
IS  - 1
UR  - http://geodesic.mathdoc.fr/articles/10.37236/504/
DO  - 10.37236/504
ID  - 10_37236_504
ER  - 
%0 Journal Article
%A Saieed Akbari
%A Vahid Liaghat
%A Afshin Nikzad
%T Colorful paths in vertex coloring of graphs
%J The electronic journal of combinatorics
%D 2011
%V 18
%N 1
%U http://geodesic.mathdoc.fr/articles/10.37236/504/
%R 10.37236/504
%F 10_37236_504
Saieed Akbari; Vahid Liaghat; Afshin Nikzad. Colorful paths in vertex coloring of graphs. The electronic journal of combinatorics, Tome 18 (2011) no. 1. doi: 10.37236/504

Cité par Sources :