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
المعرِّفات الرقمية للأشياء
حالة النشرنُشِر - 1 يناير 2022

All Science Journal Classification (ASJC) codes

  • !!Theoretical Computer Science
  • !!Geometry and Topology
  • !!Discrete Mathematics and Combinatorics
  • !!Computational Theory and Mathematics
  • !!Applied Mathematics

بصمة

أدرس بدقة موضوعات البحث “2 × n grids have unbounded anagram-free chromatic number'. فهما يشكلان معًا بصمة فريدة.

قم بذكر هذا