Rainbow paths and trees in properly-colored graphs
Isaac Clarence Wass · 2017
A graph $G$ is \\textit{properly $k$-colored} if the colors $\\{1,2,\\dots,k\\}$ are assigned to each vertex such that $u$ and $v$ have different colors if $uv$ is an edge and each color is assigned to some vertex. A \\textit{rainbow $k$-path}, a \\textit{rainbow $k$-star} and a \\textit{rainbow $k$-tree} is a path, star or tree, respectively, on $k$ vertices such that each vertex is a different color. We prove several results about the existence of rainbow paths, stars and trees in properly colored graphs, as well as their uses in proving various criteria about a graph's chromatic number. In particular, any graph $G$ properly colored with the minimum number of colors $\\chi(G)$ always contains every possible rainbow $\\chi(G)$-tree.