## Abstract

A sequence S is called anagram-free if it contains no segment r_{1}r_{2}…r_{k}r_{k+1}…r_{2k} such that r_{k+1}…r_{2k} is a permutation of the block r_{1}r_{2}…r_{k}. Answering a question of Erdős and Brown, Keränen constructed an infinite anagram-free sequence on four symbols. Motivated by the work of Alon, Grytczuk, Hałuszczak and Riordan [Alon, N., J. Grytczuk, M. Hałuszczak and O. Riordan, Non-repetitive colorings of graphs, Random Struct. Algor. 21 (2002), 336–346], we consider a natural generalisation of anagram-free sequences for graph colorings. A coloring of the vertices of a given graph G is called anagram-free if the sequence of colors on any path in G is anagram-free. We call the minimal number of colors needed for such a coloring the anagram-chromatic number of G. We have studied the anagram-chromatic number of several classes of graphs like trees, minor-free graphs and bounded-degree graphs. Surprisingly, we show that there are bounded-degree graphs (such as random regular graphs) in which anagrams cannot be avoided unless we basically give each vertex a separate color.

Original language | English |
---|---|

Pages (from-to) | 671-677 |

Number of pages | 7 |

Journal | Electronic Notes in Discrete Mathematics |

Volume | 61 |

DOIs | |

Publication status | Published - 1 Aug 2017 |

Externally published | Yes |

## Keywords

- anagram
- coloring
- Random regular graph