Premium
On Recognizing Frame and Lifted‐Graphic Matroids
Author(s) -
Chen Rong,
Whittle Geoff
Publication year - 2018
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.22141
Subject(s) - matroid , graphic matroid , combinatorics , mathematics , property (philosophy) , rank (graph theory) , graph , frame (networking) , discrete mathematics , computer science , telecommunications , philosophy , epistemology
We prove that there is no polynomial p ( · ) with the property that a matroid M can be determined to be either a lifted‐graphic or frame matroid using at most p ( | M | ) rank evaluations. This resolves two conjectures of Geelen, Gerards, and Whittle (Quasi‐graphic matroids, to appear in J. Graph Theory).