Forbidden subgraphs and matchings in graphs
by
Akira Saito
Nihon University, Japan

In this talk, we give an overview of the research on the relationship between forbidden subgraphs and the existence of a perfect matching, which was initiated by Mike Plummer and the speaker, and has been developed by a number of graph theorists.

Sumner (1976) proved that a connected K_{1, 3}-free graph of even order has a perfect matching. But why did he choose K_{1, 3}? First, we give an answer to this question : This is because if we forbid a connected graph H to force the existence of a perfect matching in a connected graph of even order, H must be K_{1, 3} or its induced subgraph.

This question and its answer lead us to further questions. For example:

(1) What happens if we restrict ourselves to graphs of higher connectivity? Sumner (1976) proved that for m ≥ 2, an m-connected K_{1, m+2}-free graph of even order has a perfect matching. This means that we can forbid a star larger than K_{1, 3} to force the existence of a perfect matching if we consider graphs of higher connectivity. But he still used a star. Why?

(2) What happens if we forbid two subgraphs instead of just one? Are there any pair of connected graphs H₁ and H₂ such that there exists a connected H_i-free graph of even order without a perfect matching for i=1, 2, but every connected H₁-free and H₂-free graph of even order has a perfect matching? What if we confine ourselves to graphs of higher connectivity? What if we forbid three or more graphs?

In this we talk, we give answers to most of the above questions. For a few open problems, we give a current situation of the research.

Recently, we began to study other matching-related properties and their relationships with forbidden subgraphs. These include perfect matchings including/excluding prescribed edges. Currently, we are working on forbidden subgraphs and the existence of a perfect matching excluding prescribed edges. In the latter part of the talk, we report the current status of this research.

Date received: May 5, 2008

Copyright © 2008 by the author(s). The author(s) of this document and the organizers of the conference have granted their consent to include this abstract in Atlas Conferences Inc. Document # cawn-70.