On characterizing the critical graphs for matching Ramsey numbers

Abstract Given simple graphs H 1 , H 2 , … , H c , the Ramsey number r ( H 1 , H 2 , … , 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 ∈ { 1 , 2 , … , c } . The critical graphs for r ( H 1 , H 2 , … , H c ) are edge-colored complete graphs on r ( H 1 , H 2 , … , H c ) − 1 vertices with c colors which contain no subgraphs in color i isomorphic to H i for any i ∈ { 1 , 2 , … , c } . For n 1 ≥ n 2 ≥ ⋯ ≥ n c ≥ 1 , Cockayne and Lorimer (1975) showed that r ( n 1 K 2 , n 2 K 2 , … , n c K 2 ) = n 1 + 1 + ∑ 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 , … , n c K 2 ) , implying a new proof for this Ramsey number.