Oriented cobicircular matroids are GSP
Research output: Contribution to journal › Research article › Contributed › peer-review
Contributors
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
| Original language | English |
|---|---|
| Article number | 113686 |
| Journal | Discrete Mathematics |
| Volume | 347 |
| Issue number | 1 |
| Publication status | Published - Jan 2024 |
| Peer-reviewed | Yes |
| Externally published | Yes |
Keywords
ASJC Scopus subject areas
Keywords
- Bicircular matroids, Colourings, Flows, Matroids, Oriented matroids