  While investigating odd-cycle free hypergraphs, Gy\H{o}ri and Lemons
introduced a colored version of the classical theorem of Erd\H{o}s and Gallai
on $P_k$-free graphs. They proved that any graph $G$ with a proper vertex
coloring and no path of length $2k+1$ with endpoints of different colors has at
most $2kn$ edges. We show that Erd\H{o}s and Gallai's original sharp upper
bound of $kn$ holds for their problem as well. We also introduce a version of
this problem for trees and present a generalization of the Erd\H{o}s-S\'os
conjecture.
