A note on the Thue chromatic number of lexicographic products of graphs
| Autor: | Iztok Peterin, Jens Schreyer, Erika Fecková Škrabul’áková, Andrej Taranenko |
|---|---|
| Jazyk: | angličtina |
| Rok vydání: | 2014 |
| Předmět: |
Mathematics::Combinatorics
Applied Mathematics lexicographic product of graphs Lexicographical order Graph Combinatorics thue chromatic number Computer Science::Discrete Mathematics non-repetitive colouring 05c15 QA1-939 FOS: Mathematics Discrete Mathematics and Combinatorics 05c76 Mathematics - Combinatorics Chromatic scale Combinatorics (math.CO) Mathematics |
| Zdroj: | Discussiones Mathematicae Graph Theory, Vol 38, Iss 3, Pp 635-643 (2018) |
| Popis: | A sequence is called non-repetitive if no of its subsequences forms a repetition (a sequence $r_1,r_2,\dots,r_{2n}$ such that $r_i=r_{n+i}$ for all $1\leq i \leq n$). Let $G$ be a graph whose vertices are coloured. A colouring $\varphi$ 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 $\pi (G)$, is the minimum number of colours of a non-repetitive colouring of $G$. In this short note we present a general upper bound for the Thue chromatic number for the lexicographic product $G\circ H$ of graphs $G$ and $H$ with respect to some properties of the factors. This upper bound is then used to derive the exact values for $\pi(G\circ H)$ when $G$ is a complete multipartite graph and $H$ is an arbitrary graph. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|