Matroids, delta-matroids and embedded graphs. / Chun, Carolyn; Moffatt, Iain; Noble, Steven; Rueckriemen, Ralf.

In: Journal of Combinatorial Theory, Series A, Vol. 167, 10.2019, p. 7-59.

Research output: Contribution to journalArticle

E-pub ahead of print

Documents

  • Accepted Manuscript

    Accepted author manuscript, 640 KB, PDF-document

    Embargo ends: 12/04/20

    Licence: CC BY-NC-ND Show licence

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 illus- trate 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.
Original languageEnglish
Pages (from-to)7-59
Number of pages53
JournalJournal of Combinatorial Theory, Series A
Volume167
Early online date12 Apr 2019
DOIs
StateE-pub ahead of print - 12 Apr 2019
This open access research output is licenced under a Creative Commons Attribution-NonCommercial-NoDerivs 3.0 Unported License.

ID: 33372594