A minor-monotone graph parameter based on oriented matroids
type: Item
instance of: scholarly article
title: A minor-monotone graph parameter based on oriented matroids
zbMATH Open document ID: 0873.05030
DOI: 10.1016/S0012-365X(96)00172-0
author: Jack Edmonds
author: Monique Laurent
author: Alexander Schrijver
published in: Discrete Mathematics
publication date: 1997-06-10T00:00:00Z
review text: For an undirected graph \(G=(V,E)\) let \(\lambda'(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\). In the paper, it is shown that \(\lambda'(G)\) is monotone under taking minors and clique sums. Moreover, the authors prove that \(\lambda'(G)\leq 3\) if and only if \(G\) has no \(K_5\)- or \(V_8\)-minor; that is, if and only if \(G\) arises from planar graphs by taking clique sums and subgraphs.
reviewed by: Mirela Ştefănescu
Mathematics Subject Classification ID: 05B35
Mathematics Subject Classification ID: 05C10
zbMATH DE Number: 1019097
zbMATH Keywords: oriented matroid
zbMATH Keywords: minors
zbMATH Keywords: clique sums
zbMATH Keywords: planar graphs
MaRDI profile type: Publication
Wikidata QID: Q101132578
cites work: Q4003411
cites work: Sur un nouvel invariant des graphes et un critère de planarité. (On a new graph invariant and a planarity criterion)
cites work: Q4273839
cites work: Graph minors. XX: Wagner's conjecture
cites work: On a minor-monotone graph invariant
cites work: Über eine Eigenschaft der ebenen Komplexe
DBLP publication ID: journals/dm/EdmondsLS97
description: scientific article; zbMATH DE number 1019097