Projects per year
Abstract
An anagram is a word of the form WP where W is a nonempty word and P is a permutation of W. A vertex coloring of a graph is anagramfree if no subpath of the graph is an anagram. Anagramfree graph coloring was independently introduced by Kam\v cev, Luczak, \ and Sudakov [Combin. Probab. Comput., 27 (2018), pp. 623642] and ourselves [Electron. J. Combin., 25 (2018), pp. 220]. In this paper we introduce the study of anagramfree colorings of graph subdivisions. We show that every graph has an anagramfree 8colorable subdivision. The number of division vertices per edge is exponential in the number of edges. For trees, we construct anagramfree 10colorable subdivisions with fewer division vertices per edge. Conversely, we prove lower bounds, in terms of division vertices per edge, on the anagramfree chromatic number for subdivisions of the complete graph and subdivisions of complete trees of bounded degree.
Original language  English 

Pages (fromto)  23462360 
Number of pages  15 
Journal  SIAM Journal on Discrete Mathematics 
Volume  32 
Issue number  3 
DOIs  
Publication status  Published  1 Jan 2018 
Keywords
 Anagramfree coloring
 Subdivision
 Trees
 Vertex coloring
Projects
 1 Finished

Graph colouring via entropy compression
Australian Research Council (ARC)
2/01/14 → 31/12/17
Project: Research