𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Minor characterization of undirected branching greedoids—a short proof

✍ Scribed by Oskar Goecke; Rainer Schrader

Publisher
Elsevier Science
Year
1990
Tongue
English
Weight
433 KB
Volume
82
Category
Article
ISSN
0012-365X

No coin nor oath required. For personal study only.

✦ Synopsis

In 1959 Tutte gave a minor characterization of graphic matroids. Within the framework of greedoids, a natural analogue of the cycle matroid in graphs is the branching greedoid. Schmidt has shown that, similar to Tutte's result, branching greedoids can be characterized by forbidden minors. Here we give a simpler proof of this theorem.

(9/F)\A.

📜 SIMILAR VOLUMES

On Paths of Greedoids and a Minor Charac
On Paths of Greedoids and a Minor Characterization
✍ Erhard Hexel 📂 Article 📅 1994 🏛 Elsevier Science 🌐 English ⚖ 156 KB

Let \(p_{n}\) denote the maximum number of paths a greedoid over \(n\) elements can have. As an upper bound, we of course have \(p_{n}<2^{n}\). We establish a lower bound for the maximum: \(1.6 \cdot 3^{n / 3}<p_{n}\). In the class of simple greedoids (those greedoids on \(n\) elements having exactl

A Short Proof of Guenin's Characterizati
A Short Proof of Guenin's Characterization of Weakly Bipartite Graphs
✍ Alexander Schrijver 📂 Article 📅 2002 🏛 Elsevier Science 🌐 English ⚖ 79 KB

We give a proof of Guenin's theorem characterizing weakly bipartite graphs by not having an odd-K 5 minor. The proof curtails the technical and case-checking parts of Guenin's original proof.