Hostname: page-component-6898cfcb55-w5hgh Total loading time: 0 Render date: 2026-11-11T11:16:14.981Z Has data issue: false hasContentIssue false
  • English
  • Français

Anagram-Free Colourings of Graphs

Part of:Graph theory

Published online by Cambridge University Press:  08 August 2017

NINA KAMČEV,
TOMASZ ŁUCZAK and
BENNY SUDAKOV
NINA KAMČEV
Affiliation:
Department of Mathematics, ETH, Rämistrasse 101, 8092 Zurich, Switzerland (e-mail: nina.kamcev@math.ethz.ch, benjamin.sudakov@math.ethz.ch)
TOMASZ ŁUCZAK
Affiliation:
Faculty of Mathematics and Computer Science, Adam Mickiewicz University, Poznań, Poland (e-mail: tomasz@amu.edu.pl)
BENNY SUDAKOV
Affiliation:
Department of Mathematics, ETH, Rämistrasse 101, 8092 Zurich, Switzerland (e-mail: nina.kamcev@math.ethz.ch, benjamin.sudakov@math.ethz.ch)
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the 'Save PDF' action button.

A sequence S is called anagram-free if it contains no consecutive symbols r1r2. . .rkrk+1. . .r2k such that rk+1. . .r2k is a permutation of the block r1r2. . .rk. 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 [2], we consider a natural generalization of anagram-free sequences for graph colourings. A colouring of the vertices of a given graph G is called anagram-free if the sequence of colours on any path in G is anagram-free. We call the minimal number of colours needed for such a colouring the anagram-chromatic number of G.

In this paper we study 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 essentially give each vertex a separate colour.

MSC classification

Primary:05C15: Coloring of graphs and hypergraphs
Secondary:05C80: Random graphs

Information

Type
Paper
Information
Combinatorics, Probability and Computing , Volume 27 , Special Issue 4: Special Issue: Oberwolfach Workshop , July 2018, pp. 623 - 642
Copyright
Copyright © Cambridge University Press 2017 

References

[1] Alon, N. and Friedland, S. (2008) The maximum number of perfect matchings in graphs with a given degree sequence. Electron. J. Combin. 15 (1) note 13.CrossRefGoogle Scholar
[2] Alon, N., Grytczuk, J., Hałuszczak, M. and Riordan, O. (2002) Non-repetitive colorings of graphs. Random Struct. Alg. 21 336–346.CrossRefGoogle Scholar
[3] Alon, N., Grytczuk, J., Lasoń, M. and Michałek, M. (2009) Splitting necklaces and measurable colorings of the real line. Proc. Amer. Math. Soc. 137 1593–1599.CrossRefGoogle Scholar
[4] Alon, N., Seymour, P. and Thomas, R. (1990) A separator theorem for graphs with an excluded minor and its applications. In STOC '90: Proc. 22nd Annual ACM Symposium on Theory of Computing, ACM, pp. 293–299.CrossRefGoogle Scholar
[5] Bean, D. R., Ehrenfeucht, A. and McNulty, G. F. (1979) Avoidable patterns in strings of symbols. Pacific J. Math. 85 261–294.CrossRefGoogle Scholar
[6] Brown, T. C. (1971) Is there a sequence on four symbols in which no two adjacent segments are permutations of one another? Amer. Math. Monthly 78 886–888.CrossRefGoogle Scholar
[7] Cheilaris, P., Keszegh, B. and Pálvölgyi, D. (2013) Unique-maximum and conflict-free coloring for hypergraphs and tree graphs. SIAM J. Discrete Math 27 1775–1787.CrossRefGoogle Scholar
[8] Chen, C. C. and Quimpo, N. (1981) On strongly Hamiltonian abelian group graphs. In Combinatorial Mathematics VIII (McAvaney, K. L., ed.), Vol. 884 of Lecture Notes in Mathematics, Springer, pp. 23–34.CrossRefGoogle Scholar
[9] Dekking, F. M. (1979) Strongly non-repetitive sequences and progression free sets. J. Combin. Theory Ser. A 27 181–185.CrossRefGoogle Scholar
[10] Erdős, P. (1961) Some unsolved problems. Magyar Tud. Akad. Mat. Kutato. Int. Kozl. 6 221–254.Google Scholar
[11] Evdokimov, A. A. (1968) Strongly asymmetric sequences generated by finite number of symbols. Dokl. Akad. Nauk. SSSR 179 1268–1271. Soviet Math. Dokl. 9 536–539.Google Scholar
[12] Frieze, A. M. and Łuczak, T. (1992) On the independence and chromatic numbers of random regular graphs. J. Combin. Theory Ser. B 54 123–132.CrossRefGoogle Scholar
[13] Grytczuk, J. (2007) Nonrepetitive colorings of graphs: A survey. Int. J. Math. Math. Sci. 2007 74639.CrossRefGoogle Scholar
[14] Grytczuk, J. (2008) Thue type problems for graphs, points, and numbers. Discrete Math. 308 4419–4429.CrossRefGoogle Scholar
[15] Janson, S., Łuczak, T. and Ruciński, A. (2000) Random Graphs, Wiley-Interscience Series in Discrete Mathematics and Optimization, Wiley.CrossRefGoogle Scholar
[16] Keränen, V. (1992) Abelian squares are avoidable on 4 letters. In ICALP 1992: International Colloquium on Automata, Languages, and Programming, Vol. 623 of Lecture Notes in Computer science, Springer, pp. 41–52.Google Scholar
[17] Krivelevich, M., Lubetzky, E. and Sudakov, B. (2010) Hamiltonicity thresholds in Achlioptas processes. Random Struct. Alg. 37 1–24.CrossRefGoogle Scholar
[18] Novikov, P. S. and Adjan, S. I. (1968) On infinite periodic groups I, II, III. Math. USSR Izv. 32 212–244, 251–524, 709–731.Google Scholar
[19] Pleasants, P. A. B. (1970) Non-repetitive sequences. Proc. Cambridge Philos. Soc. 68 267–274.CrossRefGoogle Scholar
[20] Thue, A. (1906) Über unendliche Zeichenreichen. Norske Videnskabers Selskabs Skrifter, I Mathematisch-Naturwissenschaftliche Klasse, Christiania 7 1–22.Google Scholar
[21] Wilson, T. E. and Wood, D. R. (2016) Abelian square-free graph colouring. arXiv1607.01117Google Scholar