Some excluded-minor theorems for a class of polymatroids

DOI10.1007/BF01303518MaRDI QIDQ1316652zbMATH OpenOpenAlexFDO

Authors James Oxley, Geoff Whittle

Publication date 10 August 1994

Published in Combinatorica (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/bf01303518

zbMATH Keywords

excluded minorsgraph classespolymatroidrepresentation of polymatroidsset functionset systems

Mathematics Subject Classification ID

Combinatorial aspects of matroids and geometric lattices (05B35) Hypergraphs (05C65) Structural characterization of families of graphs (05C75)

Review text

A polymatroid function \(h: 2^ S\rightarrow{\mathbf Z}\) is Boolean if it can be represented in the form \(h(A)=|\bigcup_{a\in A}\phi(A)|\) for a set function \(\phi: S\rightarrow 2^ V\). In this paper the authors develop criteria that help to identify excluded minors for classes of Boolean polymatroids. In particular, they show that there are infinitely many excluded minors (non-Boolean polymatroids such that every proper minor is Boolean), while for Boolean \(k\)-polymatroids (i.e., \(|\phi(A)|\leq k\) for all \(a\in S\)) all excluded minors have size at most \(k+2\), and thus their set of excluded minors is finite. The complete list of eight excluded minors is determined for the class of Boolean 2-polymatroids, which correspond to graphs.

Recommendations

• On an excluded-minor class of matroids
• On excluded minors for classes of graphical matroids
• Excluded minors for Boolean polymatroids
• A characterization of certain excluded-minor classes of matroids
• An excluded-minor problem in matroids
• Excluded minors for matroids satisfying Kinser's inequalities
• The excluded minors for near-regular matroids
• The excluded minors for lattice path polymatroids
• The Excluded Minors for Three Classes of 2-Polymatroids Having Special Types of Natural Matroids
• Excluded minors for the class of split matroids

Cites work

• A geometric theory of hypergraph colouring
• Decomposition of submodular functions
• scientific article; zbMATH DE number 3468904 (Why is no real title available?)
• THE CRITICAL PROBLEM FOR POLYMATROIDS
• The Redei function of a relation

Cited in

(10)

• Deletion-contraction to form a polymatroid
• The excluded minors for lattice path polymatroids
• Decomposable polymatroids and connections with graph coloring
• The excluded minors for near-regular matroids
• Unavoidable minors for connected 2-polymatroids
• Recognizing Polymatroids Associated with Hypergraphs
• scientific article; zbMATH DE number 7352034 (Why is no real title available?)
• Excluded Forest Minors and the Erdős–Pósa Property
• Excluded minors for Boolean polymatroids
• The Excluded Minors for Three Classes of 2-Polymatroids Having Special Types of Natural Matroids

This page was built for publication: Some excluded-minor theorems for a class of polymatroids

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1316652)