2 × n grids have unbounded anagram-free chromatic number

Saman Bazargani, Paz Carmi, Vida Dujmović, Pat Morin

פרסום מחקרי: פרסום בכתב עתמאמרביקורת עמיתים

תקציר

We show that anagram-free vertex colouring a 2 × n square grid requires a number of colours that increases with n. This answers an open question in Wilson’s thesis and shows that that are even graphs of pathwidth 2 that do not have anagram-free colourings with a bounded number of colours.

שפה מקוריתאנגלית אמריקאית
מספר המאמר3.43
כתב עתElectronic Journal of Combinatorics
כרך29
מספר גיליון3
מזהי עצם דיגיטלי (DOIs)
סטטוס פרסוםפורסם - 1 ינו׳ 2022

ASJC Scopus subject areas

  • ???subjectarea.asjc.2600.2614???
  • ???subjectarea.asjc.2600.2608???
  • ???subjectarea.asjc.2600.2607???
  • ???subjectarea.asjc.1700.1703???
  • ???subjectarea.asjc.2600.2604???

טביעת אצבע

להלן מוצגים תחומי המחקר של הפרסום '2 × n grids have unbounded anagram-free chromatic number'. יחד הם יוצרים טביעת אצבע ייחודית.

פורמט ציטוט ביבליוגרפי