| Autor: |
Peterin, Iztok, Schreyer, Jens, Škrabuľáková, Erika, Taranenko, Andrej |
| Rok vydání: |
2014 |
| Předmět: |
|
| Druh dokumentu: |
Working Paper |
| 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: |
arXiv |
| Externí odkaz: |
|
