Geodesic
\(2\times n\) grids have unbounded anagram-free chromatic number
Saman Bazarghani1 ; Paz Carmi2 ; Vida Dujmović1 ; Pat Morin3
1University of Ottawa
2Ben-Gurion University of the Negev
3School of Computer Science, Carleton University
The electronic journal of combinatorics, Tome 29 (2022) no. 3
Cet article a éte moissonné depuis la source The Electronic Journal of Combinatorics website

Voir la notice de l'article

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 Wilson's thesis and shows that there are even graphs of pathwidth $2$ that do not have anagram-free colourings with a bounded number of colours.
DOI : 10.37236/10411
Classification : 05C15
Mots-clés : abelian square-free sequences, \(k\)-anagram-free colouring

Saman Bazarghani  1   ; Paz Carmi  2   ; Vida Dujmović  1   ; Pat Morin  3

1 University of Ottawa
2 Ben-Gurion University of the Negev
3 School of Computer Science, Carleton University 
@article{10_37236_10411,
     author = {Saman Bazarghani and Paz Carmi and Vida Dujmovi\'c and Pat Morin},
     title = {\(2\times n\) grids have unbounded anagram-free chromatic number},
     journal = {The electronic journal of combinatorics},
     year = {2022},
     volume = {29},
     number = {3},
     doi = {10.37236/10411},
     zbl = {1496.05048},
     url = {http://geodesic.mathdoc.fr/articles/10.37236/10411/}
}
TY  - JOUR
AU  - Saman Bazarghani
AU  - Paz Carmi
AU  - Vida Dujmović
AU  - Pat Morin
TI  - \(2\times n\) grids have unbounded anagram-free chromatic number
JO  - The electronic journal of combinatorics
PY  - 2022
VL  - 29
IS  - 3
UR  - http://geodesic.mathdoc.fr/articles/10.37236/10411/
DO  - 10.37236/10411
ID  - 10_37236_10411
ER  - 
%0 Journal Article
%A Saman Bazarghani
%A Paz Carmi
%A Vida Dujmović
%A Pat Morin
%T \(2\times n\) grids have unbounded anagram-free chromatic number
%J The electronic journal of combinatorics
%D 2022
%V 29
%N 3
%U http://geodesic.mathdoc.fr/articles/10.37236/10411/
%R 10.37236/10411
%F 10_37236_10411
Saman Bazarghani; Paz Carmi; Vida Dujmović; Pat Morin. \(2\times n\) grids have unbounded anagram-free chromatic number. The electronic journal of combinatorics, Tome 29 (2022) no. 3. doi: 10.37236/10411

Cité par Sources :