Seminar of Graph Theory - Erika Fecková Škrabuľáková (2.5.2019)
Thursday 2.5.2019 at 9:50, Lecture room M/213
Erika Fecková Škrabuľáková (TU Košice):
On nonrepetitive colourings of graphs
Abstract:
A sequence r1, r2, ... , r2n such that ri = rn+i for all 1 ≤ i ≤ n, is called a repetition. A sequence S is called nonrepetitive if no subsequence of consecutive terms of S forms a repetition.
In 1906 Norwegian mathematician Axel Thue started a systematic study of word structure. In his seminal paper he showed that there are arbitrarily long nonrepetitive sequences over three symbols. Since then Thue's non- repetitive sequences have repetitively occurred also in mathematics and various questions concerning nonrepetitive colourings of graphs have been formulated.
Alon at al. introduced a natural generalization of Thue's sequences for colouring of graphs. An edge-colouring / vertex-colouring of a graph G is nonrepetitive if the sequence of colours on any path in G is nonrepetitive. A natural question is whether there is a nite bound for the number of colours needed to colour the edges / vertices of G in such a way, that the colours of no path of G form a repetition.
There are several ways how to relax the requirements in this problem and several kinds of so called problems of Thue's type. Hence, many graph colouring parameters of Thue's type: the Thue chromatic number and index, the Thue choice number and index, the facial Thue chromatic number and index, the facial Thue choice number and index, the strong and weak total Thue chromatic number, the total Thue choice number, have been de ned. All of these are connected with colourings of graphs that omit repetitions. Here you come familiar with some of them. 1