Colouring Planar Graphs With Three Colours and No Large Monochromatic Components

DOI10.1017/S0963548314000170zbMath1334.05030arXiv1303.2487MaRDI QIDQ5495675

Louis 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

colouring; planar graphs; maximum degree; monochromatic subgraph

Mathematics Subject Classification ID

05C10: Planar graphs; geometric and topological aspects of graph theory

05C75: Structural characterization of families of graphs

05C15: Coloring of graphs and hypergraphs

Related Items

Splitting Planar Graphs of Girth 6 into Two Linear Forests with Short Paths, Minor-Closed Graph Classes with Bounded Layered Pathwidth, Improper colouring of graphs with no odd clique minor, Some of My Favorite Coloring Problems for Graphs and Digraphs, Partitioning \(H\)-minor free graphs into three subgraphs with no large components, Partitioning \(H\)-minor free graphs into three subgraphs with no large components, Islands in Graphs on Surfaces, Clustered colouring of graph classes with bounded treedepth or pathwidth, Clustered 3-colouring graphs of bounded degree, WORM colorings of planar graphs, On fractional fragility rates of graph classes, Proper coloring of geometric hypergraphs, Clustered variants of Hajós' conjecture

Cites Work

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