A major line of research is discovering Ramsey-type theorems, which are results of the following form: given a graph parameter $\rho$, every graph $G$ with sufficiently large $\rho(G)$ contains a ``well-structured'' induced subgraph $H$ with large $\rho(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. Given a graph $G$, the matching number and the induced matching number of $G$ is 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. This is joint work with Boram Park and Ringi Kim.

Speaker

Ilkyoo Choi, Hankuk University of Foreign Studies

Place

A312 Academic Building

Time