Colorful Paths in Vertex Coloring of Graphs

Abstract

Let $G$ be a graph with a vertex coloring. A colorful path is a path with $\chi (G)$ vertices, in which the vertices have different colors. A colorful path starting at vertex $v$ is a colorful $v$-path. We show that for every graph $G$ and given vertex $v$ of $G$, there exists a proper vertex coloring of $G$ with a colorful path starting at $v$. Let $G$ be a connected graph with maximum degree $\mathrm{\Delta }(G)$ and $|V(G)|\ge 2$. We prove that there exists a proper $(\chi (G)+\mathrm{\Delta }(G)–1)$-coloring of $G$ such that for every $v\in V(G)$, there is a colorful $v$-path.