Nonrepetitive colorings of lexicographic product of graphs
Balázs Keszegh, Balázs Patkós, Xuding Zhu
Abstract
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. We prove
that for a sufficiently long path P, a nonrepetitive
coloring of P[Kk] needs at least
3k+⌊k/2⌋ 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+⌈k/2⌉. Finally, we define fractional
nonrepetitive colorings of graphs and consider the connections between
this notion and the above results.
Full Text: PDF PostScript