- Tytuł:
- A Note on the Thue Chromatic Number of Lexicographic Products of Graphs
- Autorzy:
-
Peterin, Iztok
Schreyer, Jens
Škrabul’áková, Erika Fecková
Taranenko, Andrej - Powiązania:
- https://bibliotekanauki.pl/articles/31342285.pdf
- Data publikacji:
- 2018-08-01
- Wydawca:
- Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
- Tematy:
-
non-repetitive colouring
Thue chromatic number
lexicographic product of graphs - Opis:
- 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.
- Źródło:
-
Discussiones Mathematicae Graph Theory; 2018, 38, 3; 635-643
2083-5892 - Pojawia się w:
- Discussiones Mathematicae Graph Theory
- Dostawca treści:
- Biblioteka Nauki
Artykuł