Colourings with Bounded Monochromatic Components in Graphs of Given Circumference

Abstract

We prove that every graph with circumference at most $k$ is $O(\log k)$-colourable such that every monochromatic component has size at most $O(k)$. The $O(\log k)$ bound on the number of colours is best possible, even in the setting of colourings with bounded monochromatic degree.

References in corpus (2)

• A relative of Hadwiger's conjecture
• Defective colouring of graphs excluding a subgraph or minor