Matroids, Delta-matroids and Embedded Graphs
arXiv:1403.0920
Abstract
Matroid theory is often thought of as a generalization of graph theory. In this paper we propose an analogous correspondence between embedded graphs and delta-matroids. We show that delta-matroids arise as the natural extension of graphic matroids to the setting of embedded graphs. We show that various basic ribbon graph operations and concepts have delta-matroid analogues, and illustrate how the connections between embedded graphs and delta-matroids can be exploited. Also, in direct analogy with the fact that The Tutte polynomial is matroidal, we show that several polynomials of embedded graphs from the literature, including the Las Vergnas, Bollabas-Riordan and Krushkal polynomials, are in fact delta-matroidal.
v2: We have split this paper into two. The later material of version 1 now appears in "On the interplay between embedded graphs and delta-matroids". Some new results have been added
References in corpus (5)
Cited by in corpus (14)
- On the interplay between embedded graphs and delta-matroids
- On a conjecture of Gross, Mansour and Tucker
- Handle slides for delta-matroids
- Tutte's dichromate for signed graphs
- A convolution formula for Tutte polynomials of arithmetic matroids and other combinatorial structures
- Delta-matroids as subsystems of sequences of Higgs lifts
- Hopf algebras and Tutte polynomials
- How many delta-matroids are there?
- Answering Two OPAC Problems Involving Banff Quivers
- Inductive tools for connected ribbon graphs, delta-matroids and multimatroids
- The Las Vergnas Polynomial for embedded graphs
- Sorting by Reversals and the Theory of 4-Regular Graphs
- The structure of delta-matroids with width one twists
- The excluded 3-minors for vf-safe delta-matroids