On two unsolved problems concerning matching covered graphs

DOI10.1137/17M1138704MaRDI QIDQ3174694zbMATH OpenOpenAlexFDO

Authors Marcelo H. de Carvalho, Nishad Kothari, U. S. R. Murty, Cláudio L. Lucchesi

Publication date 18 July 2018

Published in SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1705.09428

zbMATH Keywords

perfect matchingsmatching covered graphsconformal minorsprism-based graphssolid graphs

Mathematics Subject Classification ID

Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph minors (05C83)

Abstract: A cut $C:=partial(X)$ of a matching covered graph $G$ is a separating cut if both its $C$-contractions $G/X$ and $G/overlineX$ are also matching covered. A brick is solid if it is free of nontrivial separating cuts. In 2004, we (Carvalho, Lucchesi and Murty) 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. In 2006, we proved that the only simple planar solid bricks are the odd wheels. The problem of characterizing nonplanar solid bricks remains unsolved. A bi-subdivision 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 bi-subdivision $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'asz (1983) 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. In 2016, we (Kothari and Murty) 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 and 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.

Recommendations

• \(K_4\)-free and \(\overline{C_6}\)-free planar matching covered graphs
• On a conjecture of Lovász concerning bricks. I: The characteristic of a matching covered graph
• Generating bricks
• Matching covered graphs and subdivisions of \(K_ 4\) and \(\bar C_ 6\)
• Disjoint odd cycles in cubic solid bricks

Cites work

• 2-Isomorphic Graphs
• A generalization of Little's theorem on Pfaffian orientations
• A simpler proof for the two disjoint odd cycles theorem
• Brace generation
• Brick decompositions and the matching rank of graphs
• Ear decompositions of matching covered graphs
• Ear-decompositions of matching-covered graphs
• Generating bricks
• Graph theory
• Graphs with independent perfect matchings
• How to build a brick
• Matching structure and the matching lattice
• Matching theory
• On a conjecture of Lovász concerning bricks. I: The characteristic of a matching covered graph
• On a conjecture of Lovász concerning bricks. II: Bricks of finite characteristic
• The Factorization of Linear Graphs
• The perfect matching polytope and solid bricks
• \(K_4\)-free and \(\overline{C_6}\)-free planar matching covered graphs

Cited in

(18)

• scientific article; zbMATH DE number 5308553 (Why is no real title available?)
• Matching covered graphs with three removable classes
• On essentially 4-edge-connected cubic bricks
• On a conjecture of Lovász concerning bricks. I: The characteristic of a matching covered graph
• K₄-free planar minimal bricks with the maximum number of edges
• Minimal bricks with the maximum number of edges
• How to build a brick
• \(K_4\)-free and \(\overline{C_6}\)-free planar matching covered graphs
• On saturated non-covered graphs
• A generalization of Little's theorem on Pfaffian orientations
• The cubic vertices of solid minimal bricks
• On extremal nonsolid bricks
• Birkhoff-von Neumann graphs that are PM-compact
• Disjoint odd cycles in cubic solid bricks
• Equivalence classes in matching covered graphs
• Relations between global forcing number and maximum anti-forcing number of a graph
• Colouring non-even digraphs
• Claw-free solid bricks

This page was built for publication: On two unsolved problems concerning matching covered graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3174694)