On Two Unsolved Problems Concerning Matching Covered Graphs
Cláudio Leonardo Lucchesi, Marcelo Henriques de Carvalho, Nishad Kothari, U. S. R. Murty · SIAM Journal on Discrete Mathematics · 2018
A cut $C:=\partial (X)$ of a matching covered graph $G$ is a separating cut if both its $C$-contractions $G/X$ and $G/\overline{X}$ are also matching covered. A brick is solid if it is free of nontrivial separating cuts. Three of us (Carvalho, Lucchesi, and Murty [ J. Combin. Theory Ser. B, 92 (2004), pp. 319--324]) showed that the perfect matching polytope of a brick may be described without recourse to odd set constraints if and only if it is solid, and we proved (Carvalho, Lucchesi, and Murty [ Discrete Math., 306 (2006), pp. 2383--2410]) that the only simple planar solid bricks are the odd wheels. The problem of characterizing nonplanar solid bricks remains unsolved. A bisubdivision of a graph $J$ is a graph obtained from $J$ by replacing each of its edges by paths of odd length. A matching covered graph $J$ is a conformal minor of a matching covered graph $G$ if there exists a bisubdivision $H$ of $J$ which is a subgraph of $G$ such that $G-V(H)$ has a perfect matching. For a fixed matching covered graph $J$, a matching covered graph $G$ is $J$-based if $J$ is a conformal minor of $G$ and, otherwise, $G$ is $J$-free. A basic result due to Lovász [ Combinatorica, 3 (1983), pp. 105--117] states that every nonbipartite matching covered graph is either $K_4$-based or is $\overline{C_6}$-based or both, where $\overline{C_6}$ is the triangular prism. Two of us (Kothari and Murty [ J. Graph Theory, 82 (2016), pp. 5--32]) showed that, for any cubic brick $J$, a matching covered graph $G$ is $J$-free if and only if each of its bricks is $J$-free. We also found characterizations of planar bricks which are $K_4$-free and those which are $\overline{C_6}$-free. Each of these problems remains unsolved in the nonplanar case. In this paper we show that the seemingly unrelated problems of characterizing nonplanar solid bricks on the one hand, and on the other of characterizing nonplanar $\overline{C_6}$-free bricks, are essentially the same. We do this by establishing that a simple nonplanar brick, other than the Petersen graph, is solid if and only if it is $\overline{C_6}$-free. In order to prove this, we first show that any nonsolid brick has one of the four graphs $\overline{C_6}$, the bicorn, the tricorn, and the Petersen graph as a conformal minor. Then, using a powerful theorem due to Norine and Thomas [ J. Combin. Theory Ser. B, 97 (2007), pp. 769--817], we show that the bicorn, the tricorn, and the Petersen graph are dead-ends in the sense that any simple nonplanar nonsolid brick which contains any one of these three graphs as a proper conformal minor also contains $\overline{C_6}$ as a conformal minor.