Pairs of disjoint matchings

Faculty Member

Anush Tserunyan

For a finite graph G, let nu(G) be the maximum size of a matching in G and let phi(G) denote the maximum size of a union of a pair of disjoint matchings. Finally, let mu(G) denote the maximum size of a matching that appears in those pairs that achieve phi(G). Of course, mu(G) <= nu(G), and this project is to characterize the class of graphs for which these two parameters are equal. For example, chains are in this class, but what other graphs make it to this class?

Team Meetings


Project Difficulty


Undergrad Prerequisites

Math 347 or another proof-based course. Some experience with combinatorics, graphs, and algorithms would be helpful, but not required.