Colourings with Bounded Monochromatic Components in Graphs of Given Circumference

MaRDI QIDQ4595652zbMATH OpenFDO

Authors Bojan Mohar, David R. Wood, Bruce Reed

Publication date 6 December 2017

Full work available at URL https://arxiv.org/abs/1612.05674, http://ajc.maths.uq.edu.au/pdf/69/ajc_v69_p236.pdf

zbMATH Keywords

colourings with bounded monochromatic degree

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15)

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.

Recommendations

• Colouring planar graphs with bounded monochromatic components
• The Monochromatic Circumference of 2‐Edge‐Colored Graphs
• scientific article; zbMATH DE number 4154488
• Monochromatic components in edge-coloured graphs with large minimum degree
• On monochromatic configurations for finite colorings
• 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

Cited in

(10)

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

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)