Colourings with Bounded Monochromatic Components in Graphs of Given Circumference

zbMATH Open1375.05102arXiv1612.05674MaRDI QIDQ4595652FDOQ4595652

Authors: Bojan Mohar, David R. Wood, 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

Recommendations

• Colouring planar graphs with bounded monochromatic components
• The Monochromatic Circumference of 2‐Edge‐Colored Graphs
• scientific article
• 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

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

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)