Graph Colouring with No Large Monochromatic Components
Nathan Linial, Jiřı́ Matoušek, Or Sheffet, Gábor Tardos · Combinatorics Probability Computing · 2008
For a graph G and an integer t we let mcc t ( G ) be the smallest m such that there exists a colouring of the vertices of G by t colours with no monochromatic connected subgraph having more than m vertices. Let be any non-trivial minor-closed family of graphs. We show that mcc 2 ( G ) = O ( n 2/3 ) for any n -vertex graph G ∈ . This bound is asymptotically optimal and it is attained for planar graphs. More generally, for every such , and every fixed t we show that mcc t ( G )= O ( n 2/( t +1) ). On the other hand, we have examples of graphs G with no K t +3 minor and with mcc t ( G )=Ω( n 2/(2 t −1) ). It is also interesting to consider graphs of bounded degrees. Haxell, Szabó and Tardos proved mcc 2 ( G ) ≤ 20000 for every graph G of maximum degree 5. We show that there are n -vertex 7-regular graphs G with mcc 2 ( G )=Ω( n ), and more sharply, for every ϵ > 0 there exists c ϵ > 0 and n -vertex graphs of maximum degree 7, average degree at most 6 + ϵ for all subgraphs, and with mcc 2 ( G ) ≥ c ϵ n . For 6-regular graphs it is known only that the maximum order of magnitude of mcc 2 is between $\sqrt n$ and n . We also offer a Ramsey-theoretic perspective of the quantity mcc t ( G ).