Nonrepetitive colorings of lexicographic product of paths and other graphs

Keszegh, Balázs and Patkós, Balázs and Zhu, Xuding (2014) Nonrepetitive colorings of lexicographic product of paths and other graphs. Discrete Mathematics and Theoretical Computer Science (DMTCS), 16 (2). pp. 97-110. ISSN 1462-7264, ESSN: 1365-8050

Preview

Text 2014-08-08b.pdf Download (289kB) | Preview

Abstract

A coloring $c$ of the vertices of a graph $G$ is nonrepetitive if there exists no path $v_1v_2\ldots v_{2l}$ for which $c(v_i)=c(v_{l+i})$ for all $1\le i\le 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 $K_{k,k}$. We prove that for a sufficiently long path $P$, a nonrepetitive coloring of $P[K_k]$ needs at least $3k+\lfloor k/2\rfloor$ colors. If $k>2$ then we need exactly $2k+1$ colors to nonrepetitively color $P[E_k]$, where $E_k$ is the empty graph on $k$ vertices. If we further require that every copy of $E_k$ be rainbow-colored and the path $P$ is sufficiently long, then the smallest number of colors needed for $P[E_k]$ 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.

Actions (login required)

Edit Item