Even circuits in oriented matroids
OPEN ACCESS
Author / Producer
Date
2022
Publication Type
Journal Article
ETH Bibliography
yes
Citations
Altmetric
OPEN ACCESS
Data
Rights / License
Abstract
In this paper we generalise the even directed cycle problem, which asks whether a given digraph contains a directed cycle of even length, to orientations of regular matroids. We define non-even oriented matroids generalising non-even digraphs, which played a central role in resolving the computational complexity of the even dicycle problem. Then we show that the problem of detecting an even directed circuit in a regular matroid is polynomially equivalent to the recognition of non-even oriented matroids. Our main result is a precise characterisation of the class of non-even oriented cographic matroids in terms of forbidden minors, which complements an existing characterisation of non-even oriented graphic matroids by Seymour and Thomassen.
Permanent link
Publication status
published
External links
Editor
Book title
Journal / series
Volume
2 (1)
Pages / Article No.
3
Publisher
eScholarship
Event
Edition / version
Methods
Software
Geographic location
Date collected
Date created
Subject
Oriented matroids; circuits; even cycle problem; regular matroids
Organisational unit
03672 - Steger, Angelika (emeritus) / Steger, Angelika (emeritus)