Abstract: For several problems in Matching Theory, one may restrict attention to matching covered graphs — i.e., connected graphs with the additional property that each edge belongs to some perfect matching. Two types of decompositions — ear decompositions and tight cut decompositions — play an important role in the study of these graphs.
Lov´asz (1983) proved that every nonbipartite matching covered graph admits an ear decomposition starting from a bi-subdivision of the complete graph K4, or from a bi-subdivision of the triangular prism C6. This gives rise to two natural problems: Which matching covered graphs are K4-based (i.e., admit an ear decomposition starting from a bi-subdivision of K4)? Likewise, which ones are C6-based?
In a joint work with U. S. R. Murty (https://onlinelibrary.wiley.com/doi/full/10.1002/jgt.21882), we solved the aforementioned problems for planar graphs. At a highlevel, our solution comprises two steps: (i) reduce each problem to the case of “bricks” (special nonbipartite matching covere graphs) by applying the tight cut decomposition, and (ii) solve each problem for the case of planar bricks.
I will discuss each of these problems, and our solutions for the planar case.