Graph coloring with no large monochromatic components

Linial, N. and Matoušek, J. and Sheffet, O. and Tardos, Gábor (2007) Graph coloring with no large monochromatic components. ELECTRONIC NOTES IN DISCRETE MATHEMATICS, 29 (SPEC. ). pp. 115-122. ISSN 1571-0653

Text 0703362.pdf Restricted to Repository staff only Download (200kB) | Request a copy

Abstract

For a graph G and an integer t we let m c ct (G) be the smallest m such that there exists a coloring of the vertices of G by t colors with no monochromatic connected subgraph having more than m vertices. Let F be any nontrivial minor-closed family of graphs. We show that mcc2 (G) = O (n2 / 3) for any n-vertex graph G ∈ F. This bound is asymptotically optimal and it is attained for planar graphs. More generally, for every such F, and every fixed t we show that mcct (G) = O (n2 / (t + 1)). On the other hand, we have examples of graphs G with no Kt + 3 minor and with mcct (G) = Ω (n(2 / 2 t - 1)). It is also interesting to consider graphs of bounded degrees. Haxell, Szabó, and Tardos proved mcc2 (G) ≤ 20000 for every graph G of maximum degree 5. We show that there are n-vertex 7-regular graphs G with mcc2 (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 mcc2 (G) ≥ cε n. For 6-regular graphs it is known only that the maximum order of magnitude of mcc2 is between sqrt(n) and n. We also offer a Ramsey-theoretic perspective of the quantity m c ct (G).

Actions (login required)

Edit Item