A minor-monotone graph parameter based on oriented matroids
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.
- Graph minors. XX: Wagner's conjecture
- scientific article; zbMATH DE number 53152 (Why is no real title available?)
- scientific article; zbMATH DE number 475583 (Why is no real title available?)
- On a minor-monotone graph invariant
- Sur un nouvel invariant des graphes et un critère de planarité. (On a new graph invariant and a planarity criterion)
- Über eine Eigenschaft der ebenen Komplexe
This page was built for publication: A minor-monotone graph parameter based on oriented matroids
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1356746)
