تقرير
Oriented cobicircular matroids are $GSP$
| العنوان: | Oriented cobicircular matroids are $GSP$ |
|---|---|
| المؤلفون: | Guzmán-Pro, Santiago, Hochstättler, Winfried |
| المصدر: | Discrete Mathematics Volume 347, Issue 1, January 2024 |
| سنة النشر: | 2022 |
| المجموعة: | Mathematics |
| مصطلحات موضوعية: | Mathematics - Combinatorics, 05B35, 05C15 |
| الوصف: | 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 $\mathcal{O}$ is an $M(K_4)$-minor free oriented matroid, then $\mathcal{O}$ has a now-where $3$-coflow, i.e., it is $3$-colourable in the sense of Hochst\"attler-Ne\v{s}et\v{r}il. The class of generalized series parallel ($GSP$) oriented matroids is a class of $3$-colourable oriented matroids with no $M(K_4)$-minor. So far, the only technique towards proving that all orientations of a class $\mathcal{C}$ of $M(K_4)$-minor free matroids are $GSP$ (and thus $3$-colourable), has been to show that every matroid in $\mathcal{C}$ has a positive coline. Towards proving Hadwiger's conjecture for the class of gammoids, Goddyn, Hochst\"attler, and Neudauer conjectured that every gammoid has a positive coline. In this work we disprove this conjecture by exhibiting an infinite class of 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$. Comment: This work is an extension of our previous pre-print: arXiv:2203.12549 |
| نوع الوثيقة: | Working Paper |
| DOI: | 10.1016/j.disc.2023.113686 |
| URL الوصول: | http://arxiv.org/abs/2209.06591 |
| رقم الأكسشن: | edsarx.2209.06591 |
| قاعدة البيانات: | arXiv |
| DOI: | 10.1016/j.disc.2023.113686 |
|---|