کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
6424062 | 1632767 | 2016 | 5 صفحه PDF | دانلود رایگان |
A sequence S is nonrepetitive if no two adjacent segments of S are identical. A famous result of Thue from 1906 asserts that there are arbitrarily long nonrepetitive sequences over 3 symbols. We study the following geometric variant of this problem. Given a set P of points in the plane and a set L of lines, what is the least number of colors needed to color P so that every line in L is nonrepetitive? If P consists of all intersection points of a prescribed set of lines L, then we prove that there is such coloring using at most 405 colors. The proof is based on a theorem of Thue and on a result of Alon and Marshall concerning homomorphisms of edge colored planar graphs. We also consider nonrepetitive colorings involving other geometric structures. For instance, a nonrepetitive analog of the famous Hadwiger-Nelson problem is formulated as follows: what is the least number of colors needed to color the plane so that every path of the unit distance graph whose vertices are colinear is nonrepetitive? Using a theorem of Thue we prove that this number is at most 36.
Journal: European Journal of Combinatorics - Volume 51, January 2016, Pages 275-279