-free matching covered graphs

A nontrivial connected graph is matching covered if each edge belongs to some perfect matching. For most problems pertaining to perfect matchings, one may restrict attention to matching covered graphs; thus, there is extensive literature on them. A cornerstone of this theory is an ear decomposition result due to Lov\'asz and Plummer. Their theorem is a fundamental problem-solving tool, and also yields interesting open problems; we discuss two such problems below, and we solve one of them. A subgraph H of a graph G is conformal if G-V (H) has a perfect matching. This notion is intrinsically related to the aforementioned ear decomposition theorem -- which implies that each matching covered graph (apart from K₂ and even cycles) contains a conformal bisubdivision of, or a conformal bisubdivision of K₄, possibly both. (Here, refers to the graph with two vertices joined by three edges. ) This immediately leads to two problems: characterize -free (likewise, K₄-free) matching covered graphs. A characterization of planar K₄-free matching covered graphs was obtained by Kothari and Murty J. Graph Theory, 82 (1), 2016; the nonplanar case is open. We provide a characterization of -free matching covered graphs that immediately implies a poly-time algorithm for the corresponding decision problem. Our characterization relies heavily on a seminal result due to Edmonds, Lov\'asz and Pulleyblank Combinatorica, 2, 1982 pertaining to the tight cut decomposition theory of matching covered graphs. As corollaries, we provide two upper bounds on the size of a -free graph, namely, m 2n-1 and m 3n2+b-1, where b denotes the number of bricks obtained in any tight cut decomposition of the graph; for each bound, we provide a characterization of the tight examples. The Petersen graph and K₄ play key roles in our results.