Lecture By Prof. Yuejian Peng of Hunan University
time: 2021-01-06

Title: Tree-Star Ramsey Numbers  

Speaker:  Prof. Yuejian Peng ( Hunan University )

Time: Sat, Dec.26 2020, AM: 10:30-11:30

Location: Tencent Conference

Meeting  Number: 957 629 038

Password: 123456

Inviter: Prof. Hongying Lin


Abstract:

        Let Tn be a tree on n vertices and K1, m be the star with m+1 vertices. For graphs G and H, the Ramsey Number R(G, H) is the smallest integer N such that any red-blue-coloring of the edges of KN yields a red G or a blue H. A well-known result is that if G is a graph with minimum degree n-1, then Tn can be embedded into G.  Applying this result, Burr gave an upper bound for the Ramsey number R(Tn, K1, m) and determined the exact value of R(Tn, K1, m) for some cases. Guo and Volkmann showed that if G is a connected graph with at least n vertices and minimum degree n-2, then Tn can be embedded into G except Tn=K1, n-1. Applying this, they improved that bound of R(Tn, K1, m) in the result of Burr by 1 for some cases and obtain the exact value of  R(Tn, K1, m) for some cases in addition to Burr's result. Guo and Volkmann also conjectured that if G is a  connected graph with at least n vertices and minimum degree n-3, then Tn with maximum degree ≤n-4 can be embedded into G. In this paper, we obtain a sufficient and necessary condition that Tn with maximum degree ≤n-3 can be embedded into a connected graph G with at least n vertices and minimum degree ≥n-3. Our result implies that the conjecture of Guo and Volkmann is true with one exception.  Applying this result, we improve the upper bound of R(Tn, K1, m) and determine the exact value of R(Tn, K1, m) for some cases. (This is a joint work with Yan Zi-Long.)