θ-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≤ 3n/2+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.