Colouring Planar Graphs With Three Colours and No Large Monochromatic Components. (1st April 2014)

• Record Type: Journal Article
• Authors: ESPERET, LOUIS; JORET, GWENAËL
• Is Part Of: Combinatorics, probability and computing. Volume 23:Number 4(2014:Jul.)
• Page Start: 551
• Page End: 570
• Publication Date: 2014-04-01
• Subjects: Primary 05C15, -- Secondary 05C10; Combinatorial analysis -- Periodicals; Probabilities -- Periodicals; Computer science -- Mathematics -- Periodicals; 511.6
• DOI: 10.1017/S0963548314000170
• Languages: English
• ISSNs: 0963-5483

Abstract

Abstract : We prove the existence of a function $f :\mathbb{N} \to \mathbb{N}$ such that the vertices of every planar graph with maximum degree Δ can be 3-coloured in such a way that each monochromatic component has at most f (Δ) vertices. This is best possible (the number of colours 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.