Back to Search Start Over

Deletion–contraction to form a polymatroid

Authors :
Deborah Chun
Source :
Discrete Mathematics. (8):2592-2595
Publisher :
Elsevier B.V.

Abstract

Let M be a matroid with rank function r, and let e@?E(M). The deletion-contraction polymatroid with rank function f=r"M"@?"e+r"M"/"e will be denoted P"e(M). Notice that P"e(M) is uniquely determined by M and e. Similarly, a deletion-contraction polymatroid determines M, unless e is a loop or co-loop. This paper will characterize all polymatroids of this deletion-contraction form by giving the set of excluded minors. Vertigan conjectured that the class of GF(q)-representable deletion-contraction polymatroids is well-quasi-ordered. From this attractive conjecture, both Rota's Conjecture and the WQO Conjecture for GF(q)-representable matroids would follow.

Details

Language :
English
ISSN :
0012365X
Issue :
8
Database :
OpenAIRE
Journal :
Discrete Mathematics
Accession number :
edsair.doi.dedup.....38e2b106b3deb5a4a2368520dfeda81f
Full Text :
https://doi.org/10.1016/j.disc.2008.04.036