Colourings with Bounded Monochromatic Components in Graphs of Given Circumference

zbMATH Open1375.05102arXiv1612.05674MaRDI QIDQ4595652

David R. Wood, Bojan Mohar, Bruce Reed

Publication date: 6 December 2017

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

Full work available at URL: https://arxiv.org/abs/1612.05674

zbMATH Keywords

colourings with bounded monochromatic degree

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15)

Related Items (6)

Clustered colouring of graph classes with bounded treedepth or pathwidth ⋮ Clustered 3-colouring graphs of bounded degree ⋮ Clustered variants of Hajós' conjecture ⋮ Clustered coloring of graphs with bounded layered treewidth and bounded degree ⋮ Colouring strong products ⋮ Improper colouring of graphs with no odd clique minor

Recommendations

• Title not available (Why is that?) 👍 👎
• On monochromatic configurations for finite colorings 👍 👎
• Colouring planar graphs with bounded monochromatic components 👍 👎
• Monochromatic components in edge-coloured graphs with large minimum degree 👍 👎
• Graph coloring with no large monochromatic components 👍 👎
• Total colorings of circulant graphs 👍 👎
• The Monochromatic Circumference of 2‐Edge‐Colored Graphs 👍 👎
• Colouring graphs of bounded diameter in the absence of small cycles 👍 👎
• Colouring graphs of bounded diameter in the absence of small cycles 👍 👎

This page was built for publication: Colourings with Bounded Monochromatic Components in Graphs of Given Circumference

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