Colourings with Bounded Monochromatic Components in Graphs of Given Circumference

zbMATH Open1375.05102arXiv1612.05674MaRDI QIDQ4595652FDOQ4595652

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)

Cited In (8)

• Clustered colouring of graph classes with bounded treedepth or pathwidth
• Clustered 3-colouring graphs of bounded degree
• The Monochromatic Circumference of 2‐Edge‐Colored Graphs
• Cycles and new bounds for the chromatic number
• Clustered coloring of graphs with bounded layered treewidth and bounded degree
• Colouring strong products
• Improper colouring of graphs with no odd clique minor
• Clustered variants of Hajós' conjecture

   Recommendations

• Colouring planar graphs with bounded monochromatic components 👍 👎
• The Monochromatic Circumference of 2‐Edge‐Colored Graphs 👍 👎
• Title not available (Why is that?) 👍 👎
• Monochromatic components in edge-coloured graphs with large minimum degree 👍 👎
• Graph coloring with no large monochromatic components 👍 👎
• On monochromatic configurations for finite colorings 👍 👎
• Graph coloring with no large monochromatic components 👍 👎
• Total colorings of circulant 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)