Mathematics – Combinatorics
Scientific paper
2007-03-12
Mathematics
Combinatorics
13 pages, 2 figures
Scientific paper
For a graph G and an integer t we let mcc_t(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 \mcc_2(G) = O(n^{2/3}) for any n-vertex graph G \in 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 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)=\Omega(n^{2/(2t-1)}). It is also interesting to consider graphs of bounded degrees. Haxell, Szabo, and Tardos proved \mcc_2(G) \leq 20000 for every graph G of maximum degree 5. We show that there are n-vertex 7-regular graphs G with \mcc_2(G)=\Omega(n), and more sharply, for every \epsilon>0 there exists c_\epsilon>0 and n-vertex graphs of maximum degree 7, average degree at most 6+\epsilon for all subgraphs, and with mcc_2(G)\ge c_\eps 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).
Linial Nathan
Matoušek Jiří
Sheffet Or
Tardos Gabor
No associations
LandOfFree
Graph coloring with no large monochromatic components does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Graph coloring with no large monochromatic components, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Graph coloring with no large monochromatic components will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-438926