On characterizing the critical graphs for matching Ramsey numbers

Abstract

Given simple graphs $H_1,H_2,\dots ,H_c$, the Ramsey number $r(H_1,H_2,\dots ,H_c)$ is the smallest positive integer $n$ such that every edge-colored $K_n$ with $c$ colors contains a subgraph in color $i$ isomorphic to $H_i$ for some $i\in \{1,2,\dots ,c\}$. The critical graphs for $r(H_1,H_2,\dots ,H_c)$ are edge-colored complete graphs on $r(H_1,H_2,\dots ,H_c)-1$ vertices with $c$ colors which contain no subgraphs in color $i$ isomorphic to $H_i$ for any $i\in \{1,2,\dots ,c\}$. For $n_1\ge n_2\ge \dots \ge n_c\ge 1$, Cockayne and Lorimer (The Ramsey number for stripes, {\it J.\ Austral.\ Math.\ Soc.} \textbf{19} (1975), 252--256.) showed that $r(n_1{K}_2,n_2{K}_2,\dots ,n_c{K}_2)=n_1+1+\sum _{i=1}^c(n_i-1)$, in which $n_i{K}_2$ is a matching of size $n_i$. Using the Gallai-Edmonds Theorem, we characterized all the critical graphs for $r(n_1{K}_2,n_2{K}_2,\dots ,n_c{K}_2)$, implying a new proof for this Ramsey number.