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 \(\Delta(G)\) and \(|V(G)| \geq 2\). We prove that there exists a proper \((\chi(G) + \Delta(G) – 1)\)-coloring of \(G\) such that for every \(v \in V(G)\), there is a colorful \(v\)-path.