2019/05/21 by Chuandong Xu, Xu, Chuandong, Hongna Yang +3
Computer Science · Mathematics · #Advanced Graph Theory Research #Advanced Topology and Set Theory #Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Limits and Structures in Graph Theory
paper · pdf · doi:10.48550/arxiv.1905.08456
openalex publication_date 2019/05/21 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Given simple graphs H1,H2,…,Hc, the Ramsey number r(H1,H2,…,Hc) is the smallest positive integer n such that every edge-colored Kn with c colors contains a subgraph in color i isomorphic to Hi for some i∈\1,2,…,c\. The critical graphs for r(H1,H2,…,Hc) are edge-colored complete graphs on r(H1,H2,…,Hc)-1 vertices with c colors which contain no subgraphs in color i isomorphic to Hi for any i∈ \1,2,…,c\. For n1≥ n2≥ …≥ nc≥ 1, Cockayne and Lorimer (The Ramsey number for stripes, \it J. Austral. Math. Soc. 19 (1975), 252--256.) showed that r(n1K2,n2K2,…,ncK2)=n1+1+ ∑i=1c(ni-1), in which niK2 is a matching of size ni. Using the Gallai-Edmonds Theorem, we characterized all the critical graphs for r(n1K2,n2K2,…,ncK2), implying a new proof for this Ramsey number.