1. bookVolume 38 (2018): Issue 3 (August 2018)
Journal Details
License
Format
Journal
eISSN
2083-5892
First Published
13 Apr 2013
Publication timeframe
4 times per year
Languages
English
access type Open Access

A Note on the Thue Chromatic Number of Lexicographic Products of Graphs

Published Online: 19 Jun 2018
Volume & Issue: Volume 38 (2018) - Issue 3 (August 2018)
Page range: 635 - 643
Received: 17 Sep 2015
Accepted: 18 Jan 2017
Journal Details
License
Format
Journal
eISSN
2083-5892
First Published
13 Apr 2013
Publication timeframe
4 times per year
Languages
English
Abstract

A sequence is called non-repetitive if none of its subsequences forms a repetition (a sequence r1r2r2n such that ri = rn+i for all 1 ≤ in). 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 GH 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 π(GH) when G is a complete multipartite graph and H an arbitrary graph.

Keywords

MSC 2010

[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.1005710.1002/rsa.10057Search in Google Scholar

[2] J. Barát and D.R. Wood, Notes on nonrepetitive graph colouring, Electron. J. Combin. 15 (2008) #R99.10.37236/823Search in Google Scholar

[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.01710.1016/j.disc.2006.06.017Search in Google Scholar

[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.06310.1016/j.endm.2007.01.063Search in Google Scholar

[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.01710.1016/j.dam.2011.07.017Search in Google Scholar

[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-310.1016/0095-8956(75)90076-3Search in Google Scholar

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

[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.2034710.1002/rsa.20347Search in Google Scholar

[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.2048810.1002/jgt.20488Search in Google Scholar

[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.Search in Google Scholar

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

Recommended articles from Trend MD

Plan your remote conference with Sciendo