2016/01/08 by Rong Chen, Chen, Rong, Geoff Whittle +1
Computer Science · Engineering · #Advanced Graph Theory Research #Combinatorics (math.CO) #Computational Geometry and Mesh Generation #FOS: Mathematics #graph theory and CDMA systems
paper · pdf · doi:10.48550/arxiv.1601.01791
openalex publication_date 2016/01/08 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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, arXiv:1512.03005v1).