Geodesic
A Note on the Thue Chromatic Number of Lexicographic Products of Graphs
Discussiones Mathematicae. Graph Theory, Tome 38 (2018) no. 3, pp. 635-643

Voir la notice de l'article provenant de la source Library of Science

A sequence is called non-repetitive if none of its subsequences forms a repetition (a sequence r1r2⋯r2n such that ri = rn+i for all 1 ≤ i ≤ n). Let G be a graph whose vertices are coloured. A colouring ϕ of the graph G is non-repetitive if the sequence of colours on every path in G is non-repetitive. The Thue chromatic number, denoted by π(G), is the minimum number of colours of a non-repetitive colouring of G. In this short note we present two general upper bounds for the Thue chromatic number for the lexicographic product G ◦ H of graphs G and H with respect to some properties of the factors. One upper bound is then used to derive the exact values for π(G ◦ H) when G is a complete multipartite graph and H an arbitrary graph.
Keywords: non-repetitive colouring, Thue chromatic number, lexicographic product of graphs 
@article{DMGT_2018_38_3_a2,
     author = {Peterin, Iztok and Schreyer, Jens and \v{S}krabul{\textquoteright}\'akov\'a, Erika Feckov\'a and Taranenko, Andrej},
     title = {A {Note} on the {Thue} {Chromatic} {Number} of {Lexicographic} {Products} of {Graphs}},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {635--643},
     publisher = {mathdoc},
     volume = {38},
     number = {3},
     year = {2018},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2018_38_3_a2/}
}
TY  - JOUR
AU  - Peterin, Iztok
AU  - Schreyer, Jens
AU  - Škrabul’áková, Erika Fecková
AU  - Taranenko, Andrej
TI  - A Note on the Thue Chromatic Number of Lexicographic Products of Graphs
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2018
SP  - 635
EP  - 643
VL  - 38
IS  - 3
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DMGT_2018_38_3_a2/
LA  - en
ID  - DMGT_2018_38_3_a2
ER  - 
%0 Journal Article
%A Peterin, Iztok
%A Schreyer, Jens
%A Škrabul’áková, Erika Fecková
%A Taranenko, Andrej
%T A Note on the Thue Chromatic Number of Lexicographic Products of Graphs
%J Discussiones Mathematicae. Graph Theory
%D 2018
%P 635-643
%V 38
%N 3
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DMGT_2018_38_3_a2/
%G en
%F DMGT_2018_38_3_a2
Peterin, Iztok; Schreyer, Jens; Škrabul’áková, Erika Fecková; Taranenko, Andrej. A Note on the Thue Chromatic Number of Lexicographic Products of Graphs. Discussiones Mathematicae. Graph Theory, Tome 38 (2018) no. 3, pp. 635-643. http://geodesic.mathdoc.fr/item/DMGT_2018_38_3_a2/