#### 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.)

Done