2 n grids have unbounded anagram-free chromatic number
From MaRDI portal
Publication:2170797
DOI10.37236/10411zbMATH Open1496.05048arXiv2105.01916OpenAlexW4297724406MaRDI QIDQ2170797FDOQ2170797
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)
Abstract: We show that anagram-free vertex colouring a square grid requires a number of colours that increases with . This answers an open question in Wilson's thesis and shows that even graphs of pathwidth do not have anagram-free colourings with a bounded number of colours.
Full work available at URL: https://arxiv.org/abs/2105.01916
File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)
Recommendations
Cites Work
- Title not available (Why is that?)
- Tree-depth, subgraph coloring and homomorphism bounds
- Title not available (Why is that?)
- Abelian squares are avoidable on 4 letters
- Title not available (Why is that?)
- Title not available (Why is that?)
- Is There a Sequence on Four Symbols in Which No Two Adjacent Segments are Permutations of One Another?
- A powerful abelian square-free substitution over 4 letters
- Anagram-free chromatic number is not pathwidth-bounded
- Anagram-free graph colouring
- Anagram-free colourings of graphs
- Anagram-Free Colorings of Graph Subdivisions
Cited In (4)
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)
