Matching covered graphs with three removable classes

MaRDI QIDQ405203zbMATH OpenFDO

Authors Marcelo H. de Carvalho, C. H. C. Little

Publication date 4 September 2014

Published in The Electronic Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL http://www.combinatorics.org/ojs/index.php/eljc/article/view/v21i2p13

IPFS File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

zbMATH Keywords

matching covered graphsperfect matchings

Mathematics Subject Classification ID

Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Structural characterization of families of graphs (05C75)

Review text

Summary: The notion of removable classes arises in connection with ear decompositions of matching covered graphs introduced by \textit{L. Lovász} and \textit{M. D. Plummer} [Matching theory. Providence, RI: AMS Chelsea Publishing (2009; Zbl 1175.05002)]. The last (single or double) ear of an ear decomposition is defined as a removable class. Every matching covered graph not induced by a circuit has at least three removable classes. In this paper, we characterize matching covered graphs with precisely three removable classes and show, as a corollary, that every non-planar matching covered graph has at least four removable classes. Let \(G\) be a matching covered graph. A matching covered subgraph \(H\) of \(G\) is conformal if \(G-VH\) has a perfect matching. Given \(S \subseteq EG\), what is a minimal conformal subgraph of \(G\) that contains \(S\)? It is known that if \(|S|=2\) then it is induced by a circuit. As an application of the main result, we answer this question for \(|S|=3\).

Recommendations

• Ear decompositions of matching covered graphs
• Matching covered graphs
• On a conjecture of Lovász concerning bricks. I: The characteristic of a matching covered graph
• On two unsolved problems concerning matching covered graphs
• On generalizations of matching-covered graphs

Cites work

• A generalization of Little's theorem on Pfaffian orientations
• A theorem on connected graphs in which every edge belongs to a 1-factor
• Circuit decompositions of join-covered graphs
• Ear decompositions of matching covered graphs
• Ear-decompositions of matching-covered graphs
• Graph theory
• Graphs with independent perfect matchings
• Matching structure and the matching lattice
• Matching theory
• The perfect matching polytope and solid bricks

Cited in

(8)

• Bicritical graphs without removable edges
• \(K_4\)-free and \(\overline{C_6}\)-free planar matching covered graphs
• Even cycles and perfect matchings in claw-free plane graphs
• Removable edges in Halin graphs
• Removable and forced subgraphs of graphs
• Independent removable edges in cubic bricks
• Three ways to cover a graph
• A lower bound on the number of removable ears of 1-extendable graphs

This page was built for publication: Matching covered graphs with three removable classes

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