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\).

05C15 Coloring of graphs and hypergraphs
05C83 Graph minors
05C55 Generalized Ramsey theory
Full Text: DOI
[1] Matou?ek, Invitation to Discrete Mathematics (1998)
[2] DOI: 10.1016/0196-6774(86)90023-4 · Zbl 0611.05017 · doi:10.1016/0196-6774(86)90023-4
[3] DOI: 10.1007/BF01303516 · Zbl 0790.05067 · doi:10.1007/BF01303516
[4] DOI: 10.1016/S0095-8956(03)00031-5 · Zbl 1033.05083 · doi:10.1016/S0095-8956(03)00031-5
[5] DOI: 10.1016/j.jctb.2006.11.002 · Zbl 1123.05039 · doi:10.1016/j.jctb.2006.11.002
[6] DOI: 10.2307/2320146 · Zbl 0448.90097 · doi:10.2307/2320146
[7] Jensen, Graph Coloring Problems (1995)
[8] Janson, Topics in Random Graphs (2000) · doi:10.1002/9781118032718
[9] DOI: 10.1007/BF01275667 · Zbl 0755.05045 · doi:10.1007/BF01275667
[10] DOI: 10.1016/0012-365X(95)00293-6 · Zbl 0870.05036 · doi:10.1016/0012-365X(95)00293-6
[11] Bollob?s, Set Systems, Hypergraphs, Families of Vectors and Combinatorial Probability (1986)
[12] DOI: 10.1090/S0273-0979-06-01126-8 · Zbl 1147.68608 · doi:10.1090/S0273-0979-06-01126-8
[13] DOI: 10.2307/1990903 · Zbl 0747.05051 · doi:10.2307/1990903
[14] DOI: 10.1016/S0095-8956(02)00006-0 · Zbl 1023.05045 · doi:10.1016/S0095-8956(02)00006-0
[15] DOI: 10.1006/jctb.1998.1868 · Zbl 0930.05043 · doi:10.1006/jctb.1998.1868
[16] DOI: 10.1006/jctb.1995.1006 · Zbl 0823.05038 · doi:10.1006/jctb.1995.1006
[17] DOI: 10.1016/0095-8956(91)90061-N · Zbl 0764.05069 · doi:10.1016/0095-8956(91)90061-N
[18] 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.