On chains of 3-connected matroids

DOI10.1016/0166-218X(86)90039-9MaRDI QIDQ1086571zbMATH OpenOpenAlexFDO

Authors Robert E. Bixby, Collette R. Coullard

Publication date 1986

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0166-218x(86)90039-9

zbMATH Keywords

3-connected matroids3-connected minorchain

Mathematics Subject Classification ID

Combinatorial aspects of matroids and geometric lattices (05B35)

Review text

A sequence \(N_ 0,N_ 1,...,N_ m\) of 3-connected matroids is called a chain from \(N_ 0\) to \(N_ m\) if each of \(N_ 0,N_ 1,...,N_{m-1}\) is a minor of its successor. The gap of such a chain is \(\max \{| E(N_ i)| -| E(N_{i-1})|:\) \(i=1,2,...,m\}\). A result of \textit{K. Truemper} [Eur. J. Comb. 5, 377-394 (1984; Zbl 0561.05018)] shows that if N is a 3-connected minor of a 3-connected matroid M, then there is always a chain from N to M of gap at most three and this paper proves several extensions of Truemper's result. In particular, the authors show that the chain of gap at most three from N to M may be chosen so that each term is obtained from its successor by a single-element contraction followed by a simplification, or by a single-element deletion followed by a cosimplification. In addition, they prove that, provided N has no circuits or cocircuits of size less than four, one may find a chain whose gap is at most two.

Recommendations

• On minor-minimally 3-connected binary matroids
• A chain theorem for matroids
• \(N\)-critical matroids
• Triads and triangles in 3-connected matroids
• On 3-connected minors of 3-connected matroids and graphs

Cites work

• A characterization of 3-connected graphs containing a given graph
• A Combinatorial Decomposition Theory
• A simple theorem on 3-connectivity
• Connectivity in Matroids
• Decomposition of regular matroids
• scientific article; zbMATH DE number 3534506 (Why is no real title available?)
• scientific article; zbMATH DE number 3598496 (Why is no real title available?)
• Menger's theorem for matroids
• On matroid connectivity
• Partial matroid representations
• The Minimum Number of Edges and Vertices in a Graph with Edge Connectivity n and m n‐Bonds

Cited in

(10)

• Finding a small 3-connected minor maintaining a fixed minor and a fixed element
• On fixing elements in matroid minors
• Extensions of Tutte's wheels-and-whirls theorem
• On the minor-minimal 3-connected matroids having a fixed minor.
• On the structure of 3-connected matroids and graphs
• Improving a chain theorem for triangle-free 3-connected matroids
• On triangle-free 3-connected matroids
• \(N\)-critical matroids
• scientific article; zbMATH DE number 3896952 (Why is no real title available?)
• On chains of matroids in the weak order

This page was built for publication: On chains of 3-connected matroids

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