| Let H1,...,Ht be graphs.The Ramsey number r(H1,...,Ht)is the minimum integer N such that any t-coloring of E(KN)yields a monochromatic copy of Hi0,with color i0 for some i0∈[t].Let mK1,t denote m vertex-disjoint copies of K1,t.An easy lower bound is that r(mK1,t,nK1,s)≥max{m(t+1)+n-1.n(s+1)+m-1}.In 1975,Burr,Erd?s and Spencer proved that if t=s=3,m≥2 and m≥n,then this lower bound is also an upper bound for r(mK1,t,nK1,s).In 1979,Grossman proved that r(2K1,t,2K1,t)=max{3t,2t+3} which shows that if t≥4,then the lower bound is not the upper bound for r(2K1,t,2K1,t).In this paper,we show that if t≥s=3,m≥2 and m≥n,or s≥4,t≥(s(s-1))/2 and m>n,then this lower bound is also an upper bound for r(mK1,t,nK1,s).Let G be a graph.Let χ(G)denote the chromatic number of G and s(G)denote the chromatic surplus of G,the cardinality of a minimum color class taken over all proper colorings of H with χ(H)colors.In 1981,Burr showed that for a connected graph H and a graph J with |V(J)|≥s(H),r(H,J)≥|V(H)|1)(χ(J)-1)+s(J).If the equality holds,then call H J-good.Let Km denote a complete graph with m vertices and tKm denote t vertex disjoint copies of Km.Chvátal showed that if m≥,then any tree is Km-good.Recently,Hu and Peng proved that if n≥3 and m≥2,then any tree Tn is 2Km-good.They also showed that if t≥3,then any large tree is tK2-good.In this paper,we show that if t≥3 and m≥3,then any large tree is tKm-good.Let H1,...,Ht be graphs.The bipartite Ramsey number br(H1,...,Ht)is the minimum integer N such that any t-coloring of E(KN,N)yields a monochromatic copy of Hi0 with color i0 for some i0∈[t].Let s be an integer and CMs be a connected graph containing a matching of size s.In 2019,Bucic,Letzter and Sudakov determined the exact values of br(CMk,CMl,CMl)and led to the asymptotic value of 3-colored bipartite Ramsey number of cycles(symmetric case).In this paper,we determine the exact values of br(CMk,CMl,CMm)completely.This answers a question of Bucic,Letzter and Sudakov.Applying Szemerédi’s regularity lemma and Luczak method,we obtain the asymptotic value of 3-colored bipartite Ramsey number of cycles for all asymmetric cases.Let G and F be graphs.G is F-saturated if G does not contain any copy of F,but for any edge e ∈ E(G),the addition of e to G creates a new copy of F containing e.The saturation number sat(n,F)is the minimum number of edges over all F-saturated graphs on n vertices.G is weakly F-saturated if G does not contain any copy of F,but there exists an ordering {e1,...,et} of E(G)such that for each i∈[t],the addition of ei to G∪{e1,...,ei-1}creates a new copy of F containing ei.The weak saturation number wsat(n,F)is the minimum number of edges over all weakly F-saturated graphs on n vertices.In this paper,we show that sat(n,Ks∨D)=(2s)+s(n-s)+sat(n-s,D)for n≥3s2-s+2sat(n-s,D)+1,where D is a graph without any isolated vertex.As a direct corollary,we obtain that sat(n,Fps)=(2s)+s(n-s)+3p-3 for n≥3s2-s+6p-5,where Fps denotes the generalized fan Ks ∨ pK2.We also give an upper bound and a lower bound of the weak saturation number of the join of two graphs.Furthermore,we show that(?)... |
