# Quasi-graphic matroids

@article{Geelen2018QuasigraphicM, title={Quasi-graphic matroids}, author={James F. Geelen and Bert Gerards and Geoff Whittle}, journal={J. Graph Theory}, year={2018}, volume={87}, pages={253-264} }

htmlabstractFrame matroids and lifted-graphic matroids are two interesting generalizations of graphic matroids. Here we introduce a new generalization, quasi-graphic matroids, that unifies these two existing classes. Unlike frame matroids and lifted-graphic matroids, it is easy to certify that a matroid is quasi-graphic. The main result of the paper is that every 3-connected representable quasi-graphic matroid is either a lifted-graphic matroid or a rame matroid.

#### Topics from this paper

#### 12 Citations

On excluded minors for classes of graphical matroids

- Mathematics, Computer Science
- Discret. Math.
- 2018

It is shown that M has only a finite number of excluded minors of rank r, which generalises both the classes of frame and lifted-graphic matroids. Expand

The $9$-connected Excluded Minors for the Class of Quasi-graphic Matroids

- Mathematics
- 2021

The class of quasi-graphic matroids, recently introduced by Geelen, Gerards, and Whittle, is minor closed and contains both the class of lifted-graphic matroids and the class of frame matroids, each… Expand

On Recognizing Frame and Lifted-Graphic Matroids

- Mathematics, Computer Science
- J. Graph Theory
- 2018

We prove that there is no polynomial $p(\cdot)$ 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… Expand

Describing quasi-graphic matroids

- Mathematics, Computer Science
- Eur. J. Comb.
- 2020

The class of quasi-graphic matroids recently introduced by Geelen, Gerards, and Whittle generalises each of the classes of frame matroids and lifted-graphic matroids introduced earlier by Zaslavsky.… Expand

Obstructions for Bounded Branch-depth in Matroids

- Mathematics
- 2020

DeVos, Kwon, and Oum introduced the concept of branch-depth of matroids as a natural analogue of tree-depth of graphs. They conjectured that a matroid of sufficiently large branch-depth contains the… Expand

Infinitely many excluded minors for frame matroids and for lifted-graphic matroids

- Computer Science, Mathematics
- J. Comb. Theory, Ser. B
- 2018

Abstract We present infinite sequences of excluded minors for both the class of lifted-graphic matroids and the class of frame matroids.

There are only a finite number of excluded minors for the class of bicircular matroids

- Mathematics
- 2021

We show that the class of bicircular matroids has only a finite number of excluded minors. Key tools used in our proof include representations of matroids by biased graphs and the recently introduced… Expand

Projective planarity of matroids of 3-nets and biased graphs

- Computer Science
- Australas. J Comb.
- 2020

Criteria for embeddability of biased-graphic matroids in Desarguesian projective spaces is established, that is, embeddable in an arbitrary projective plane that is not necessarily Desargue'sian. Expand

Matrix representations of frame and lifted-graphic matroids correspond to gain functions

- Mathematics
- 2016

Let $M$ be a 3-connected matroid and let $\mathbb F$ be a field. Let $A$ be a matrix over $\mathbb F$ representing $M$ and let $(G,\mathcal B)$ be a biased graph representing $M$. We characterize the… Expand

The graphs that have antivoltages using groups of small order

- Computer Science, Mathematics
- Discret. Math.
- 2019

These characterizations yield polynomial-time recognition algorithms for such graphs and also determine the list of minor-minimal graphs that have no Γ -antivoltage. Expand

#### References

SHOWING 1-9 OF 9 REFERENCES

Frame Matroids and Biased Graphs

- Computer Science, Mathematics
- Eur. J. Comb.
- 1994

It is proved that certain matroids, called bias matroIDS, of biased graphs are identical to the finitary frame matrosids. Expand

On Recognizing Frame and Lifted-Graphic Matroids

- Mathematics, Computer Science
- J. Graph Theory
- 2018

We prove that there is no polynomial $p(\cdot)$ 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… Expand

Recognizing graphic matroids

- Mathematics
- 1981

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… Expand

Supersolvable Frame-matroid and Graphic-lift Lattices

- Computer Science, Mathematics
- Eur. J. Comb.
- 2001

This work characterize modular coatoms in and supersolvability of graphic lifts of finite rank and describes explicitly the frames that are supersolvable. Expand

Biased graphs. II. The three matroids

- Computer Science, Mathematics
- J. Comb. Theory, Ser. B
- 1991

It is proved that these circuits of G(Ω) are the balanced circles and the minimal edge sets of cyclomatic number two (not necessarily connected) containing no balanced circle, and it is established that G has an infinitary analog for infinite graphs generalizing Klee's infInitary bicircular matroid and the Bean-Higgs inf initary graphic matroid. Expand

Biased graphs. I. Bias, balance, and gains

- Computer Science, Mathematics
- J. Comb. Theory, Ser. B
- 1989

Here the properties of balance and also subgraphs and contractions of biased and gain graphs are studied and their matroids are studied. Expand

Matroid theory

- Computer Science
- 1992

The current status has been given for all the unsolved problems or conjectures that appear in Chapter 14 and the corrected text is given with the inserted words underlined. Expand

Biased graphs

- II. The three matroids, J Combin Theory Ser B 47
- 1989

Matroid Theory Oxford University Press

- New York, second edition
- 2011