Graph coloring with no large monochromatic components

Simple item page
dc.creatorLinial, N.
dc.creatorMatousek, J.
dc.creatorSheffet, O.
dc.creatorTardos, G.
dc.date2007-03-12
dc.date.accessioned2026-07-07T07:56:37Z
dc.date.available2026-07-07T07:56:37Z
dc.descriptionFor 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)=Ω(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)=Ω(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)\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).
dc.description13 pages, 2 figures
dc.identifierhttps://arxiv.org/abs/math/0703362
dc.identifierhttp://arxiv.org/abs/math/0703362
dc.identifier.urihttp://salesiana.dossiersoluciones.com/handle/123456789/127373
dc.subjectCombinatorics
dc.subject05C15
dc.titleGraph coloring with no large monochromatic components
dc.typetext

Files

Collections

arXiv