2 n grids have unbounded anagram-free chromatic number

DOI10.37236/10411MaRDI QIDQ2170797zbMATHOpenAlexFDO

Authors Saman Bazarghani, Paz Carmi, Pat Morin, Vida Dujmović

Publication date 6 September 2022

Published in The Electronic Journal of Combinatorics (Search for Journal in Brave)

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

IPFS File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

zbMATH Keywords

abelian square-free sequences\(k\)-anagram-free colouring

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15)

Abstract: We show that anagram-free vertex colouring a $2imesn$ square grid requires a number of colours that increases with $n$. This answers an open question in Wilson's thesis and shows that even graphs of pathwidth $2$ do not have anagram-free colourings with a bounded number of colours.

Recommendations

• Anagram-free graph colouring
• Anagram-free colourings of graphs
• Anagram-free colorings of graphs
• Anagram-free chromatic number is not pathwidth-bounded
• Anagram-Free Colorings of Graph Subdivisions

Cites work

• scientific article; zbMATH DE number 3162927 (Why is no real title available?)
• scientific article; zbMATH DE number 1737190 (Why is no real title available?)
• scientific article; zbMATH DE number 3296252 (Why is no real title available?)
• scientific article; zbMATH DE number 3375509 (Why is no real title available?)
• A powerful abelian square-free substitution over 4 letters
• Abelian squares are avoidable on 4 letters
• Anagram-Free Colorings of Graph Subdivisions
• Anagram-free chromatic number is not pathwidth-bounded
• Anagram-free colourings of graphs
• Anagram-free graph colouring
• Is There a Sequence on Four Symbols in Which No Two Adjacent Segments are Permutations of One Another?
• Tree-depth, subgraph coloring and homomorphism bounds

Cited in

(4)

• Anagram-free chromatic number is not pathwidth-bounded
• Every grid has an independent \([1, 2]\)-set
• Anagram-free colourings of graphs
• Anagram-free graph colouring

This page was built for publication: \(2\times n\) grids have unbounded anagram-free chromatic number

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