Colouring planar graphs with three colours and no large monochromatic components

DOI10.1017/S0963548314000170MaRDI QIDQ5495675zbMATH OpenOpenAlexFDO

Authors L. Esperet, Gwenaël Joret

Publication date 6 August 2014

Published in Combinatorics, Probability and Computing (Search for Journal in Brave)

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

zbMATH Keywords

colouringmaximum degreemonochromatic subgraphplanar graphs

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Coloring of graphs and hypergraphs (05C15) Structural characterization of families of graphs (05C75)

Abstract: We prove the existence of a function $f:mathbbNomathbbN$ such that the vertices of every planar graph with maximum degree $Delta$ can be 3-colored in such a way that each monochromatic component has at most $f(Delta)$ vertices. This is best possible (the number of colors cannot be reduced and the dependence on the maximum degree cannot be avoided) and answers a question raised by Kleinberg, Motwani, Raghavan, and Venkatasubramanian in 1997. Our result extends to graphs of bounded genus.

Recommendations

• Clustered 3-colouring graphs of bounded degree
• scientific article; zbMATH DE number 4089589
• Polychromatic colorings of bounded degree plane graphs
• 3-hued coloring of planar graphs
• Planar graphs without cycles of length from 4 to 7 are 3-colorable

Cites work

• A relaxed Hadwiger's conjecture for list colorings
• An extremal function for contractions of graphs
• Bounded size components -- partitions and transversals.
• Contractibility and the Hadwiger conjecture
• From the plane to higher surfaces
• Low diameter graph decompositions
• Lower bound of the Hadwiger number of graphs by their average degree
• Partitioning into graphs with only small components

Cited in

(22)

• On monochromatic component size for improper colourings
• On fractional fragility rates of graph classes
• Proper coloring of geometric hypergraphs
• Clustered variants of Hajós' conjecture
• scientific article; zbMATH DE number 4089589 (Why is no real title available?)
• Splitting planar graphs of girth 6 into two linear forests with short paths
• Minor-Closed Graph Classes with Bounded Layered Pathwidth
• WORM colorings of planar graphs
• Improper colouring of graphs with no odd clique minor
• Some of my favorite coloring problems for graphs and digraphs
• Clustered colouring of graph classes with bounded treedepth or pathwidth
• Clustered 3-colouring graphs of bounded degree
• Partitioning \(H\)-minor free graphs into three subgraphs with no large components
• Partitioning \(H\)-minor free graphs into three subgraphs with no large components
• Clustered coloring of graphs with bounded layered treewidth and bounded degree
• Weak diameter coloring of graphs on surfaces
• Colouring strong products
• Product structure of graph classes with bounded treewidth
• Weak diameter choosability of graphs with an excluded minor
• Realizing an m-uniform four-chromatic hypergraph with disks
• Clustered coloring of (path + 2K₁)-free graphs on surfaces
• Clustered coloring of graphs excluding a subgraph and a minor

This page was built for publication: Colouring planar graphs with three colours and no large monochromatic components

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