2012/10/20 by Balázs Keszegh, Balázs Patkós, Keszegh, Balázs +3 · 1 citation
Computer Science · Mathematics · #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Graph theory and applications #Limits and Structures in Graph Theory
paper · pdf · doi:10.48550/arxiv.1210.5607
openalex publication_date 2012/10/20 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
A coloring c of the vertices of a graph G is nonrepetitive if there exists no path v1v2… v2l for which c(vi)=c(vl+i) 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 Kk,k. %Our main results are the following. We prove that for a sufficiently long path P, a nonrepetitive coloring of P[Kk] needs at least 3k+\lfloor k/2\rfloor colors. If k>2 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+\lceil k/2\rceil. Finally, we define fractional nonrepetitive colorings of graphs and consider the connections between this notion and the above results.