Balázs Keszegh ; Balázs Patkós ; Xuding Zhu - Nonrepetitive colorings of lexicographic product of graphs

dmtcs:2077 - Discrete Mathematics & Theoretical Computer Science, October 30, 2014, Vol. 16 no. 2 -
Nonrepetitive colorings of lexicographic product of graphsArticle

Authors: Balázs Keszegh 1; Balázs Patkós 2; Xuding Zhu 3

  • 1 Alfréd Rényi Institute of Mathematics
  • 2 Geometric and Algebraic Combinatorics Research Group
  • 3 Department of Mathematics [Jinhua]

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+&#x230A;k/2&#x230B; 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+&#x2308;k/2&#x2309;. Finally, we define fractional nonrepetitive colorings of graphs and consider the connections between this notion and the above results.

Volume: Vol. 16 no. 2
Section: PRIMA 2013
Published on: October 30, 2014
Submitted on: November 1, 2013
Keywords: Discrete Mathematics,[INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM]

Consultation statistics

This page has been seen 375 times.
This article's PDF has been downloaded 511 times.