×

Edges not covered by monochromatic bipartite graph. (English) Zbl 1525.05060

Summary: Let \(f_k(n,H)\) denote the maximum number of edges not contained in any monochromatic copy of \(H\) in a \(k\)-coloring of the edges of \(K_n\), and let \(\mathrm{ex}(n,H)\) denote the Turán number of \(H\). In place of \(f_2(n,H)\) we simply write \(f(n,H)\). P. Keevash and B. Sudakov [J. Comb. Theory, Ser. B 90, No. 1, 41–53 (2004; Zbl 1033.05042)] proved that \(f(n,H)=\mathrm{ex}(n,H)\) if \(H\) is an edge-critical graph or \(C_4\) and asked if this equality holds for any graph \(H\). All known exact values of this question require \(H\) to contain at least one cycle. In this paper we focus on acyclic graphs and present the following results: (1) We prove \(f(n,H)=\mathrm{ex}(n,H)\) when \(H\) is a spider or a double broom. (2) We show that a tail in \(H\) is a path \(P_3=v_0v_1v_2\) such that \(v_2\) is only adjacent to \(v_1\), and \(v_1\) is only adjacent to \(v_0,v_2\) in \(H\). We obtain a tight upper bound for \(f(n,H)\) when \(H\) is a bipartite graph with a tail. This result provides the first bipartite graphs which answer the question of Keevash and Sudakov [loc. cit.] in the negative. (3) We answer a question of H. Liu et al. [ibid. 135, 16–43 (2019; Zbl 1404.05056)] who asked if \(f_k(n,T)=(k-1)\mathrm{ex}(n,T)\) when \(T\) is a tree. We provide an upper bound for \(f_{2k}(n,P_{2k})\) and show it is tight when \(2k-1\) is prime. This provides a negative answer to their question.

MSC:

05C15 Coloring of graphs and hypergraphs
05C55 Generalized Ramsey theory
05D10 Ramsey theory
05D40 Probabilistic methods in extremal combinatorics, including polynomial methods (combinatorial Nullstellensatz, etc.)
05C35 Extremal problems in graph theory
05C70 Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)

References:

[1] Bushaw, N. and Kettle, N., Turán numbers of multiple paths and equibipartite forests, Combin. Probab. Comput., 20 (2011), pp. 837-853. · Zbl 1234.05128
[2] Erdős, P., Some recent problems and results in graph theory, Discrete Math., 164 (1997), pp. 81-85. · Zbl 0871.05054
[3] Erdős, P. and Simonovits, M., A limit theorem in graph theory, Studia Sci. Math. Hungar., 1 (1966), pp. 51-57. · Zbl 0178.27301
[4] Erdős, P. and Stone, A., On the structure of linear graphs, Bull. Amer. Math. Soc., 52 (1946), pp. 1087-1091. · Zbl 0063.01277
[5] Faudree, R. and Schelp, R., Path Ramsey numbers in multicolorings, J. Combin. Theory Ser. B, 19 (1975), pp. 150-160. · Zbl 0286.05111
[6] Goodman, A., On sets of acquaintances and strangers at any party, Amer. Math. Monthly, 66 (1959), pp. 778-783. · Zbl 0092.01305
[7] Keevash, P. and Sudakov, B., On the number of edges not covered by monochromatic copies of a fixed graph, J. Combin. Theory Ser. B, 90 (2004), pp. 41-53. · Zbl 1033.05042
[8] Liu, H., Pikhurko, O., and Sharifzadeh, M., Edges not in any monochromatic copy of a fixed graph, J. Combin. Theory Ser. B, 135 (2019), pp. 16-43. · Zbl 1404.05056
[9] Ma, J., On edges not in monochromatic copies of a fixed bipartite graph, J. Combin. Theory Ser. B, 123 (2017), pp. 240-248. · Zbl 1367.05077
[10] McLennan, A., The Erdős-Sós conjecture for trees of diameter four, J. Graph Theory, 49 (2005), pp. 291-301. · Zbl 1068.05035
[11] Pyber, L., Clique covering of graphs, Combinatorica, 6 (1986), pp. 393-398. · Zbl 0641.05030
[12] Thomason, A., Graph products and monochromatic multiplicities, Combinatorica, 17 (1997), pp. 125-134. · Zbl 0886.05100
[13] Yuan, L.-T., Extremal graphs for edge blow-up of graphs, J. Combin. Theory Ser. B, 152 (2022), pp. 379-398. · Zbl 1478.05083
[14] Zhu, X. and Chen, Y., Turán number for odd-ballooning of trees, J. Graph Theory, 104 (2023), pp. 261-274. · Zbl 1522.05043
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.