Predavatelj: Michal Kotrbčík (Masaryk University, Brno, Češka)
A matching in a graph G is a set of independent edges of G, that is, a
set in which no two edges have a common endpoint. The area of matching
extensions is concerned with adding edges to matchings to obtain larger
matchings (with specified properties). Slightly more formally, consider
the following problem: If M is any matching with property A, is there
always a set of edges N such that Mcup N is a matching with property B?
A particular example of arising notion is the class of matching-covered
graphs, graphs in which every edge belongs to a maximum matching.
set in which no two edges have a common endpoint. The area of matching
extensions is concerned with adding edges to matchings to obtain larger
matchings (with specified properties). Slightly more formally, consider
the following problem: If M is any matching with property A, is there
always a set of edges N such that Mcup N is a matching with property B?
A particular example of arising notion is the class of matching-covered
graphs, graphs in which every edge belongs to a maximum matching.
In this talk I will first give a brief overview of the landscape of
matching extensions, introducing some of the more interesting concepts
living there. In particular, I will mention Gallai-Edmonds structure
theorem which provides a description of all matchings in a graph. In the
second part of the talk I will present the state of the art in
characterising equimatchable graphs, that is, graphs in which each
matching can be extended to a maximum matching, and pose several open
problems.
