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/

[1] N. Alon, J. Grytczuk, M. Hałuszczak and O. Riordan, Nonrepetitive colorings of graphs, Random Structures Algorithms 21 (2002) 336–346. doi:10.1002/rsa.10057

[2] J. Barát and D.R. Wood, Notes on nonrepetitive graph colouring, Electron. J. Combin. 15 (2008) #R99.

[3] B. Brešar, J. Grytczuk, S. Klavžar, S. Niwczyk and I. Peterin, Nonrepetitive colorings of trees, Discrete Math. 307 (2007) 163–172. doi:10.1016/j.disc.2006.06.017

[4] S. Czerwiński and J. Grytczuk, Nonrepetitive colorings of graphs, Electron. Notes Discrete Math. 28 (2007) 453–459. doi:10.1016/j.endm.2007.01.063

[5] F. Fiorenzi, P. Ochem, P. Ossona de Mendez and X. Zhu, Thue choosability of trees, Discrete Appl. Math. 159 (2011) 2045–2049. doi:10.1016/j.dam.2011.07.017

[6] D. Geller and S. Stahl, The chromatic number and other functions of the lexicographic product, J. Combin. Theory Ser. B 19 (1975) 87–95. doi:10.1016/0095-8956(75)90076-3

[7] J. Grytczuk, Thue type problems of graphs, points and numbers, Discrete Math. 308 (2008) 4419–4429. doi:10.1016/j.disc.2007.08.039

[8] J. Grytczuk, J. Przyby lo and X. Zhu, Nonrepetitive list colourings of paths, Random Structures Algorithms 38 (2011) 162–173. doi:10.1002/rsa.20347

[9] F. Havet, S. Jendrol’, R. Soták and E. Škrabul’áková, Facial non-repetitive edge coloring of plane graphs, J. Graph Theory 66 (2011) 38–48. doi:10.1002/jgt.20488

[10] B. Keszegh, B. Patkós and X. Zhu, Nonrepetitive colorings of lexicographic product of paths and other graphs, Discrete Math. Theor. Comput. Sci. 16 (2014) 97–110.

[11] A. Thue, Über unendliche Zeichenreihen, Norske Vid. Selsk. Skr., I Mat. Nat. Kl., Christiana 7 (1906) 1–22.