Nonrepetitive colorings of lexicographic product of graphs

الأصل · EN

A coloring c of the vertices of a graph G is nonrepetitive if there exists no path v₁v₂ v₂ₗ for which c(vᵢ)=c(vₗ₊ᵢ) for all 1≤ i≤ l. Given graphs G and H with |V(H)|=k, the lexicographic product G[H] is the graph obtained by substituting every vertex of G by a copy of H, and every edge of G by a copy of Kₖ,ₖ. %Our main results are the following. We prove that for a sufficiently long path P, a nonrepetitive coloring of P[Kₖ] needs at least 3k+ k/2 colors. If k>2 then we need exactly 2k+1 colors to nonrepetitively color P[Eₖ], where Eₖ is the empty graph on k vertices. If we further require that every copy of Eₖ be rainbow-colored and the path P is sufficiently long, then the smallest number of colors needed for P[Eₖ] 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.