Nonrepetitive colorings of lexicographic product of graphs
Balázs Keszegh, Balázs Patkós, Xuding Zhu · Discrete Mathematics & Theoretical Computer Science · 2014
Special issue PRIMA 2013 A coloring c of the vertices of a graph G is nonrepetitive if there exists no path v1v2\textellipsisv2l for which c(vi)=c(vl+i) for all 12 then we need exactly 2k+1 colors to nonrepetitively color P[Ek], where Ek is the empty graph on k vertices. If we further require that every copy of Ek be rainbow-colored and the path P is sufficiently long, then the smallest number of colors needed for P[Ek] is at least 3k+1 and at most 3k+⌈k/2⌉. Finally, we define fractional nonrepetitive colorings of graphs and consider the connections between this notion and the above results.