Anagram-Free Colorings of Graph Subdivisions

DOI10.1137/17M1145574MaRDI QIDQ4684464zbMATH OpenOpenAlexWikidataFDO

Authors Tim E. Wilson, David R. Wood

Publication date 1 October 2018

Published in SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1708.09571

zbMATH Keywords

anagram-free coloringsubdivisiontreesvertex coloring

Mathematics Subject Classification ID

Trees (05C05) Coloring of graphs and hypergraphs (05C15)

Abstract: An anagram is a word of the form $WP$ where $W$ is a non-empty word and $P$ is a permutation of $W$. A vertex colouring of a graph is anagram-free if no subpath of the graph is an anagram. Anagram-free graph colouring was independently introduced by Kamv{c}ev, {L}uczak and Sudakov and ourselves. In this paper we introduce the study of anagram-free colourings of graph subdivisions. We show that every graph has an anagram-free $8$-colourable subdivision. The number of division vertices per edge is exponential in the number of edges. For trees, we construct anagram-free $10$-colourable subdivisions with fewer division vertices per edge. Conversely, we prove lower bounds, in terms of division vertices per edge, on the anagram-free chromatic number for subdivisions of the complete graph and subdivisions of complete trees of bounded degree.

Recommendations

• Anagram-free colorings of graphs
• Anagram-free colourings of graphs
• Anagram-free graph colouring
• Acyclic colorings of graph subdivisions
• Acyclic colorings of graph subdivisions revisited
• Subgraph-avoiding coloring of graphs
• Subdivision of hypergraphs and their colorings
• Subcolorings and the subchromatic number of a graph
• Anticoloring and separation of graphs
• scientific article; zbMATH DE number 2159660

Cites work

• A powerful abelian square-free substitution over 4 letters
• Abelian squares are avoidable on 4 letters
• Anagram-free colourings of graphs
• Anagram-free graph colouring
• Characterisations and examples of graph classes with bounded expansion
• scientific article; zbMATH DE number 5130733 (Why is no real title available?)
• scientific article; zbMATH DE number 969188 (Why is no real title available?)
• New approach to nonrepetitive sequences
• Non-repetitive 3-coloring of subdivided graphs
• Nonrepetitive colorings of graphs
• Nonrepetitive colorings of graphs -- a survey
• Nonrepetitive colorings of trees
• Nonrepetitive colouring via entropy compression
• Nonrepetitive vertex colorings of graphs
• Notes on nonrepetitive graph colouring

Cited in

(6)

• Anagram-free chromatic number is not pathwidth-bounded
• Anagram-free colorings of graphs
• Anagram-free graph colouring
• 2 n grids have unbounded anagram-free chromatic number
• Facial anagram-free edge-coloring of plane graphs
• Anagram-free colourings of graphs

This page was built for publication: Anagram-Free Colorings of Graph Subdivisions

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4684464)