Nonrepetitive colorings of line arrangements

Jarosław Grytczuk , Karol Kosiński , Michał Zmarz


A sequence is nonrepetitive if no two adjacent segments of 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 of points in the plane and a set of lines, what is the least number of colors needed to color so that every line in is nonrepetitive? If consists of all intersection points of a prescribed set of lines , 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 .
Author Jarosław Grytczuk (FMIS / DAC) - [Wydział Matematyki i Informatyki, Uniwersytet Jagielloński w Krakowie]
Jarosław Grytczuk,,
- Department of Algebra and Combinatorics
- Wydział Matematyki i Informatyki, Uniwersytet Jagielloński w Krakowie
, Karol Kosiński - [Uniwersytet Jagielloński w Krakowie (UJ)]
Karol Kosiński,,
- Uniwersytet Jagielloński w Krakowie
, Michał Zmarz - [Uniwersytet Jagiellonski w Krakowie]
Michał Zmarz,,
Journal seriesEuropean Journal of Combinatorics, ISSN 0195-6698
Issue year2016
Publication size in sheets0.5
ASJC Classification2607 Discrete Mathematics and Combinatorics
Languageen angielski
Score (nominal)30
Score sourcejournalList
ScoreMinisterial score = 25.0, 09-01-2020, ArticleFromJournal
Ministerial score (2013-2016) = 30.0, 09-01-2020, ArticleFromJournal
Publication indicators Scopus Citations = 4; WoS Citations = 3; Scopus SNIP (Source Normalised Impact per Paper): 2016 = 1.167; WoS Impact Factor: 2016 = 0.786 (2) - 2016=0.828 (5)
Citation count*
Share Share

Get link to the record

* presented citation count is obtained through Internet information analysis and it is close to the number calculated by the Publish or Perish system.
Are you sure?