Anagram-Free Chromatic Number is not Pathwidth-Bounded

DOI10.1007/978-3-030-00256-5_8MaRDI QIDQ6297352arXivFDO

Authors Paz Carmi, Vida Dujmović, Pat Morin

Publication date 5 February 2018

Published in arXiv

Full work available at URL https://doi.org/10.1007/978-3-030-00256-5_8

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Coloring of graphs and hypergraphs (05C15) Random graphs (graph-theoretic aspects) (05C80) Graph algorithms (graph-theoretic aspects) (05C85)

arXiv classification

math.CO

Abstract: The anagram-free chromatic number is a new graph parameter introduced independently Kamv{c}ev, {L}uczak, and Sudakov (2017) and Wilson and Wood (2017). 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 $Omega(logn)$. We also describe $kn$ vertex graphs with pathwidth $2k-1$ having anagram-free chromatic number in $Omega(klogn)$.

This page was built for publication: Anagram-Free Chromatic Number is not Pathwidth-Bounded

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6297352)