论文标题
定向的同性矩形为$ GSP $
Oriented cobicircular matroids are $GSP$
论文作者
论文摘要
色素和流是图理论中众所周知的双重概念。反过来，图中流的定义自然延伸至定向的矩形中的流动。因此，颜色流二重性将Hadwiger关于图形色素的猜想概括为围绕定向矩阵的coflows的猜想。哈德威格（Hadwiger）针对定向的矩阵的猜想的第一个非平凡案例如下所示。如果$ \ MATHCAL {O} $是$ M（k_4）$ - 少量免费定向的Matroid，则$ \ Mathcal {o} $具有现在的$ 3 $ -coflow，即，它是$ 3 $ 3 $ -Colourable在Hochstättler-nešetmen的意义上。一类通用系列并行（$ GSP $）面向的Matroids是$ 3 $ - 颜色的定向的Matroids的类别，没有$ M（K_4）$ - 未成年人。到目前为止，唯一证明$ m（k_4）$的类$ \ mathcal {c} $的所有方向是 - 较小的免费矩阵是$ gsp $（因此$ 3 $ - 彩色）已经表明，每个矩阵都$ \ nathcal {c} $均具有阳性coline。旨在证明哈德威格对γ类，戈迪，霍奇斯特勒和纽多尔的猜想，猜想每个伽马体都有阳性的coline。在这项工作中，我们通过表现出一类无阳性coline的无限严格γ-通过表现出这种猜想。我们通过提出了一种更简单的技术来表明某些面向的矩阵为$ GSP $，从而结束了。特别是，我们恢复了定向的晶格路径Matroids为$ gsp $，我们表明定向的同型矩形为$ gsp $。
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ättler-Nešetř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ättler, 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$.
