\documentclass{elsarticle} \usepackage{amssymb,url,amsmath} \newcommand{\hide}[1]{} \newcommand{\R}{{\mathbb R}} \newcommand{\Z}{{\mathbb Z}} \newcommand{\Oscr}{{\mathcal O}} \newcommand{\D}{{\mathcal D}} \newcommand{\F}{{\mathcal F}} %\newcommand{\nullsp}{{\rm nullsp}} %\newcommand{\ar}{{\rm arng}} %\newcommand{\s}{\scriptscriptstyle} %\newcommand{\deltaplus }{\delta^{\mbox{\raisebox{1pt}{$\s +$}}}\!} %\newcommand{\deltaminus}{\delta^{\mbox{\raisebox{1pt}{$\s -$}}}\!} \newtheorem{lemma}{\sc Lemma}% Sectionless Paper \newtheorem{theorem}[lemma]{\sc Theorem}% \newtheorem{proposition}[lemma]{\sc Proposition}% \newtheorem{corollary}[lemma]{\sc Corollary}% \newtheorem{claim}[lemma]{\sc Claim}% \newtheorem{conjecture}[lemma]{\sc Conjecture}% \newdefinition{remark}[lemma]{\sc Remark}% \newdefinition{definition}[lemma]{\sc Definition}{}% \newdefinition{question}[lemma]{\sc Question}{}% \newproof{proof}{Proof} \DeclareMathOperator{\lat}{lat} \DeclareMathOperator{\rk}{rank} \title{Bicircular Matroids are $3$-colorable} \author{Luis Goddyn} \ead{goddyn@sfu.ca} \address{Department of Mathematics, Simon Fraser University, 8888 University Drive, Burnaby BC V5A 1S6, Canada} \author{Winfried Hochst\"attler\corref{cor}} \ead{Winfried.Hochstaettler@FernUni-Hagen.de} \address{FernUniversit\"at in Hagen, Fakult\"at f\"ur Mathematik und Informatik, 58084 Hagen} \author{Nancy Ann Neudauer} \ead{nancy@pacificu.edu} \address{Nancy Ann Neudauer, Department of Mathematics and Computer Science, Pacific University, Forest Grove, OR 97116, USA } \cortext[cor1]{Corresponding author} \begin{document} \begin{abstract} Hugo Hadwiger proved that a graph that is not $3$-colorable must have a $K_4$-minor and conjectured that a graph that is not $k$-colorable must have a $K_{k+1}$-minor. By using the Hochst\"attler-Ne\v{s}et\v{r}il definition for the chromatic number of an oriented matroid, we formulate a generalized version of Hadwiger's conjecture that might hold for the class of oriented matroids. In particular, it is possible that every oriented matroid with no $M(K_4)$-minor is $3$-colorable. The fact that $K_4$-minor-free graphs are characterized as series-parallel networks leads to an easy proof that they are all $3$-colorable. We show how to extend this argument to a particular subclass of $M(K_4)$-minor-free oriented matroids. Specifically we generalize the notion of being series-parallel to oriented matroids, and then show that generalized series-parallel oriented matroids are $3$-colorable. To illustrate the method, we show that every orientation of a bicircular matroid is $3$-colorable. \end{abstract} \begin{keyword} colorings \sep series-parallel networks \sep matroids \sep oriented matroids \MSC 05C15 \sep 05B35 \sep 52C40 \end{keyword} \maketitle \section{Introduction} Hadwiger's conjecture \cite{Hadwiger}, that every graph that is not $k$-colorable must have a $K_{k+1}$-minor for $k\ge 1$, is ``one of the deepest unsolved problems in graph theory''\cite{Bollobás1980195}. While the first non-trivial case, when $k=3$, was proved by Hadwiger, he pointed out that Klaus Wagner had shown that $k=4$ is equivalent to the Four Color Theorem~\cite{wagner_ber_1937,appel_every_1976,robertson_four-colour_1997}. Robertson, Seymour and Thomas~\cite{RST} reduced the case $k=5$ to the Four Color Theorem. The conjecture remains open for $k\ge 6$. Recently, Goddyn and Hochst\"attler \cite{boergerband} observed that a proper generalization of Hadwiger's conjecture to regular matroids includes Tutte's $k$-flow conjectures for the cases $k \in \{4,5\}$ \cite{Tutte:dichromate,tutte2,tutte3}. Let $N$ be a matroid. We say that an oriented matroid $\mathcal{O}$ is \emph{$N$-free} if no minor of its underlying matroid $\underline{\mathcal O}$ is isomorphic to $N$. The extension of Hadwiger's conjecture in \cite{boergerband} asserts that every regular matroid $\Oscr$ that is $M(K_{k+1})$-free either is $k$-colorable or $k=4$ with $\underline{\Oscr}$ having the cographic matroid of the Petersen graph as a minor. The case $k=3$ remains the only non-trivial settled case. Hochst\"attler and Ne\v{s}et\v{r}il~\cite{honese} generalized the theory of nowhere-zero flows to the class of oriented matroids. Hochst\"attler and Nickel \cite{HoNi, honijct} extended this work and defined the chromatic number of an oriented matroid. They also showed that the chromatic number of a simple oriented matroid of rank $r$ is at most $r+1$, with equality if and only if the matroid is an orientation of $M(K_{r+1})$. This suggests that, in some sense, complete graphs are necessary to construct oriented matroids with large chromatic number. With their definition of chromatic number, Hadwiger's conjecture may, to our knowledge, hold true for the class of oriented matroids. \begin{question} Is every oriented matroid $\Oscr$ that is $M(K_{k+1})$-free either $k$-colorable or $k=4$ with $\underline{\Oscr}$ having the cographic matroid of the Petersen graph as a minor? \end{question} But, in this setting, even the case $k=3$ remains open: Are $M(K_4)$-free oriented matroids always $3$-colorable? Jim Geelen asked \cite{geelen:blog} for some characterization of matroids without an $M(K_4)$-minor. Here we define the class of generalized series-parallel oriented matroids (Definition~\ref{def:serpar}), which might provide some progress towards an answer to Geelen's question in the oriented case. While it is clear by definition that every generalized series-parallel matroid is $M(K_4)$-free, the converse statement, if true, would verify Hadwiger's conjecture for oriented matroids in the case $k=3$. We assume some familiarity with graph theory, matroid theory and oriented matroids; standard references are~\cite{west, oxley, BLSW}. The paper is organized as follows. In the next section we review the definition of the chromatic number of an oriented matroid. In Section~\ref{sec:series-parallel} we define generalized series-parallel oriented matroids and prove that they are $3$-colorable. In Section~\ref{sec:bicircular} we prove that every orientation of a bicircular matroid is generalized series-parallel, and is therefore $3$-colorable. We conclude with several open problems. \section{Nowhere-Zero Coflows in Oriented Matroids} A {\em tension} in a digraph $D=(V,A)$ is a map $f^\ast: A \to \R$ such that \[\sum_{a\in C^+}f^\ast (a) - \sum_{a\in C^-}f^\ast (a) = 0\] for every weak cycle $C$ in $D$, where $C^+$ and $C^-$ are the forward and backward arcs in $C$. We say that $f^\ast$ is a {\em nowhere-zero-$k$ tension (NZ-$k$ tension)} if $f^\ast: A \to \{\pm 1, \pm 2 \ldots, \pm (k-1)\}$. Let $c:V \to \{0,1,\ldots,k-1\}$ be a proper $k$-coloring of a connected graph $G=(V,E)$. Let $D=(V,A)$ be some orientation of $G$ and define $f^\ast:A \to \{\pm 1,\ldots, \pm (k-1)\}$ by $f^\ast((u,v))=c(v)-c(u)$. Then $f^\ast$ is a {NZ-$k$ tension}. The Kirchhoff Voltage Law implies every NZ-$k$ tension arises from a proper $k$-coloring this way (see for example \cite{Tutte:dichromate, GhouilaHouri}). The notion of a NZ-$k$ tension can be generalized to a regular matroid $M$ (essentially done by Arrowsmith and Jaeger \cite{arrowsmith_enumeration_1982}) by referring to the integer combinations of rows in a totally unimodular matrix representation of $M$. If one attempts to further generalize NZ-$k$ tensions to the class of oriented matroids one faces the difficulty that, for example, the four point line does not admit a nontrivial tension. The following definitions from \cite{honese, HoNi, honijct} avoid this difficulty. The {\em coflow lattice} of an oriented matroid $\Oscr$ on a finite set $E$, denoted as $\F_{\Oscr^\ast}$, is the integer lattice generated by the signed characteristic vectors of the signed cocircuits $\mathcal D$ of $\mathcal O$, where the {\em signed characteristic vector} of a signed cocircuit $D=(D^+,D^-)$ is defined by \[ \vec D(e):=\begin{cases} \phantom-1& \text{if }e\in D^+\\ -1& \text{if }e\in D^-\\ \phantom-0& \text{otherwise}. \end{cases} \] That is \[\F_{\Oscr^*}=\left\{\sum_{ D\in\D} \lambda_D \vec{D} \mid \lambda_i\in\Z\right\}\subseteq\Z^{|E|}.\] We call any $x\in\F_{\Oscr^*}$ a {\em coflow} of $\mathcal{O}$. Such an $x$ is a {\em nowhere-zero-$k$ coflow (NZ-$k$ coflow)} if $0<|x(e)|0$ holds for the chromatic polynomial $P(M;\lambda)$. This definition does not require orientability and coincides with ours for regular matroids. But then the chromatic number of the $n$-pont line $U_2^n$ equals $n$ (see \cite{welsh1976matroid} Page 264) and is not bounded for matroids of bounded rank. Another alternative is to define the chromatic number of an oriented matroid $\mathcal O$ to be $\lceil \chi_c (\mathcal O) \rceil$, where $\chi_c (\mathcal O)$ is the circular chromatic number of $\mathcal O$, as defined by Hlin\v{e}n\'y et.\ al.\ \cite{{hlineny, laura}}. Although their definition coincides with ours when $\mathcal O$ is regular \cite{goddyntarsizhang}, it is not a matroid invariant in general. For example, the (bicircular) matroid $U_3^6$ has $3$ reorientation classes with chromatic number $2$, and one with chromatic number $4$. The following theorem further supports the suitability of our definition of $\chi(\Oscr)$ with regard to Hadwiger's conjecture. \begin{theorem}[\cite{honijct}] Let $\Oscr$ be a simple oriented matroid of rank $r\ge3$. Then $\chi(\Oscr)\le r+1$. Moreover, $\chi(\Oscr)=r+1$ if and only if $\Oscr$ is an orientation of $M(K_{r+1}).$ \end{theorem} \section{Generalized Series-parallel Oriented Matroids} Recall that a {\em parallel extension} of a matroid $M$ is an extension by an element $e'$ which is parallel to some element $e$ of $M$ while a {\em series extension} is a coextension by an element $e'$ which is coparallel to some element. A matroid is called {\em series-parallel}~\cite{aigner} if it can be obtained from a one element matroid by a sequence of series and parallel extensions. It is well known that series-parallel matroids are exactly the graphic matroids of series-parallel networks, which are the graphs without a $K_4$-minor. The latter makes an inductive proof of Hadwiger's conjecture for the case $k=3$ almost trivial: if $G$ arises by a parallel extension from $G'$, any proper 3-coloring of $G'$ remains a proper 3-coloring of $G$, whereas, if $G$ arises by subdividing an edge $e$ into $e$ and $e'$, we have a free color for the new vertex. Translating this proof into a proof for the resulting NZ-$3$ coflow in an orientation of $G$, the key point arises in the case $G'=G/e$ (series extension), where the induction step relies on the existence of a $\{0,\pm 1\}$-valued coflow in $\vec G$, say $g^\ast$, whose support is $\{e,e'\}$. It has been shown \cite[Theorem 3.8]{HoNi} that such a coflow, $g^\ast$, exists in the coflow lattice of any orientation of a uniform oriented matroid, and implies that this class of matroids is 3-colorable. This motivates the following definition. \begin{definition}\label{def:serpar} Let $\Oscr$ be an oriented matroid. We say that $\Oscr$ is {\em generalized series-parallel (GSP)} if every simple minor of $\Oscr$ has a $\{0,\pm 1\}$-valued coflow which has exactly one or two nonzero entries. \end{definition} \label{sec:series-parallel} By its definition, the class of GSP oriented matroids is closed under minors. Note that an orientation of a regular matroid is GSP if and only if it is an orientation of a series-parallel matroid. \begin{theorem}\label{theo:3sr} Let $\Oscr$ be a GSP oriented matroid on a finite set $E$ without loops. Then $\Oscr$ has a NZ-$3$ coflow. \end{theorem} \begin{proof} We proceed by induction on $|E|$. If $\Oscr$ is not simple, then it has two parallel or antiparallel elements $e$ and $e'$. Since $\Oscr \setminus \{e'\}$ is generalized series-parallel without loops, by induction it admits a NZ-$3$ coflow which extends to a NZ-$3$ coflow in $\Oscr$ because every cocircuit contains either both or none of $e$ and $e'$, and either always with the same or always with opposite sign. Thus, we may assume $\Oscr$ is simple and that $\Oscr$ has a $\{0,\pm 1\}$-valued coflow, say $g^\ast$, whose support is $\{e,e'\}$ (possibly with $e=e'$). By reorienting $e'$ if necessary, we may assume that $g^\ast(e')=1$. Let $\Oscr'=\Oscr/e$. Then, $\Oscr'$ is a GSP oriented matroid without loops and, hence, there exists a NZ-$3$ coflow ${f'}^\ast$ in $\Oscr'$, which extends to a coflow ${f}^\ast$ in $\Oscr$ which is $0$ on $e$ and has entries from $\{\pm 1, \pm 2\}$ elsewhere. If ${f}^\ast(e')\in \{-2,0,1\}$, then ${f}^\ast + g^\ast$ is a NZ-$3$ coflow in $\Oscr$. Otherwise we have ${f}^\ast(e')\in \{-1,2\}$, so ${f}^\ast - g^\ast$ is a NZ-$3$ coflow in $\mathcal{O}$. \end{proof} A practical way to prove that every orientation of a matroid from a certain minor-closed class is GSP is to show the existence of {\em positive colines} for that class. \begin{definition} Let $M$ be a matroid. A {\em copoint} of $M$ is a flat of codimension~1, that is, a hyperplane. A {\em coline} is a flat of codimension 2. If $L$ is a coline of $M$ and $L \subseteq H$, a copoint, then we say $H$ is a {\em copoint on $L$}. The copoint is {\em simple} (with respect to $L$) if $|H\setminus L| =1$, otherwise it is {\em multiple}. A coline $L$ is {\em positive} if there are more simple than multiple copoints on $L$. \end{definition} %We will show in Lemma~\ref{lem:sp} that the existence of a positive coline in $M$ implies %the existence of a vector with exactly 2 non-zero entries which are %$\pm 1$ in the coflow lattice of any orientation of $M$. \begin{lemma}\label{lem:sp} If an orientable matroid $M$ has a positive coline, then every orientation $\Oscr$ of $M$ has a $\{0,\pm 1\}$-valued coflow which has exactly two nonzero entries. \end{lemma} \begin{proof} Let $L$ be a positive coline of $M$ and $\Oscr$ be some orientation of $M$. By Proposition 4.1.17 of \cite{BLSW}, the interval $[L,\hat 1]$ in the big face lattice of $\Oscr$ has the structure of the big face lattice of an even cycle. Here, each antipodal pair of vertices of the even cycle corresponds to a copoint of $L$. Neighboring copoints in this cycle are conformal vectors (see 3.7 in~\cite{BLSW}). Since $L$ is positive, by the pidgeonhole principle there must exist two neighboring simple copoints $D_1$ and $D_2$ in the even cycle. Since both copoints are simple, $(D_1 \cup D_2) \setminus L = \{e_1,e_2\}$. Since they are conformal, $\vec D_1 - \vec D_2$ is a vector with exactly two non-zero entries which are $+1$ or $-1$, namely on $e_1$ and $e_2$. \end{proof} \section{Bicircular Matroids} In this section we show that orientations of bicircular matroids are GSP and hence 3-colorable by Theorem~\ref{theo:3sr}. \label{sec:bicircular} Bicircular matroids form a minor-closed subclass of the class of transversal matroids. Therefore, they are $M(K_4)$-free, coordinatizable over the reals, and hence orientable. \begin{definition}\cite{simoes} \label{def:bicircular} Let $G$ be a graph (loops and parallel edges allowed) with vertex set $V$ and edge set $E$. The {\it bicircular matroid} of $G$ is the matroid $B(G)$ defined on $E$ whose circuits are the subgraphs which are subdivisions of one of the graphs: (i) two loops on the same vertex, (ii) two loops joined by an edge, (iii) three edges joining the same pair of vertices. A matroid is \emph{bicircular} if by deleting its loops it becomes isomorphic to $B(G)$ for some graph $G$. %Let $G=(V,E)$ be a graph. We define a set $I\subseteq E$ to be %independent if each component of $G[I]$ contains at most one cycle. %This defines the family of independent sets of a matroid called the %{\em bicircular matroid $B(G)$ represented by $G$}. A matroid is \emph{bicircular} %if by deleting its loops it becomes isomorphic to $B(G)$ for some graph $G$. % Let $G=(V,E)$ be a not necessarily simple graph. The {\em bicircular % matroid $B(G)$ represented by $G$} has as its independent sets the % subsets of $E$ that contain the edge set of at most one cycle of $G$ % in each of its connected components. A matroid is \emph{bicircular} % if deleting its loops results in $B(G)$ for some graph $G$. \end{definition} Note that the original definition of a bicircular matroid did not allow loops. The following is immediate from Definition~\ref{def:bicircular}. \begin{proposition}\label{prop:bc} \begin{enumerate} \item Bicircular matroids are closed under taking minors. \item For any graph $G$, the edge set of every forest in $G$ defines a closed set, that is, a flat of $B(G)$. \end{enumerate} \end{proposition} The following result suffices for our purpose. % \begin{theorem}\label{theo:poscol} Every simple bicircular matroid $M$ of rank $\ge 2$ has a positive coline. \end{theorem} \begin{proof} If $M$ has two coloops, then deleting both of them results in a coline of $M$ which has exactly $2$ simple copoints on it and no other copoints. If $M$ has exactly one coloop, say $e$, then we must have $\rk(M) \ge 3$. Applying induction on $|M|$, we find that $M/e$ has a positive coline which, together with $e$, gives a positive coline of $M$. Similarly, if a connected component $N$ of $M$ has a positive coline, then adding it to $M\setminus N$ results in a positive coline of $M$. Thus, we may assume $M$ is connected, simple, of rank at least 3, and without coloops. Therefore, $M = B(G)$ for some connected graph $G$ with $|V(G)| = \rk(M) \ge 3$. We select $G$ to have the fewest possible loops. Let $T_1$ be a spanning tree of $G$ and let $v$ be a leaf of $T_1$. Let $\{e_1, e_2, \dots, e_k\}$ be the set of non-loop edges of $G$ which are incident with $v$, for some $k \ge 1$. Since $M$ is simple, $v$ is incident to at most one loop edge of $G$; we denote this loop edge by $\ell$ if it exists. If $k=1$, then $\ell$ must exist, for otherwise $e_1$ is a coloop of $M$. But now we have that $B(G) = B(G')$ where $G'$ is the graph obtained from $G$ by replacing $\ell$ with an edge parallel to $e_1$. This contradicts the choice of $G$. So we may assume $k \ge 2$. Exactly one edge in $\{ e_1, e_2, \dots, e_k\}$ belongs to $T_1$, say $e_1 \in E(T_1)$. Let $F = T_1-e_1$ and let $T_i = F + e_i$, for $1 \le i \le k$. Then $T_i$ is a spanning tree of $G$ and $v$ is a leaf of $T_i$, for $1 \le i \le k$. By Proposition~\ref{prop:bc}, the set $L := E(F)$ is a flat of $M$. Since $L$ is also independent in $M$ and $|L| = |V(G)|-2$, $L$ is a coline of $M$. Also, for $1 \le i \le k$, the set $L \cup \{e_i\} = E(T_i)$ is a simple copoint on $L$. If $\ell$ exists then $L \cup \{\ell\} $ is also a simple copoint on $L$. Every remaining edge $e \in E(G)- L - \{e_1, e_2, \dots, e_k, \ell\}$ has both of its endpoints in the connected subgraph $F-v$, so the closure of $L \cup \{e\}$ in $M$ is the copoint $E- \{e_1, e_2, \dots, e_k, \ell\}$. There are no other copoints on $L$, and at most one of them is multiple. Since $k\ge2$, we have shown that $L$ is a positive coline of $M$. \end{proof} \begin{theorem}\label{theo:11} Every orientation of a bicircular matroid is GSP. \end{theorem} \begin{proof} The statement trivially holds for bicircular matroids of rank $\le 1$. The result now follows from Lemma~\ref{lem:sp}, Theorem~\ref{theo:poscol} and Proposition~\ref{prop:bc}. \end{proof} \begin{corollary} Bicircular matroids are 3-colorable. \end{corollary} \section{Open Problems and Conjectures} The definition of an oriented matroid being GSP does not seem to be related to duality. \begin{question} Are GSP oriented matroids closed under duality? \end{question} Since $M(K_4)$ is not series-parallel, every GSP oriented matroid is $M(K_4)$-free. Probably it would be too much to hope for the other inclusion: \begin{question} Does there exist an $M(K_4)$-free oriented matroid which is not GSP? \end{question} The previous question begs the following, more fundamental one. \begin{question} Does there exist an $M(K_4)$-free matroid which is not orientable? \end{question} Not every $M(K_4)$-free matroid has a positive coline, an example being $P_7$. We checked with Lukas Finschi's database \cite{finschi:enumeration} that $P_7$ has a unique reorientation class. Although there is no positive coline, this class still is GSP. Every bicircular matroid is a gammoid. Since $P_7$ is not a gammoid, the following might be a possible extension of Theorem \ref{theo:11} to the class of gammoids, which includes the class of transversal matroids. \begin{conjecture} Every simple gammoid of rank at least two has a positive coline. \end{conjecture} \section*{Acknowledgement} The term {\em positive coline} is due to Stephanie Adolph. \section*{References} \bibliographystyle{model4-names} \bibliography{bicircular} \end{document} %%% Local Variables: %%% mode: latex %%% TeX-master: t %%% End: