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.
scientific article; zbMATH DE number 1019097