Recognizing graphic matroids

P. D. Seymour

doi:10.1007/BF02579179

Recognizing graphic matroids

P. D. Seymour

Research output: Contribution to journal › Article › peer-review

54 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 language	English (US)
Pages (from-to)	75-78
Number of pages	4
Journal	Combinatorica
Volume	1
Issue number	1
DOIs	https://doi.org/10.1007/BF02579179
State	Published - Mar 1981
Externally published	Yes

All Science Journal Classification (ASJC) codes

Discrete Mathematics and Combinatorics
Computational Mathematics

Keywords

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

Access to Document

10.1007/BF02579179

Cite this

@article{51f0c8f59d7b4aa8bfd1f1b8c568eaaf,

title = "Recognizing graphic matroids",

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.",

keywords = "AMS subject classification (1980): 05B35, 68C25",

author = "Seymour, {P. D.}",

year = "1981",

month = mar,

doi = "10.1007/BF02579179",

language = "English (US)",

volume = "1",

pages = "75--78",

journal = "Combinatorica",

issn = "0209-9683",

publisher = "Janos Bolyai Mathematical Society",

number = "1",

}

TY - JOUR

T1 - Recognizing graphic matroids

AU - Seymour, P. D.

PY - 1981/3

Y1 - 1981/3

N2 - 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.

AB - 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.

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

UR - http://www.scopus.com/inward/record.url?scp=51249186893&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=51249186893&partnerID=8YFLogxK

U2 - 10.1007/BF02579179

DO - 10.1007/BF02579179

M3 - Article

AN - SCOPUS:51249186893

SN - 0209-9683

VL - 1

SP - 75

EP - 78

JO - Combinatorica

JF - Combinatorica

IS - 1

ER -

Recognizing graphic matroids

Abstract

All Science Journal Classification (ASJC) codes

Keywords

Access to Document

Other files and links

Fingerprint

Cite this