# zbMATH — the first resource for mathematics

Graph colouring with no large monochronomatic components. (English) Zbl 1171.05021
Summary: 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 $$\mathcal F$$ 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\in{\mathcal F}$$. This bound is asymptotically optimal and it is attained for planar graphs. More generally, for every such $$\mathcal 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. P. Haxell, T. Szabó and G. Tardo [J. Comb. Theory, Ser. B 88, No. 2, 281–297 (2003; Zbl 1033.05083)] proved $$mcc_t(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 $$\varepsilon > 0$$ there exists $$c_\varepsilon > 0$$ and $$n$$-vertex graphs of maximum degree 7, average degree at most $$6 + \varepsilon$$ for all subgraphs, and with $$mcc_2(G)\geq c_\varepsilon n$$. For 6-regular graphs it is known only that the maximum order of magnitude of $$mcc_2$$ is between $$\sqrt n$$ and $$n$$.

##### MSC:
 05C15 Coloring of graphs and hypergraphs 05C83 Graph minors 05C55 Generalized Ramsey theory
Full Text:
##### References:
  Matou?ek, Invitation to Discrete Mathematics (1998)  DOI: 10.1016/0196-6774(86)90023-4 · Zbl 0611.05017 · doi:10.1016/0196-6774(86)90023-4  DOI: 10.1007/BF01303516 · Zbl 0790.05067 · doi:10.1007/BF01303516  DOI: 10.1016/S0095-8956(03)00031-5 · Zbl 1033.05083 · doi:10.1016/S0095-8956(03)00031-5  DOI: 10.1016/j.jctb.2006.11.002 · Zbl 1123.05039 · doi:10.1016/j.jctb.2006.11.002  DOI: 10.2307/2320146 · Zbl 0448.90097 · doi:10.2307/2320146  Jensen, Graph Coloring Problems (1995)  Janson, Topics in Random Graphs (2000) · doi:10.1002/9781118032718  DOI: 10.1007/BF01275667 · Zbl 0755.05045 · doi:10.1007/BF01275667  DOI: 10.1016/0012-365X(95)00293-6 · Zbl 0870.05036 · doi:10.1016/0012-365X(95)00293-6  Bollob?s, Set Systems, Hypergraphs, Families of Vectors and Combinatorial Probability (1986)  DOI: 10.1090/S0273-0979-06-01126-8 · Zbl 1147.68608 · doi:10.1090/S0273-0979-06-01126-8  DOI: 10.2307/1990903 · Zbl 0747.05051 · doi:10.2307/1990903  DOI: 10.1016/S0095-8956(02)00006-0 · Zbl 1023.05045 · doi:10.1016/S0095-8956(02)00006-0  DOI: 10.1006/jctb.1998.1868 · Zbl 0930.05043 · doi:10.1006/jctb.1998.1868  DOI: 10.1006/jctb.1995.1006 · Zbl 0823.05038 · doi:10.1006/jctb.1995.1006  DOI: 10.1016/0095-8956(91)90061-N · Zbl 0764.05069 · doi:10.1016/0095-8956(91)90061-N  DOI: 10.1137/0136016 · Zbl 0432.05022 · doi:10.1137/0136016
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.