Colorful paths in vertex coloring of graphs (Q625379)

Summary: 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)\).