A minor-monotone graph parameter based on oriented matroids
| Authors |
|
|---|---|
| Publication date | 1997 |
| Journal | Discrete mathematics |
| Volume | Issue number | 165-166 |
| Pages (from-to) | 219-226 |
| Organisations |
|
| Abstract |
For an undirected graph G = (V,E) let λ ′(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 λ′(G) is monotone under taking minors and clique sums. Moreover, we show that λ′(G) ≤ 3 if and only if G has no K5- or V8-minor; that is, if and only if G arises from planar graphs by taking clique sums and subgraphs. |
| Document type | Article |
| Language | English |
| Published at | https://doi.org/10.1016/S0012-365X(96)00172-0 |
| Downloads |
A minor-monotone graph parameter based on oriented matroids
(Final published version)
|
| Permalink to this page | |