Nonrepetitive colorings of lexicographic product of graphs

preprint2013arXivOpen access

Abstract

A coloring cc of the vertices of a graph GG is nonrepetitive if there exists no path v1v2…v2lv_1v_2\ldots v_{2l} for which c(vi)=c(vl+i)c(v_i)=c(v_{l+i}) for all 1≤i≤l1\le i\le l. Given graphs GG and HH with ∣V(H)∣=k|V(H)|=k, the lexicographic product G[H]G[H] is the graph obtained by substituting every vertex of GG by a copy of HH, and every edge of GG by a copy of Kk,kK_{k,k}. %Our main results are the following. We prove that for a sufficiently long path PP, a nonrepetitive coloring of P[Kk]P[K_k] needs at least 3k+⌊k/2⌋3k+\lfloor k/2\rfloor colors. If k>2k>2 then we need exactly 2k+12k+1 colors to nonrepetitively color P[Ek]P[E_k], where EkE_k is the empty graph on kk vertices. If we further require that every copy of EkE_k be rainbow-colored and the path PP is sufficiently long, then the smallest number of colors needed for P[Ek]P[E_k] is at least 3k+13k+1 and at most 3k+⌈k/2⌉3k+\lceil k/2\rceil. Finally, we define fractional nonrepetitive colorings of graphs and consider the connections between this notion and the above results.

Explore this paper’s authors, topics and related work.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Reviews 0

Write a reviewWrite

No reviews yet.

Discussion 0

Add a commentWrite

No comments yet.