Oriented cobicircular matroids are GSP

Publikation: Beitrag in FachzeitschriftForschungsartikelBeigetragenBegutachtung

Beitragende

  • Santiago Guzmán-Pro - , FernUniversität in Hagen (Autor:in)
  • Winfried Hochstättler - , FernUniversität in Hagen (Autor:in)

Abstract

Colourings and flows are well-known dual notions in graph theory. In turn, the definition of flows in graphs naturally extends to flows in oriented matroids. So, the colour-flow duality gives a generalization of Hadwiger's conjecture about graph colourings, to a conjecture about coflows of oriented matroids. The first non-trivial case of Hadwiger's conjecture for oriented matroids reads as follows. If O is an M(K4)-minor free oriented matroid, then O has a nowhere-zero 3-coflow, i.e., it is 3-colourable in the sense of Hochstättler-Nešetřil. The class of generalized series parallel (GSP) oriented matroids is a class of 3-colourable oriented matroids with no M(K4)-minor. So far, the only technique towards proving that all orientations of a class C of M(K4)-minor free matroids are GSP (and thus 3-colourable), has been to show that every matroid in C has a positive coline. Towards proving Hadwiger's conjecture for the class of gammoids, Goddyn, Hochstättler, and Neudauer conjectured that every gammoid has a positive coline. In this work we disprove this conjecture by showing that there are infinitely many strict gammoids that do not have positive colines. We conclude by proposing a simpler technique for showing that certain oriented matroids are GSP. In particular, we recover that oriented lattice path matroids are GSP, and we show that oriented cobicircular matroids are GSP.

Details

OriginalspracheEnglisch
Aufsatznummer113686
FachzeitschriftDiscrete Mathematics
Jahrgang347
Ausgabenummer1
PublikationsstatusVeröffentlicht - Jan. 2024
Peer-Review-StatusJa
Extern publiziertJa

Schlagworte

Schlagwörter

  • Bicircular matroids, Colourings, Flows, Matroids, Oriented matroids