Skip to Main content Skip to Navigation
Journal articles

Nonrepetitive colorings of lexicographic product of graphs

Abstract : 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 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.
Document type :
Journal articles
Complete list of metadata

Cited literature [9 references]  Display  Hide  Download
Contributor : Coordination Episciences Iam Connect in order to contact the contributor
Submitted on : Thursday, August 20, 2015 - 5:13:58 PM
Last modification on : Tuesday, August 18, 2020 - 4:46:07 PM
Long-term archiving on: : Wednesday, April 26, 2017 - 10:08:57 AM


Publisher files allowed on an open archive




Balázs Keszegh, Balázs Patkós, Xuding Zhu. Nonrepetitive colorings of lexicographic product of graphs. Discrete Mathematics and Theoretical Computer Science, DMTCS, 2014, Vol. 16 no. 2 (2), pp.97--110. ⟨10.46298/dmtcs.2077⟩. ⟨hal-01185617⟩



Record views


Files downloads