Colouring Planar Graphs With Three Colours and No Large Monochromatic Components

DOI10.1017/S0963548314000170zbMath1334.05030arXiv1303.2487OpenAlexW3104062130MaRDI 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

colouringplanar graphsmaximum degreemonochromatic subgraph

Mathematics Subject Classification ID

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

Related Items (13)

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

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

This page was built for publication: Colouring Planar Graphs With Three Colours and No Large Monochromatic Components