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).
Item Type: | Article |
---|---|
Subjects: | Q Science / természettudomány > QA Mathematics / matematika |
SWORD Depositor: | MTMT SWORD |
Depositing User: | MTMT SWORD |
Date Deposited: | 06 Feb 2014 21:30 |
Last Modified: | 06 Feb 2014 21:30 |
URI: | http://real.mtak.hu/id/eprint/10043 |
Actions (login required)
![]() |
Edit Item |