Skip to main content
eScholarship
Open Access Publications from the University of California

Combinatorial Theory

Combinatorial Theory banner

Even circuits in oriented matroids

Published Web Location

https://doi.org/10.5070/C62156875Creative Commons 'BY' version 4.0 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.

Mathematics Subject Classifications: 05B35, 05C20, 05C70, 05C75, 05C83, 05C85, 52C40

Main Content
For improved accessibility of PDF content, download the file to your device.
Current View