Properly colored paths and cycles

In an edge-colored graph, let dc(v)dc(v) be the number of colors on the edges incident to vv and let δc(G)δc(G) be the minimum dc(v)dc(v) over all vertices v∈Gv∈G. In this work, we consider sharp conditions on δc(G)δc(G) which imply the existence of properly edge-colored paths and cycles, meaning no two consecutive edges have the same color.

► We consider edge colorings of graphs with color degree conditions. ► Increasing color degree implies that properly colored cycles and paths exist. ► Large color degree implies that small properly colored cycles exist. ► Large color degree implies that vertices are connected by properly colored paths.