Colouring Planar Graphs With Three Colours and No Large Monochromatic Components. (July 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-07
• Subjects: Combinatorial analysis -- Periodicals; Probabilities -- Periodicals; Computer science -- Mathematics -- Periodicals; 511.6
• DOI: 10.1017/S0963548314000170
• Languages: English
• ISSNs: 0963-5483

Abstract

<abstract abstract-type="normal"> <title> <x content-type="archive" xml:space="preserve">Abstract</x> </title> <p>We prove the existence of a function <inline-formula><alternatives><inline-graphic xlink:href="ark:/27927/pghjm91rh6" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" /><tex-math><![CDATA[$f :\mathbb{N} \to \mathbb{N}$]]></tex-math></alternatives></inline-formula> 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 <italic>f</italic>(Δ) 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.</p> </abstract>