Alladi Ramakrishnan Hall

Conformal Subgraphs, 5 Open problems

Nishad Kothari

University of Campinas, Brazil

A connected graph G, on two or more vertices, is matching covered if each edge belongs to
some perfect matching. A subgraph H of G is conformal if G - V (H) has a perfect matching.
For problems pertaining to perfect matchings of a graph G — such as those arising from
the perfect matching polytope PMP(G) — one may restrict attention to matching covered
graphs. Several of these problems may be stated in terms of conformal subgraphs of a graph.
I will discuss 5 such problems each of which pertains to characterizing a class of graphs. (By ‘characterize’, I mean: obtain an NP or a co - NP
characterization, and ideally, show that the corresponding decision problem is in P.)