%
% July, 1992
%

%
% Uncomment the following 5 lines if AMS fonts are avail.
%
\documentstyle[art12,amssymbols]{article}
\newcommand{\QQ}{{\Bbb Q}}%
\newcommand{\QQP}{{\Bbb Q}_{\geq 0} }%
\newcommand{\ZZ}{{\Bbb Z}}%
\newcommand{\ZZP}{{\Bbb Z}_{\geq 0} }%

%
% Comment out the following 5 lines if AMS fonts are avail.
%
%\documentstyle[art12]{article}%
%\newcommand{\QQ}{\mbox{\boldmath$\cal Q$}}%
%\newcommand{\QQP}{{\QQ}_{\geq 0} }%
%\newcommand{\ZZ}{\mbox{\boldmath $\cal Z$}}%
%\newcommand{\ZZP}{{\ZZ}_{\!\geq 0} }%

 
\setlength{\textwidth}{6.3in}
\setlength{\textheight}{8.8in}
\setlength{\oddsidemargin}{0.0 in}
\setlength{\evensidemargin}{0.0 in}
\setlength{\topmargin}{0.0in}
\setlength{\headheight}{0in}  
\setlength{\headsep}{0in}
\flushbottom

\newcommand{\kdc}{$(k,d\/)$-coloring }%
\newcommand{\kdcs}{$(k,d\/)$-colorings }%
\newcommand{\kdf}{$(k,d\/)$-flow }%
\newcommand{\kdfs}{$(k,d)$-flows }%
\newcommand{\w}{\omega}%
\newcommand{\bs}{\backslash}
\newcommand{\se}{\subseteq}
\newcommand{\C}{{\cal C} }%
\newcommand{\B}{{\cal B} }%
\newcommand{\G}{\Gamma}%


\newtheorem{lemma}{\sc Lemma}[section]%
\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}%
\newtheorem{remark}[lemma]{\sc Remark}%
\newtheorem{note}[lemma]{\sc Note}%
\newtheorem{algorithm}[lemma]{\sc Algorithm}%
\newtheorem{example}[lemma]{\sc Example}%
\newtheorem{observation}[lemma]{\sc Observation}%
\newtheorem{definition}[lemma]{\sc Definition}{}%
\newtheorem{numbered}[lemma]{\sc}%
\newenvironment{proof}{\noindent {\sc Proof.}}{$\Box$\par\medskip}%
\date{July 22, 1993}

\title{On $(k,d\,)$-Colorings and Fractional Nowhere Zero Flows}
\author{Luis A. Goddyn\thanks{Supported by the National Sciences and
Engineering Research Council operating grant \#A-4699.} \\
{\normalsize Department of Mathematics and Statistics}\\
{\normalsize Simon Fraser University}\\
{\normalsize Burnaby, BC}\\
\and
Michael Tarsi\\
{\normalsize Computer Science Department}\\
{\normalsize School of Mathematical Sciences}\\
{\normalsize Tel-Aviv University, 69978}\\
{\normalsize Israel}\\
\and
Cun-Quan Zhang\thanks{Partially supported under NSF grant DMS-9306379.}\\
%Cun-Quan Zhang\thanks{Partially supported under NSF grant DMS-8906973.}\\
{\normalsize Department of Mathematics}\\
{\normalsize West Virginia University}\\
{\normalsize Morgantown, WV}
}

\begin{document}
\maketitle

\begin{abstract}
The concepts of \kdc and the star chromatic number,
studied by Vince, by Bondy and Hell, and by Zhu
are shown to reflect the cographic instance of a wider concept,
that of  fractional nowhere-zero flows in  regular matroids.
\end{abstract}

\section{Introduction}

Vince \cite{Vin}
introduced the following generalization of chromatic number.

\begin{definition}
A {\em \kdc}of a graph $G$ is a function $c:V(G) \rightarrow Z_k$ such
that for every $xy \in E(G)$, $|c(x) -c(y)| \ge d$. 
(Here, $Z_k$ denotes the cyclic group of residues mod $k$,
and $|a|$ is the smaller of the two integers $a$ and $k-a$.)
The {\em star chromatic number}, $\chi^*(G)$, is the infimum of
$k/d$ over all \kdcs of $G$.
\end{definition}

Vince proved, by means of analytical arguments, that this infimum is
a minimum (and hence rational).  He also proved that for every $k,d$ such that
$k/d \ge \chi^*(G)$, there exists a \kdc of $G$. 
Setting $d=1$ we have that the chromatic number of $G$ is
$\chi(G) = \lceil \chi^*(G) \rceil$.
Later, Bondy and Hell \cite{Bon} improved Vince's result by giving a
purely combinatorial proof.  A further study and an alternate
definition of $\chi^*(G)$ in terms of homomorphisms into
intervals of a unit circle
appear in \cite{Zhu}.  The purpose of this note is to show
that \kdcs are an instance of
the more general concept of fractional
nowhere-zero flows in regular matroids.

\section{Fractional Flows in Graphs}
It is helpful to introduce the notion of fractional flows in graphs
before considering the general matroidal case.
Let $k$ be a positive integer.
A {\em $k$-flow} in a graph $G$ is an orientation
$\w(G)$ together with a function
$f:E(G) \rightarrow \{ 0, \pm 1, \pm 2,\ldots ,\pm (k-1) \}$
such that the net flow
$\sum_{vu \in \delta^+(v)} f(vu) - \sum_{uv \in \delta^-(v)} f(uv)$
is zero for each $v \in V(G)$. 
The {\em flow  index}, $\xi(G)$ is the least $k$ for which
$G$ has a {\em nowhere-zero} $k$-flow
(that is, $f(e) \ne 0, \: \mbox{for all } e \in E(G)$). 
This parameter has been studied by many authors
(see \cite{Jae} for a thorough review).
We generalize this notion with the following.


\begin{definition}\label{Def1}
A {\em \kdf}in a graph $G$ is a $k$-flow
$(\w(G),f)$ such that the range of $f$ is contained in
$\{ \pm d, \pm (d+1) ,\ldots,\pm (k-d) \}$.
The {\em star flow index} $\xi^*(G)$ is the infimum of 
$k/d$ over all \kdfs in $G$.
\end{definition}

Thus, a $(k,1)$-flow is the same as a nowhere-zero $k$-flow.
We shall see that, analogously to $(k,d)$-colorings,
the infimum in Definition \ref{Def1} is a minimum, and $G$ has a
\kdf  whenever $k/d \ge \xi^*(G)$, 
and thus that $\xi(G) = \lceil \xi^*(G) \rceil$.

It is well known that, in the setting of matroids,
vertex colorings and nowhere-zero flows are dual concepts.
In particular, if $G$ is a plane graph and $H$ its planar dual,
then $\chi(G) = \xi(H)$. 
We shall see that a similar correspondence holds between the concepts
of star chromatic number and star flow index.

\section{Flows in Matroids} \label{flows_in_matroids}

The proper setting for the study of flows and colorings is that of 
regular matroids.
We assume familiarity with the circuit/cocircuit axioms of basic
matroid theory such as in \cite{Wel}.
Let $\C$ ($\B$) denote the \{0,1\}-valued circuit-element
(cocircuit-element) incidence matrix of a matroid $M$. 
If $M$ is binary then, over GF$(2)$, we have $\C \B^\top =0$. 
An {\em orientation} $\w(M)$ of $M$ is a signing
($1 \mapsto \pm 1$) of the elements of $\C$ and $\B$ 
such that $\C \B^\top =0$ as rational matrices.
It is well known that a binary matroid is orientable if and only if
it is {\em regular}.  (See \cite{Wel} for terminology and a proof.) 
It is a good exercise to find the relationship between orientations
of a graph $G$ and of the graphic matroid $M(G)$.
For any circuit $C$ in $\w (M)$, let $C^+$ ($C^-$) denote the set of
elements in $C$ which are positively (negatively) oriented
with respect to $\w(M)$.
For any cocircuit $B$ in $\w (M)$, we define $B^+$ and $B^-$ similarly.

Let $\G$ be an abelian group.  A {\it $\G$-flow} in a
regular matroid $M$ is an orientation $\w(M)$ and
a function $f:M \rightarrow \G$ such that
for every cocircuit $B$,
$\sum_{e \in B^+} f(e) = \sum_{e \in B^-} f(e).$
A flow $f$ is said to be {\em nowhere-zero}
if $f(e) \ne 0$, for all $e \in M$.
An {\em integer flow} is a $\G$-flow where $\G=\ZZ$,
the ring of integers.  
For integers $0 < d < k$, a {\it $(k,d)$-flow} is an integer flow
with values in the set $\{ \pm d, \pm  (d+1), \ldots ,\pm  (k-d) \}$,
and a {\it nowhere-zero $k$-flow} is a $(k,1)$-flow.
As with graphs, 
the {\it star flow index} $\xi^*(M)$ is the infimum of $k/d$
over all $(k,d)$-flows in $M$,
and the {\it flow index} $\xi(M)$ is the minimum $k$ for which 
$M$ has a nowhere-zero $k$-flow.


The following facts about nowhere-zero flows are well known and can be found
in \cite{Tut}.

\begin{proposition}\label{basic}
Let $\w(M)$ be an oriented regular matroid.
\begin{enumerate}
\item
If $M$ has no coloops (one-element cocircuits) then $M$ has a
nowhere-zero $k$-flow for some integer $k$, and hence $\xi(M)$ and
$\xi^*(M)$ are bounded.
\item
For any abelian group $\G$ of order $k$,
$M$ has a nowhere-zero $\G$-flow if and only if
$M$ has a nowhere-zero $k$-flow.
Furthermore, if $f$ is a $Z_k$-flow in $M$,
then $M$ has a $k$-flow $f'$ such that
$f'(e) \equiv f(e) \!\!\pmod k ,\:\: \mbox{for all } e \in E$.
\end{enumerate}
\end{proposition}

Our starting point is the following lemma, due to Hoffman \cite{Hof}.

\begin{lemma}[Hoffman's Lemma]\label{HoffLemma}
Let $M$ be an oriented regular matroid.  Given a pair of non-negative
rational functions
$l,u : M \rightarrow \QQ$ such that $0 \le l(e) \le u(e)$ for $e \in M$,
there exists a rational flow $f:M \rightarrow \QQ$
such that $l(e) \le f(e) \le u(e)$ for every $e \in M$ if and only if,
for every cocircuit $B$,
\begin{equation}
\sum_{e \in B^{+}}l(e) \leq \sum_{e \in B^{-}}u(e)~~~~~{\rm and}~~~~~
\sum_{e \in B^{-}}l(e) \leq \sum_{e \in B^{+}}u(e).
\end{equation}
Additionally, $f$ can be chosen to be
 integer valued provided that $l$ and $u$ are integer valued.
\end{lemma}

In case $M$ is graphic, Hoffman's Lemma is just the Ford-Fulkerson
flow theorem \cite{For}.  If $M$ is cographic then this is the
Potential Differences Existence Theorem of Ghouila-Houri \cite{Gho}.
If $l(e)\equiv l$ and $u(e)\equiv u$ are constant, then (1) becomes:
\[\frac{l}{u} \leq \frac{|B^{+}|}{|B^{-}|} \leq \frac{u}{l}.\]

Thus by Hoffman's Lemma with $l \equiv d$ and $u \equiv k-d$,
we obtain the following.

\begin{theorem}\label{main}
A regular matroid $M$ has a \kdf if and only if there exists some 
orientation $\w(M)$ such that, for any cocircuit $B$,
$d/(k-d) \le |B^+|/|B^-| \le (k-d)/d$.
\end{theorem}

\begin{corollary}\label{maincor}
The star flow index $\xi^*(M)$ of a regular matroid $M$ is
the minimum over all orientations $\w(M)$ of
\[1 + \max \{ \frac{|B^+|}{|B^-|},\frac{|B^-|}{|B^+|}
  : B\mbox{ is a cocircuit in }\w(M) \}  .\]
\[= \max \{ \frac{|B|}{|B^-|},\frac{|B|}{|B^+|}
  : B\mbox{ is a cocircuit in }\w(M) \}  .\]
\end{corollary}

This maximum is unbounded (and hence $\xi^*(M):=\infty$) if and
only if $M$ has a coloop.
Putting $d=1$, we have that for any regular matroid $M$,
$$\xi(M) = \lceil\xi^*(M)\rceil.$$

A \kdc $c:V(G) \rightarrow Z_k$ of an
(arbitrarily oriented) graph $G$ induces a $Z_k$-nowhere-zero flow
 $f$ in the cographic
matroid $M^*(G)$ by letting $f(xy)=c(x)-c(y)$ for every arc $xy \in G$.
By {\em 2.} of Proposition \ref{basic},
this is equivalent to the existence of
an integer flow in $M^*(G)$ whose values range in absolute value
between $d$ and $k-d$, that is, a \kdf in $M^*(G)$.
This process can be reversed to obtain a \kdc of $G$
from a \kdf of $M^*(G)$. 
Thus from Theorem \ref{main} we have the following.

\begin{corollary}\label{cor}
The star chromatic number $\chi^*(G) = \xi^*(M^*(G))$ of a graph $G$ equals
\[ \min_{\w(G)} \max_C \{ \frac{|C|}{|C^+|} , \frac{|C|}{|C^-|} \} \]
where the minimum is over all orientations of $G$ and the 
maximum is over all circuits of $G$.
\end{corollary}

We note that the characterization of the (integer) chromatic number
$\chi = \lceil \chi^* \rceil$ of a
graph via the formula of Corollary \ref{cor} was proved independently of
Hoffman's Lemma by Minty \cite{Min}.

\section{Some Observations Regarding $\chi^*$ and $\xi^*$}

(1) Vince's results \cite{Vin}
regarding the star-chromatic number of a graph 
immediately follow from Corollary \ref{cor}.  For example, in the case of the odd
circuit $C_{2k+1}$, at least $k+1$ edges must be similarly oriented
in any orientation and hence $\chi^*(C_{2k+1})=(2k+1)/k = 2+1/k$.

\vspace{.1in} \noindent
(2) Let $c : V \rightarrow Z_k$ be a \kdc of a graph $G=(V,E)$.
For each $a \in Z_k$ let $I(a)$ denote the independent set
$\{ v \in V :  c(v) \in \{ a, a+1,\ldots,a+d-1\}\!\!\!\!\pmod k \,\}$.
%By definition, $\{ I(a): a \in Z_k \}$ provides $k$ independent sets,
%which together cover every vertex exactly $d$ times.
The $k$ independent sets $\{I(a):a\in Z_k\}$ together cover
every vertex exactly $d$ times. 
Let us call such a collection a {\it $(k,d)$-independent cover}.
Since any graph with a $(k,d)$-independent cover has an independent
set of size at least $|V|d/k$, it follows that
%An immediate consequence of the last statement is
$\alpha(G) \geq |V| / \chi^{*}(G)$,
an improvement on the well-known bound
$|V| / \chi(G)$.

Although a \kdc always provides a $(k,d)$-independent cover,
the two concepts are not equivalent.
Take, for example, the graph $G_{10}$ on 10 vertices and 35 edges
obtained by adding all edges joining two disjoint circuits of length
five.
Each `side' of $G_{10}$ induces a $C_5$ subgraph and hence has a
$(5,2)$-independent cover. 
Two such covers, one from each `side', form a
$(10,2)$-independent cover of $G_{10}$.  On the other hand, 
$G_{10}$ does not admit a $(10,2)$-coloring as $\chi(G_{10}) =6$.

\vspace{.1in} \noindent
(3) A {\em weighted independent cover} is a collection of independent
sets, each of which is assigned a positive rational weight, 
such that the total weight of the sets containing each vertex is 
at least 1.  The {\em fractional chromatic number} $\chi^f(G)$
is defined to be the least total weight of any weighted independent
cover of $G$.  This parameter has been studied in several papers
(see \cite{Fur},\cite{Hel} for example).
As the existence of a  $(k,d)$-independent cover of $G$ implies
$\chi^f(G) \le k/d$ we have the following.
\begin{observation}
For any graph $G$, $\chi^f(G) \le \chi^*(G)$.
\end{observation}
Equality does not always hold here;
for instance, $\chi^f(G_{10})=5$ while $\chi^*(G_{10})=6$.
(We leave these for the reader to check!)

\vspace{.1in} \noindent
(4) Let the graph $G=(V,E_1 \cup E_2)$ be the union two subgraphs 
$G_1 = (V,E_1)$ and $G_2 = (V,E_2)$.  Obviously, 
$\chi(G) \le \chi (G_1)\chi(G_2)$.  Such a product formula also holds for 
the flow index --- a fact utilized in Seymour's proof \cite{Sey} that
$\xi(G) \le 6=2 \times 3$ for any 2-edge connected graph $G$.  Unfortunately
analogous statements, where $\chi$ and $\xi$ are replaced by $\chi^*$
and $\xi^*$, are false.
A counterexample for $\chi^*$ is provided again by the graph $G_{10}$;
the star chromatic number of
the disjoint union of two $C_5$'s is 2.5 and $\chi^*(K_{5,5}) =2$,
whereas $\chi^*(G_{10})=6$.  Using a similar
construction one can find, for any pair of rational numbers
$a,b \ge2$, a graph $G$ consisting of two subgraphs $G_1$ and $G_2$,
such that $\chi^*(G_1)=a$, $\chi^*(G_2)=b$ and
$\chi^*(G)= \lceil a \rceil \lceil b \rceil$.
Analogous examples exist for $\xi^*$.

\vspace{.1in} \noindent
(5) We finish with an extension of the notion of chromatic number
to (general) orientable matroids.  
As explained in \cite{Bjo}, orientable matroids need not be binary
(as is tacitly assumed in some works such as \cite{Wel}).
The following definition is more general than --- but consistent
with --- that given in in Section \ref{flows_in_matroids}.
An {\em orientation} of an arbitrary matroid is a signing
$1\rightarrow \pm1$ of $\C$ and $\B$
such that, for any row $C$ of $\C$ and any row $B$ of $\B$, if 
$C_e, B_e \ne 0$ for some $e \in E$, then there exists
$f\in E\backslash \{e\}$ such that one of $C_e B_e$, $C_f B_f$
equals $+1$ and the other equals $-1$.   
A matroid is {\em orientable} if it has at least one orientation. 
One can use Corollaries \ref{maincor} and \ref{cor} to {\em define}
$\xi^*(M)$ and $\chi^*(M)$ (and hence $\xi(M)$ and $\chi(M)$)
for an arbitrary orientable matroid $M$.
There are several natural questions one might ask.  For example,
the chromatic number of a (loop-free) orientable matroid of rank $r$
is bounded by the size of its largest circuit, which is at most $r+1$.
However, we do not know whether the flow index of a (coloop-free)
orientable matroid of bounded rank is bounded. 
(This is true for regular matroids since their
underlying simple matroids have bounded size.)

Two orientations of $M$
are said to belong to the same {\em reorientation class} if one
is obtained from the other by multiplying a corresponding set
of columns of $\B$ and $\C$ by $-1$.  Although regular matroids have
only one reorientation class, orientable matroids can have
many reorientation classes.  Winfried Hochst\"attler has pointed out
that it may be more sensible to define $\xi^*$ (and $\chi^*$) for
each reorientation class $\psi(M)$ of $M$ by appropriately
restricting the minimum in Corollary \ref{maincor}.
%restricting the minimum in
%Corollary \ref{maincor} and \ref{cor} to those
%orientations belonging to that class.

\begin{definition}
The star flow index of a reorientation class $\psi(M)$ of
an orientable matroid $M$ is given by
\[
\xi^*(\psi(M)) =  \min_{\w\in \psi(M)} \max_B \{ \frac{|B|}{|B^+|} ,
\frac{|B|}{|B^-|} \}.\]
where the maximum is taken over the cocircuits $B$ of $M$.
\end{definition}

\begin{thebibliography}{99}

\bibitem{Bon}
{\sc J. A. Bondy and P. Hell},
On the star chromatic number,
{\em J. Graph Theory} {\bf 14} (1990) 479-482.

\bibitem{Bjo}
{\sc A.~Bj\"orner, M.~Las Vergnas, B.~Sturmfels, N.~White, G.~M.~Zieg\-ler},
{\em Oriented Matroids, Encyclopedia of Mathematics and its Applications}
{\bf 46}, Cambridge University Press, Cambridge (1993).

\bibitem{For}
{\sc L. R. Ford and D. R. Fulkerson},
Maximal flow through a network,
{\em Canad. J. Math.} {\bf 8} (1956) 399-404.

\bibitem{Fur}
{\sc Z. F\"uredi},
Matching and covering in hypergraphs,
{\em Graphs and Combinatorics} {\bf 4} (1988) 115-206.

\bibitem{Gho}
{\sc A. Ghouila-Houri},
Sur l'existence d'un flot ou d'une tension prenant ses
valeurs dans un groupe ab\'elien,
{\em C. R. Acad. Sciences} {\bf 250} (1960) 3931-3932.

\bibitem{Hel}
{\sc P. Hell and F. Roberts},
Analogues of the Shannon capacity of a graph,
{\em Ann. Discrete Math.} {\bf 12} (1982) 155-186.

\bibitem{Hof}
{\sc A. J. Hoffman},
Some recent applications of the theory of linear inequalities
to extremal combinatorial analysis,
{\em Combinatorial Analysis: Proceedings of the Tenth Symposium
in Applied Mathematics of the American Mathematical Society},
R. Bellman and M. Hall Jr. Eds., American Mathematical Society (1960) 113-128.

\bibitem{Jae}
{\sc F. Jaeger},
Nowhere-zero flow problems,
{\em in} Selected Topics in Graph Theory, Vol. 3,
L. Beineke and R. Wilson Eds., Academic Press, New York (1988) 91-95.

\bibitem{Min}
{\sc G. J. Minty},
A theorem on $n$-coloring the points of  a linear graph,
{\em Amer. Math. Monthly} {\bf 69} (1962) 623-624.

\bibitem{Sey}
{\sc P. D. Seymour},
Nowhere-zero 6-flows,
{\em J. Combin. Theory Ser. B} {\bf 30} (1981) 130-135.

\bibitem{Tut}
{\sc W. T. Tutte},
A contribution to the theory of chromatic polynomials.
{\em Canad. J. Math.} {\bf 6} (1955) 80-91.

\bibitem{Vin}
{\sc A. Vince},
Star chromatic number,
{\em J. Graph Theory} {\bf 12} (1988) 551-559.

\bibitem{Wel}
{\sc D. Welsh},
{\em Matroid Theory},
Academic Press, San Francisco (1976).

\bibitem{Zhu}
{\sc X. Zhu},
Star chromatic numbers and products of graphs,
{\em J. Graph Theory} {\bf 16} (1992) 557-569.

\end{thebibliography}

\end{document}