\(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
    0 references
    0 references
    0 references
    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

    Identifiers