2022/01/13 by Sinan Hu, Hu, Sinan, Yuejian Peng +1
Computer Science · Mathematics · #Advanced Graph Theory Research #Advanced Topology and Set Theory #Combinatorics (math.CO) #FOS: Mathematics #Limits and Structures in Graph Theory
paper · pdf · doi:10.48550/arxiv.2201.04884
openalex publication_date 2022/01/13 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Given two graphs G and H, the Ramsey number R(G,H) is the minimum integer N such that any coloring of the edges of KN in red or blue yields a red G or a blue H. Let v(G) be the number of vertices of G and χ(G) be the chromatic number of G. Let s(G) denote the chromatic surplus of G, the cardinality of a minimum color class taken over all proper colorings of G with χ(G) colors. Burr showed that for a connected graph G and a graph H with v(G)≥ s(H), R(G,H) ≥ (v(G)-1)(χ(H)-1)+s(H). A connected graph G is called H-good if R(G,H)=(v(G)-1)(χ(H)-1)+s(H). In this paper, we mainly confirm the Ramsey number for any tree Tn versus Km∪ Kl. Our result yields that Tn is Km∪ Kl-good.