{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,11,16]],"date-time":"2026-11-16T22:49:03Z","timestamp":1794869343578,"version":"4.9.1"},"reference-count":22,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"2","funder":[{"DOI":"10.13039\/501100002322","name":"Coordena\u00e7\u00e3o de Aperfei\u00e7oamento de Pessoal de N\u00edvel Superior","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100002322","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100005672","name":"Funda\u00e7\u00e3o de Apoio ao Desenvolvimento do Ensino, Ci\u00eancia e Tecnologia do Estado de Mato Grosso do Sul","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100005672","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100003593","name":"Conselho Nacional de Desenvolvimento Cient\u00edfico e Tecnol\u00f3gico","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100003593","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Discrete Math."],"published-print":{"date-parts":[[2018,1]]},"abstract":"<jats:p>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\u00e1sz [ 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.<\/jats:p>","DOI":"10.1137\/17m1138704","type":"journal-article","created":{"date-parts":[[2018,6,28]],"date-time":"2018-06-28T11:39:57Z","timestamp":1530185997000},"page":"1478-1504","source":"Crossref","is-referenced-by-count":14,"title":["On Two Unsolved Problems Concerning Matching Covered Graphs"],"prefix":"10.1137","volume":"32","author":[{"given":"Cl\u00e1udio L.","family":"Lucchesi","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Marcelo H.","family":"de Carvalho","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Nishad","family":"Kothari","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"U. S. R.","family":"Murty","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2018,6,28]]},"reference":[{"key":"atypb1","doi-asserted-by":"crossref","unstructured":"J. A. Bondy and U. S. R. Murty,\n                      Graph Theory\n                      , Springer, New York, 2008.","DOI":"10.1007\/978-1-84628-970-5"},{"key":"atypb2","unstructured":"C. N. Campos and C. L. Lucchesi,\n                      On the relation between the Petersen graph and the characteristic of separating cuts in matching covered graphs\n                      , Technical report 22, Institute of Computing, University of Campinas, Brazil, 2000."},{"key":"atypb3","doi-asserted-by":"publisher","DOI":"10.1007\/s004930050051"},{"key":"atypb4","doi-asserted-by":"crossref","first-page":"94","DOI":"10.1006\/jctb.2001.2091","volume":"85","author":"Carvalho M. H.","year":"2002","journal-title":"J. Combin. Theory Ser. B"},{"key":"atypb5","doi-asserted-by":"publisher","DOI":"10.1006\/jctb.2001.2092"},{"key":"atypb6","doi-asserted-by":"publisher","DOI":"10.1016\/j.jctb.2004.08.003"},{"key":"atypb7","doi-asserted-by":"publisher","DOI":"10.1002\/jgt.20036"},{"key":"atypb8","doi-asserted-by":"publisher","DOI":"10.1016\/j.disc.2005.12.032"},{"key":"atypb9","unstructured":"M. H. Carvalho, C. L. Lucchesi, and U. S. R. Murty,\n                      Generating simple bricks and braces\n                      , Technical report IC-08-16, Institute of Computing, University of Campinas, 2008."},{"key":"atypb10","doi-asserted-by":"publisher","DOI":"10.1016\/j.jctb.2012.07.004"},{"key":"atypb11","doi-asserted-by":"publisher","DOI":"10.1007\/BF02579233"},{"key":"atypb12","doi-asserted-by":"publisher","DOI":"10.1016\/j.jctb.2012.11.004"},{"key":"atypb13","doi-asserted-by":"publisher","DOI":"10.1002\/jgt.21882"},{"key":"atypb14","doi-asserted-by":"publisher","DOI":"10.1007\/BF02579346"},{"key":"atypb15","doi-asserted-by":"publisher","DOI":"10.1016\/0095-8956(87)90021-9"},{"key":"atypb16","unstructured":"L. Lova\u0301sz and M. D. Plummer,\n                      Matching Theory\n                      , Ann. Discrete Math. 29, Elsevier Science, New York, 1986."},{"key":"atypb17","doi-asserted-by":"publisher","DOI":"10.1002\/jgt.1029"},{"key":"atypb18","doi-asserted-by":"publisher","DOI":"10.1016\/j.jctb.2007.01.002"},{"key":"atypb19","doi-asserted-by":"publisher","DOI":"10.1007\/BF02392606"},{"key":"atypb20","unstructured":"B. A. Reed and Y. Wakabayashi,\n                      A characterization of solid bricks\n                      , personal communication, 2003."},{"key":"atypb21","doi-asserted-by":"publisher","DOI":"10.1112\/jlms\/s1-22.2.107"},{"key":"atypb22","doi-asserted-by":"publisher","DOI":"10.2307\/2371127"}],"container-title":["SIAM Journal on Discrete Mathematics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/17M1138704","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T13:06:31Z","timestamp":1787317591000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/17M1138704"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,1]]},"references-count":22,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2018,1]]}},"alternative-id":["10.1137\/17M1138704"],"URL":"https:\/\/doi.org\/10.1137\/17m1138704","relation":{},"ISSN":["0895-4801","1095-7146"],"issn-type":[{"value":"0895-4801","type":"print"},{"value":"1095-7146","type":"electronic"}],"subject":[],"published":{"date-parts":[[2018,1]]}}}