A major line of research is discovering Ramsey-type theorems, which are results of the following form: given a graph parameter ρ, every graph G with sufficiently large ρ(G) contains a particular induced subgraph H with large ρ(H). The classical Ramsey's theorem deals with the case when the graph parameter under consideration is the number of vertices. There is also a Ramsey-type theorem regarding connected graphs, namely, every sufficiently large connected graph contains a large induced connected graph that is a complete graph, a large star, or a path. Given a graph G, the matching number and the induced matching number of G are the maximum size of a matching and an induced matching, respectively, of G. In this paper, we formulate Ramsey-type theorems for the matching number and the induced matching number regarding connected graphs. Along the way, we obtain a Ramsey-type theorem for the independence number regarding connected graphs as well.
Ilkyoo Choi was supported by Basic Science Research Program, through the National Research Foundation of Korea (NRF) funded by the Ministry of Education (NRF-2018R1D1A1B07043049), and also by Hankuk University of Foreign Studies Research Fund.Michitaka Furuya was supported by JSPS KAKENHI Grant Number JP18K13449.Ringi Kim was supported by the National Research Foundation of Korea (NRF) grant funded by the Korea government (MSIT) (NRF-2018R1C1B6003786).Boram Park was supported by the National Research Foundation of Korea (NRF) grant funded by the Korea government (MSIT) (NRF-2018R1C1B6003577).
