Clustered 3-Colouring Graphs of Bounded Degree

DOI10.1017/S0963548321000213MaRDI QIDQ6335650arXivFDO

Authors Vida Dujmović, L. Esperet, Pat Morin, Bartosz Walczak, David R. Wood

Publication date 26 February 2020

Published in arXiv

Full work available at URL https://doi.org/10.1017/S0963548321000213

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Coloring of graphs and hypergraphs (05C15) Graph minors (05C83)

arXiv classification

math.CO

Abstract: A (not necessarily proper) vertex colouring of a graph has "clustering" $c$ if every monochromatic component has at most $c$ vertices. We prove that planar graphs with maximum degree $Delta$ are 3-colourable with clustering $O(Delt{a}^2)$. The previous best bound was $O(Delt{a}^{37})$. This result for planar graphs generalises to graphs that can be drawn on a surface of bounded Euler genus with a bounded number of crossings per edge. We then prove that graphs with maximum degree $Delta$ that exclude a fixed minor are 3-colourable with clustering $O(Delt{a}^5)$. The best previous bound for this result was exponential in $Delta$.

This page was built for publication: Clustered 3-Colouring Graphs of Bounded Degree

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