Recognizing graphic matroids

Research output: Contribution to journalArticle

47 Scopus citations

Abstract

There is no polynomially bounded algorithm to test if a matroid (presented by an "independence oracle") is binary. However, there is one to test graphicness. Finding this extends work of previous authors, who have given algorithms to test binary matroids for graphicness. Our main tool is a new result that if M′ is the polygon matroid of a graph G, and M is a different matroid on E(G) with the same rank, then there is a vertex of G whose star is not a cocircuit of M.

Original languageEnglish (US)
Pages (from-to)75-78
Number of pages4
JournalCombinatorica
Volume1
Issue number1
DOIs
StatePublished - Mar 1 1981
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Discrete Mathematics and Combinatorics
  • Computational Mathematics

Keywords

  • AMS subject classification (1980): 05B35, 68C25

Fingerprint Dive into the research topics of 'Recognizing graphic matroids'. Together they form a unique fingerprint.

  • Cite this