The anagram-free chromatic number is a new graph parameter introduced independently by Kamcev, Luczak, and Sudakov and Wilson and Wood . In this note, we show that there are planar graphs of pathwidth 3 with arbitrarily large anagram-free chromatic number. More specifically, we describe 2n-vertex planar graphs of pathwidth 3 with anagram-free chromatic number Ω(log n). We also describe kn vertex graphs with pathwidth 2k-1 having anagram-free chromatic number in Ω(k log n).
展开▼
