\(2\times n\) grids have unbounded anagram-free chromatic number (Q2170797)
From MaRDI portal
 | This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use this page instead for the normal view: 2 n grids have unbounded anagram-free chromatic number |
scientific article
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| 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
0.8363838791847229
0 references
0.8248499035835266
0 references
0.8122950792312622
0 references
0.7950055003166199
0 references
0.7816109657287598
0 references
