𝔖 Bobbio Scriptorium
✦   LIBER   ✦

A minor-monotone graph parameter based on oriented matroids

✍ Scribed by Jack Edmonds; Monique Laurent; Alexander Schrijver

Publisher
Elsevier Science
Year
1997
Tongue
English
Weight
573 KB
Volume
165-166
Category
Article
ISSN
0012-365X

No coin nor oath required. For personal study only.

✦ Synopsis

For an undirected graph G = (V,E) let i'(G) be the largest d for which there exists an oriented matroid M on V of corank d such that for each nonzero vector (x+,x-) of M, x+ is nonempty and induces a connected subgraph of G.

We show that I'(G) is monotone under taking minors and clique sums. Moreover, we show that L'(G) $ 3 if and only if G has no Kg-or Vs-minor; that is, if and only if G arises from planar graphs by taking clique sums and subgraphs.

In this paper, all graphs are assumed to be simple.) This graph parameter can be easily seen to be monotone under taking minors. That is, if G is a minor of H, then A(G) 6 i(H). So for each natural number d the class of graphs G with A(G) d d is closed under taking minors.

πŸ“œ SIMILAR VOLUMES

On a Minor-Monotone Graph Invariant
On a Minor-Monotone Graph Invariant
✍ H Vanderholst; M Laurent; A Schrijver πŸ“‚ Article πŸ“… 1995 πŸ› Elsevier Science 🌐 English βš– 558 KB
On vertex partitions and some minor-mono
On vertex partitions and some minor-monotone graph parameters
✍ D. GonΓ§alves πŸ“‚ Article πŸ“… 2010 πŸ› John Wiley and Sons 🌐 English βš– 107 KB

We study vertex partitions of graphs according to some minormonotone graph parameters. Ding et al. [J Combin Theory Ser B 79(2) (2000), 221-246] proved that some minor-monotone parameters are such that, any graph G with (G) β‰₯ 2 admits a vertex partition into two graphs with parameter at most (G)-1.

A lower bound on connectivities of matro
A lower bound on connectivities of matroid base graphs
✍ Guizhen Liu πŸ“‚ Article πŸ“… 1988 πŸ› Elsevier Science 🌐 English βš– 853 KB

The connectivity of a graph G and the corank of a matroid M are denoted by K(G) and p, respectively. X is shown that if a graph G is the base graph of a simple mat&d M, then K(G) L 2p and the lower bound of 2p izA best possible.