Abstract
A coloring of the vertices of a graph is nonrepetitive if there exists no path for which for all . Given graphs and with , the lexicographic product is the graph obtained by substituting every vertex of by a copy of , and every edge of by a copy of . %Our main results are the following. We prove that for a sufficiently long path , a nonrepetitive coloring of needs at least colors. If then we need exactly colors to nonrepetitively color , where is the empty graph on vertices. If we further require that every copy of be rainbow-colored and the path is sufficiently long, then the smallest number of colors needed for is at least and at most . Finally, we define fractional nonrepetitive colorings of graphs and consider the connections between this notion and the above results.
Connections
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 review
No reviews yet.
Discussion 0
Add a comment
No comments yet.