\(2\times n\) grids have unbounded anagram-free chromatic number (Q2170797)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | \(2\times n\) grids have unbounded anagram-free chromatic number |
scientific article |
Statements
\(2\times n\) grids have unbounded anagram-free chromatic number (English)
0 references
6 September 2022
0 references
Summary: We show that anagram-free vertex colouring a \(2\times n\) square grid requires a number of colours that increases with \(n\). This answers an open question in \textit{T. E. Wilson}'s thesis [Anagram-free graph colouring and colour schemes. Melbourne: Monash University (PhD Thesis) (2019)] and shows that there are even graphs of pathwidth \(2\) that do not have anagram-free colourings with a bounded number of colours.
0 references
abelian square-free sequences
0 references
\(k\)-anagram-free colouring
0 references
0 references