% LaTeX file
%

% Uncomment the following 5 lines if AMS fonts are avail.
\documentstyle[amssymbols]{article}
\newcommand{\RR}{{\Bbb R}}%
\newcommand{\QQ}{{\Bbb Q}}%
\newcommand{\ZZ}{{\Bbb Z}}%
\newcommand{\NN}{{\Bbb N}}%
\newcommand{\PP}{{\Bbb P}}%

% Comment out the following 5 lines if AMS fonts are avail.
%
%\documentstyle[]{article}%
%\newcommand{\RR}{\mbox{\boldmath$R$}}%
%\newcommand{\QQ}{\mbox{\boldmath$Q$}}%
%\newcommand{\ZZ}{\mbox{\boldmath$Z$}}%
%\newcommand{\NN}{\mbox{\boldmath$N$}}%
%\newcommand{\PP}{\mbox{\boldmath$P$}}%

% Length/width adjustments
\textwidth=6.1truein
\oddsidemargin=.25truein
\evensidemargin=.25truein
\setlength{\topmargin}{-0.7in}
\setlength{\textheight}{8.9in}

% Macros for this paper
\let\al\alpha \let\be\beta \let\ga\gamma \let\de\delta
\let\si\sigma \let\ka\kappa \let\edp\epsilon
\let\OF\Phi
\let\OC\Gamma
\let\o\circ
\def\iv{^{-1}}
\def\sign{\hbox{\rm sign}}
\def\deg{\hbox{\rm deg}}
\def\Van{\hbox{\rm Van}}
\def\vprod{\prod_{v \in V(G)}} 
\def\eprod{\prod_{e \in E(G)}}
\def\vsum{\sum_{v \in V(G)}}
\def\EC{{\fam0 EC}}
\def\ONF{{\fam0 1F}}
\def\KE{{\fam0 KE}}
\def\dEC{{\fam0 EC}_d}
\def\BTF{{\fam0 B2F}}
\def\RF{R}
\def\OOBTF{{\fam0 OOB2F}}
\def\F{\mbox{\boldmath$F$}}
\let\UF=F
\def\factn{fac\-tor\-iz\-ation}
\def\cl#1{\hbox to \hsize{\hss #1 \hss}}
%
\newtheorem{theorem}{Theorem}[section]
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{observation}[theorem]{Observation}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{conjecture}[theorem]{Conjecture}
%
\newenvironment{proof}%
	{\smallbreak\noindent {\bf Proof.\ }}%
	{\hskip 1em \vrule height1.5ex width1ex \medbreak}
%

\begin{document}

\cl{\Large\bf List edge colourings of some 1-factorable multigraphs}
\medskip
\cl{M. N. Ellingham\footnote{Supported by the University Research
Council of Vanderbilt University and NSERC Canada.}}
\cl{\sl Department of Mathematics, 1326 Stevenson Center}
\cl{\sl Vanderbilt University, Nashville, TN 37240, U. S. A.}
\cl{\tt mne@math.vanderbilt.edu}
\medskip
\cl{Luis Goddyn\footnote{Supported by NSERC Canada.}}
\cl{\sl Department of Mathematics and Statistics}
\cl{\sl Simon Fraser University, Burnaby, B. C., V5A 1S6, Canada}
\cl{\tt goddyn@math.sfu.ca}
\bigskip

\begin{abstract}
The List Edge Colouring Conjecture asserts that,
given any multigraph $G$ with chromatic index $k$ and
any set system $\{S_e: e \in E(G)\}$ with each $|S_e| = k$,
we can choose elements $s_e \in S_e$ such that $s_e \not = s_f$ whenever
$e$ and $f$ are adjacent edges.
Using a technique of Alon and Tarsi which involves the graph
monomial $\prod \{x_u-x_v : uv \in E\}$
of an oriented graph,
we verify this conjecture for certain families of 1-factorable
multigraphs, including 1-factorable planar graphs.
\end{abstract}

Keywords: list edge colouring, choosability, 1-factorization,
graph polynomial, graph monomial, planar graphs, regular graphs.

AMS Classification numbers: 05C15, (05C70, 05C10).

\section{Introduction}\label{intro}
Let $G=(V,E)$ be a graph (with multiple edges allowed).
A proper (vertex) colouring of $G$ is a function on
$V$ for which adjacent vertices receive distinct values.
A {\it proper $k$-colouring\/} is a proper colouring
whose range is a subset of $[k] := \{0,1,\ldots,k-1\}$.
With this definition, two distinct proper $k$-colourings
of $G$ may induce the same partition of $V(G)$.
A graph is {\it $k$-colourable} if it has a proper $k$-colouring.
The following concept was introduced by Erd\"os, Rubin and Taylor
\cite{ErdRubTay}. 
Let $a:V(G) \to \{1,2,\ldots\}$. 
We say that $G$ is {\it $a$-choosable\/} or
{\it $a$-list colourable\/} if for every set system
$\{ S_v : v \in V\}$ such that $|S_v| = a(v)$,
there is a proper colouring $c$
such that $c(v) \in S_v$ for $v\in V(G)$.
In case $a$ is the constant function $a(v) \equiv k$,
we say that $G$ is {\it $k$-choosable\/}.
The terms {\it $k$-edge colourable, $a$-edge choosable\/} and
{\it $k$-edge choosable\/} are defined in an analogous way.
If a graph is $k$-choosable, then it is $k$-colourable,
but not conversely, as shown by $K_{3,3}$
which is not $2$-choosable.
In contrast, we have the following.
%
\begin{conjecture}[List Edge Colouring Conjecture]\label{lecc}
If \/$G$ is a $k$-edge colourable multigraph,
then $G$ is $k$-edge choosable.
\end{conjecture}
%
This conjecture seems to have been arrived at
independently by several people.
It has been verified for the class of bipartite graphs
\cite{Gal}, and also for complete graphs of odd order
\cite{HagJan2}.
An excellent survey appears in \cite{Alo}.
Further results and historical comments
may be found in \cite{BolHin,CheHag}.
Our main result verifies this conjecture for a class
of planar graphs.
%
\begin{theorem}\label{main}
If $G$ is a $d$-regular $d$-edge colourable planar
multigraph, then $G$ is $d$-edge choosable.
\end{theorem}
%
The Four Colour Theorem is equivalent
to the statement that every $2$-connected $3$-regular planar graph
is $3$-edge colourable.
Theorem \ref{main} therefore implies that the
Four Colour Theorem is equivalent to the statement that
every $2$-connected $3$-regular planar graph is $3$-edge choosable. 
This was observed independently by F. Jaeger and M. Tarsi
[personal communication].
For $d \ge 4$,
the question of which $d$-regular planar multigraphs are $d$-edge
colourable has not yet been resolved.
Seymour \cite{Seymour} and others have proposed conjectures
that would imply that any $d$-edge connected
$d$-regular planar multigraph of even order is $d$-edge colourable,
and hence, by Theorem \ref{main}, $d$-edge choosable.

Our main tool is a result of Alon
and Tarsi \cite{AloTar} which relates choosablility to
coefficients in a certain polynomial. 
Let $D$ be an orientation of $G$. 
The {\it graph monomial\/}
of $G$ is the homogeneous polynomial $\edp(G)$
with variables $\{ x_v : v \in V(G)\}$ and defined by
\[
\edp(G)= \prod_{uv \in E(D)} (x_u-x_v) .
\]
(Some authors call $\edp(G)$ the {\em graph polynomial\/}, but
we abandon this overused term in favour of that used
by Sabidussi \cite{Sab}.)
As we have defined it, $\edp(G)$ depends on a particular
orientation $D$ of $G$; however changing the orientation
multiplies $\edp(G)$ by $\pm 1$, so $\edp(G)$ is unique up
to sign.
The graph monomial was first used by Petersen \cite{Petersen};
indeed Petersen gave {\it order, degree\/} and {\it factor\/}
their graph theoretical meanings by reference to $\edp(G)$.
Scheim \cite{Scheim} used $\edp(G)$
to prove some results about $3$-edge colourings of
$3$-regular planar graphs;
our Theorem \ref{main} extends one of his results.
Li and Li \cite{LiLi} mention $\edp(G)$ in the context of
determining the independence number of $G$.
%
\begin{theorem}[Alon and Tarsi \cite{AloTar}]\label{edpcoeff}
\hspace{0.5 in}
Let $a:V(G) \to \{1,2,\ldots\}$.  If the coefficient of
$\;\vprod x_v^{a(v)-1}$ in $\edp(G)$ is nonzero,
then $G$ is $a$-choosable.
\end{theorem}
%
Scheim's paper \cite{Scheim} contains much of the
reasoning needed to prove this theorem; however, he was working
before the introduction of the idea of list colourings, and did
not state his results in full generality.
Alon and Tarsi \cite{AloTar} give combinatorial interpretations
of the coefficients of $\edp(G)$, and use Theorem \ref{edpcoeff}
to investigate the (vertex) choosability of planar graphs and
bipartite graphs.
Fleischner and Stiebitz \cite{FleSti} use Alon and Tarsi's
results to solve a conjecture of Erd\"os regarding the $3$-vertex
colourability of certain $4$-regular graphs.
Penrose \cite{Pen} states the case $d=3$ of Theorem 3.1 in terms of
``abstract tensor systems''.



\section{Interpreting the Coefficient}\label{interpret}

In order to study edge choosability one applies
Theorem \ref{edpcoeff}
to line graphs.  
The {\it line graph\/} $L(G)$ of a multigraph $G$ has
$V(L(G))=E(G)$ with an edge joining $e$ to $f$ in $L(G)$
for each common endpoint that $e$ and $f$ have in $G$.  
Thus, every pair of parallel edges in $G$
is joined by {\em two} edges in $L(G)$. 
For regular $G$, the coefficient of
$\edp(L(G))$ which is of interest has several
nice combinatorial interpretations, some of which are
implicit in \cite{AloTar}
and explicitly described by N. Alon in the preamble to
Proposition 3.8 of \cite{Alo}. 

 From here on, $G$ is a $d$-regular multigraph.
Let  $\xi(G)$ denote the coefficient of
$\eprod x_e^{d-1}$ in $\edp(L(G))$.
If $\xi(G) \ne 0$, then $G$ is $d$-edge choosable,
and thus the List Edge Colouring Conjecture holds true for $G$.

The set of edges $\delta(v)$
incident with each vertex $v$ of $G$ can be ordered
with a {\it star labelling at $v$}, a bijection $\pi_v :
\delta(v) \to [d]$.  A {\it global star labelling} is a
set $\pi=\{\pi_v : v \in V(G)\}$.  We assume that $G$ comes with
a fixed global star labelling $\rho=\rho(G)=\{\rho_v\}$, called
the {\it reference labelling} of $G$, with which other star
labellings will be compared.
In particular, the {\it sign\/} of a star labelling $\pi_v$
(relative to $\rho$) is the sign of the permutation $\pi_v \o
\rho_v\iv$, and is denoted $\sign_\rho(\pi_v)$, or sometimes
just $\sign(\pi_v)$. 
The sign of a global star labelling $\pi$ is defined as
$\sign(\pi) = \prod_{v \in V(G)} \sign(\pi_v)$.

Star labellings allow us to assign signs to other combinatorial
objects in $G$.
A {\it $k$-factor\/} in $G$ is a $k$-regular spanning
subgraph of $G$.
Let $p=\lceil d/2 \rceil$.
An {\it ordered (near) $2$-\factn{}\/} of $G$ is an ordered
partition $\F=(F_0,F_1,\ldots, F_{p-1})$ of $E(G)$, where each
$F_i$ is a $2$-factor, unless $d$ is odd, in which case 
$F_{p-1}$ is a $1$-factor (hence the word ``near'').
An {\it orientation\/}
$\OF$ of $\F$ is an orientation of $G$ so that each
$F_i$ becomes a union $\OF_i$ of directed circuits, except that
when $d$ is odd $\OF_{p-1}=F_{p-1}$ remains an unoriented $1$-factor.
Let $\OOBTF(G)$ denote the set of oriented ordered (near)
$2$-\factn{}s of $G$ in which each $2$-factor is bipartite, i.e.
a union of even circuits.  For each $\OF \in \OOBTF(G)$, there is
an associated global star labelling $\pi$: given $uv \in \OF_i$
oriented from $u$ to $v$, we set $\pi_u(uv)=i$ and
$\pi_v(uv)=d-1-i$, or if $d$ is odd and $uv \in \OF_{p-1}$ then
$\pi_u(uv)=\pi_v(uv)=(d-1)/2$.  We define
$\sign(\OF)=\sign_\rho(\OF)$ to be $\sign(\pi)$.
As shown in \cite{Alo},
%
\begin{equation}\label{xi<orient}
\xi(G)\quad=\quad\pm
\sum_{\OF \in \OOBTF(G)} \sign(\OF) .
\end{equation}

Let $\BTF(G)$ denote the set of unordered
and unoriented bipartite (near)
$2$-\factn{}s of $G$. For any $\UF \in \BTF(G)$, we can define
$\sign(\UF)=\sign_\rho(\UF)$ to be $\sign(\OF)$ for any
orientation $\OF$ of any ordering of $\UF$. All such $\OF$ have
the same sign, because reversing the orientation of an even
circuit changes the sign at an even number of vertices, and
swapping two $2$-factors swaps two pairs of edges at each
vertex. If $\omega(\UF)$ is the total number of circuits in all
of the $2$-factors in $\UF$, then there are $2^{\omega(\UF)}$
orientations of each of the $\lfloor d/2 \rfloor !$ orderings of
$\UF$, so that (\ref{xi<orient}) may be rewritten as
%
\begin{equation}\label{xi<unordered}
\xi(G) \quad=\quad \pm
\; \lfloor d/2 \rfloor ! \;
\sum_{\UF \in \BTF(G)} \sign(\UF) \, 2^{\omega(\UF)} .
\end{equation}

The coefficient $\xi(G)$ may also be interpreted in
terms of edge colourings of $G$.
Let $\dEC(G)$ denote the set of
proper $d$-edge colourings $c:E(G) \rightarrow [d]$.
Each $c \in \dEC(G)$
induces a global star labelling $\tau=\tau(c)
%\in \SL(G)
$
%(not regular),
where for each edge $e=uv$, $\tau_u(e)=\tau_v(e)=c(e)$.
We define the sign of $c$ (with respect to $\rho(G)$) by
$\sign(c) = \sign(\tau(c))$.
As explained in \cite{Alo}, there is a bijection between
$\OOBTF(G)$ and $\dEC(G)$ which preserves all or reverses all
signs, giving
%
\begin{equation}\label{xi<colour}
\xi(G)\quad=\quad\pm\sum_{c \in \dEC(G)}\quad \sign(c).
\end{equation}

Let $\ONF(G)$ denote the set of unordered $1$-\factn{}s
of $G$.  Each $f \in \ONF(G)$ corresponds to an equivalence
class of $d!$ edge colourings in $\dEC(G)$ under permutations
of the colours $[d]$.  As interchanging two colours in $c$
introduces exactly $|V(G)|$ transpositions in $\tau(c)$, 
equivalent colourings in $\dEC(G)$ have equal sign.
Thus a sign function is well defined on $\ONF(G)$.
%
\begin{equation}\label{xi<onefactor}
\xi(G)\quad=\quad\pm \;\; d!\sum_{f \in \ONF(G)}\quad \sign(f)
\end{equation}

There is a coarser equivalence relation on $\dEC(G)$ on
whose parts a sign function can be defined.
An {\it elementary Kempe recolouring} of $c \in \dEC(G)$
exchanges the colours $i$ and $j$ on the edges of a single
component circuit of the $2$-factor $c\iv (i) \cup c\iv (j)$,
for some distinct $i,j \in [d]$.
Two elements of $\dEC(G)$ (or $\ONF(G)$)
are {\it Kempe equivalent} if
one can be obtained from the other by a 
sequence of elementary Kempe recolourings.
Let $\KE(G)$ denote the set of {\it Kempe (equivalence) classes} 
of proper $d$-edge colourings of $G$.
As with $1$-\factn{}s, Kempe equivalent colourings have the
same sign, and the sign of a Kempe class is well defined.
%
\begin{equation}\label{xi<kempe}
\xi(G)\quad=\quad\pm\;\;\sum_{\ka\in\KE(G)}\quad\sign(\ka)\,|\ka|
\end{equation}

We summarize with a list of sufficient conditions
for a graph to be $d$-edge choosable.
%
\begin{theorem}\label{oddep}
Let $G$ be a $d$-regular multigraph.
Suppose that at least one of the following holds.
\begin{description}
\item[(i)] $G$ has an odd number of distinct $1$-\factn{}s,
\item[(ii)] $G$ is $1$-factorable and any two $1$-\factn{}s
are Kempe equivalent,
\item[(iii)] $G$ is $1$-factorable and any two $1$-\factn{}s
have the same sign, or
\item[(iv)] the number of $F\in\BTF(G)$ which minimize the
total number $\omega(F)$ of circuits in all of
the $2$-factors in $F$ is odd.
\end{description}
Then $\xi(G) \ne 0$, and as a consequence
$G$ is $d$-edge choosable.
\end{theorem}
%
\begin{proof}
Claims (i) and (iii) follow immediately from
(\ref{xi<onefactor}), while (ii) follows from
(\ref{xi<kempe}).
If (iv) holds then the sum in (\ref{xi<unordered})
is non-zero modulo $2^{\omega_0+1}$, 
where $\omega_0 = \min\{\omega(F):F\in \BTF(G)\}$.
\end{proof}
%
Note that condition (ii) implies condition (iii).
We illustrate with some examples of $d$-regular graphs
which are $d$-edge choosable by Theorem \ref{oddep}.
The skeleton of the $3$-cube has four
distinct $1$-\factn{}s, but they are all
Kempe equivalent; thus (ii) applies, although (i) does not.
The generalized Petersen graph $P(9,2)$ has a unique
$1$-\factn{}
\cite{Thom},
%\cite[Chapter 18]{FioWil},
and so (i) and (ii) both apply.
Larger generalized Petersen graphs $P(6k+3,2)$, $k \ge 2$,
are not uniquely $1$-factorable, but have exactly three
Hamilton circuits \cite{Thom}.
Thus $\omega(F)$ is minimum (equal to $1$) for exactly three 
$F\in\BTF(G)$.  These provide an examples of
(iv) whereas (i), (ii) and (iii) may not hold.
The $8$-vertex M\"obius ladder
(which may be thought of as an octagon with all four
long diagonals added) has exactly three 1-\factn{}s,
and they are all Kempe equivalent; therefore (i) and (ii) both apply.
The skeleton of the dodecahedron has exactly ten
1-\factn{}s, each in its own Kempe class
and all of the same sign;
thus (iii) applies. 
The even complete graphs $K_{2r}$ satisfy (iii) for $r\le3$,
but not for $r\ge4$.
It appears likely that $\xi(K_{2r})$ is never zero
(we have verified this electronically for $r\le5$),
though this is probably a difficult problem.
It is not even known whether the
List Colouring Conjecture holds for $K_{2r}$.
Similarly, we expect that $\xi(K_{2r,2r})$ is never zero
(as has been verified for $r\le5$ by J. Janssen
[private communication]), although (iii) holds
only for $r\le2$.
 
In the next section we show that all $1$-\factn{}s
of a regular planar multigraph have the same sign.
In contrast, $K_{3,3}$ has exactly one $1$-\factn{} of 
each sign, thus $\xi(K_{3,3})=0$.
(Even so, $K_{3,3}$ is 3-edge choosable as it is bipartite \cite{Gal}.)
This is a special case of the situation for $K_{d,d}$
with $d\ge3$ odd, which is discussed in \cite{AloTar}.
More generally we have the following.
%
\begin{proposition}\label{duplicatedvertex}
If $G$ is $d$-regular, with $d$ odd, and there exist
distinct vertices $v$, $v'$ with identical neighbourhoods,
then $\xi(G)=0$.
\end{proposition}
%
\begin{proof}
We consider the involution on $\dEC(G)$ which interchanges
the colours of $vw$ and $v'w$, for each neighbour $w$ of $v$.
This involution is fixed-point free and, as $d$ is odd,
is sign-reversing.  Thus by (\ref{xi<colour}), $\xi(G)=0$.
\end{proof}
%
%Interestingly, we know of no $1$-factorable graph $G$ with $\xi(G)=0$
%which does not arise from this proposition
%and does not decompose, as described in Section \ref{decomp}.
%
We briefly describe two operations which can be used to produce
regular multigraphs $G$ with $\xi(G)=0$.
Let $G_0$ and $G_1$ be disjoint $d$-regular multigraphs
of even order,
and let
$v_i \in V(G_i)$ and $e_i \in E(G_i)$, $i=0,1$. 
We form a new $d$-regular multigraph $H$ from
$(G_0 -v_0) \cup (G_1 - v_1)$ 
by adding $d$ new edges,
each joining a neighbour of $v_0$ to a neighbour of $v_1$.
We also form a new $d$-regular multigraph $K$ from
$(G_0 -e_0) \cup (G_1 - e_1)$ 
by adding two new edges,
each joining an endpoint of $e_0$ to an endpoint of $e_1$.
Using (3),
%it is not hard to check that $\xi(H) = \xi(K) = 0$ provided that $\xi(G_0) = 0$.
one can show that
$\xi(H) = \pm \xi(G_0) \xi(G_1)/d!$ and that
$\xi(K) = \pm \xi(G_0) \xi(G_1)/d$.
Thus $\xi(H) = \xi(K) = 0$ provided that $\xi(G_0) = 0$.
%Interestingly, we know of no connected
%$1$-factorable graph $G$ with $\xi(G)=0$
%which does not arise from Proposition \ref{duplicatedvertex}
%and repeated application of these two operations.
Pavol Gvozdjak (personal communication) has found a Hamiltonian
cubic graph $G$ with $xi(G) = 0$, but which does not arise from
Proposition 2.2 nor either of these two operations.
We do not know whether this graph is 3-edge colourable.


\section{Regular planar multigraphs}\label{regplane}

In this section we prove Theorem \ref{main} by showing the following.
%
\begin{theorem}\label{eccount}
Let $G$ be a $d$-regular planar multigraph, $d \ge 1$.
Then all $1$-factorizations of $G$ have the same sign.
Hence $|\xi(G)|$ is precisely the number of 
proper $d$-edge colourings of $G$.
\end{theorem}
%
The case $d=3$ of this theorem was proved
by Scheim \cite{Scheim},
and can also be deduced from a result of
Vigneron \cite{Vigneron}
(see also Jaeger \cite{Jaeger})
together with observations of
Alon and Tarsi \cite{AloTar} relating the coefficients of
$\edp(G)$ to eulerian orientations of $G$.
We leave as unsolved the problem of 
determining which graphs satisfy
the conclusion of Theorem \ref{eccount}.

Roughly, we prove this theorem by giving a `geometric'
interpretation of $\sign(\OF)$ in (\ref{xi<orient}),
and then using the topology of the plane to deduce that
this sign is always positive.
We use terminology and notation from Section \ref{interpret}.
Let $G$ be a $d$-regular graph embedded on an orientable surface.
For $v \in V(G)$, a star labelling $\pi_v$ 
is said to be {\it clockwise\/} if the edges 
are labelled in clockwise ascending order around $v$.
A global star labelling $\pi = \{\pi_v\}$ of
$G$ is {\it clockwise\/} if each of its members is clockwise.  From
here on we assume the reference labelling $\rho(G)$
to be clockwise.
Let $\OF=(\OF_0,\ldots,\OF_{p-1}) \in \OOBTF(G)$
and let $v$ be a vertex of $G$.
For $\OF_i \in \OF$
we denote by $\OF_i(v)$ the connected component of
$\OF_i$ which contains $v$;  thus $\OF_i(v)$ is either
an edge or a directed circuit.
Two oriented $2$-factors $\OF_i , \OF_j\in \OF$
are said to {\it cross\/} at $v$ if the circuits
$\OF_i(v)$, $\OF_j(v)$ geometrically cross at $v$.
We say that an edge $e \in \de(v)\backslash E(\OF_i)$
lies {\it to the right\/} of $\OF_i$ (at $v$)
if $e$ lies geometrically on the right as
$\OF_i(v)$ is traversed through $v$.
Similarly, if $v$ lies on the boundary of a face $\RF$
of the embedding,
then $\RF$ is {\it to the left\/} of $\OF_i$ (at $v$)
if $\RF$ lies geometrically on the left as $\OF_i(v)$
is traversed through $v$.
It is important to note that the terms `cross'
and `to the left/right' can equally well (though more cumbersomely)
be defined purely in terms of $\OF$ and $\rho(G)$,
%for any reference labelling $\rho$,
without reference to any embedding of $G$.
For example, a face $\RF$ is specified by a pair of edges
in $\de(v)$ having consecutive $\rho_v$-labels (modulo $d$);
two 2-factors  $\OF_i$ and $\OF_j$ cross at $v$ if some cyclic
rotation of the sequence
$\rho_v\o\pi_v\iv(i),\:\rho_v\o\pi_v\iv(j),\:
\rho_v\o\pi_v\iv(d-1-i),\:\rho_v\o\pi_v\iv(d-1-j)$
is monotone,
%either increasing or decreasing,
where $\pi$ is the global star labelling associated with $\OF$.

We define three invariants which determine the sign of $\OF$
(relative to $\rho(G)$).
Let $v \in V(G)$.  
We denote by $x(\OF,v)$ the number of unordered pairs
of 2-factors in $\OF$ which cross at $v$. 
If $d\ge1$ is odd, then we define the {\it root edge} $e_v$
to be the edge $\OF_{p-1}(v)$;
we let $r(\OF,v)$ denote the number of
oriented 2-factors $\OF_i \in \OF$ for which 
$e_v$ lies to the right of $\OF_i$ at $v$.
If $d\ge 2$ is even, then we define the {\it root face} $\RF_v$
to be the face specified by the $\rho_v$-labels $0$ and $d-1$;
we let $l(\OF,v)$ denote the number of
oriented 2-factors $\OF_i\in \OF$ for which $\RF_v$
lies to the left of $\OF_i$ at $v$.
Finally, we set
$x(\OF) := \vsum x(\OF,v)$,
$r(\OF) := \vsum r(\OF,v)$, and
$l(\OF) := \vsum l(\OF,v)$.
%
\begin{lemma}
Let $G$ be a $d$-regular multigraph with reference
labelling $\rho$.
For any oriented ordered (near) $2$-factorization $\OF$  of $G$
we have
$\sign(\OF)=(-1)^{x(\OF)+r(\OF)}$ or 
$\sign(\OF)=(-1)^{x(\OF)+l(\OF)}$  
according to whether $d$ is odd or even. 
\end{lemma}
%
\begin{proof}
Given any star labelling $\pi_v$, let $\OF(v)$ denote the
oriented ordered partion of $\de(v)$ whose $i$th part is the
directed path with edges $\pi_v^{-1}(d-1-i)$ followed by
$\pi_v^{-1}(i)$, except that when $d$ is odd the $(p-1)$th part
is the unoriented root edge $e_v=\pi_v^{-1}(p-1)$. In general,
$x(\OF,v)$ equals the number of pairs of paths in $\OF(v)$ which
cross, and $r(\OF,v)$ ($l(\OF,v)$) is the number of such paths
for which $e_v$ ($R_v$) lies to the right (left).

Let $\pi$ be the global star labelling associated with $\OF$.
For each $v$, $\OF(v)$ is just the restriction of $\OF$ to $\de(v)$.
A {\it $\rho$-consecutive transposition\/} of 
$\pi_v$ is any transposition which exchanges the
$\pi_v$-labels on any two edges in $\delta(v)$
whose $\rho_v$-labels differ by exactly one.
The sign of $\pi_v$ is determined by the length
of a sequence $S$ of such transpositions which transforms
$\pi_v$ into $\rho_v$.
In case $d$ is odd,
a $\rho$-consecutive transposition of $\pi_v$ corresponds
to a modification of $\OF(v)$
which does exactly one of two things. 
First, it may cross or uncross exactly one pair of
dipaths in $\OF(v)$.
%changing $x(\OF,v)$ by $\pm 1$. 
Second, it may transfer
%the root edge
$e_v$ from one side of exactly one such dipath
to its other side.
%changing $r(\OF,v)$ by $\pm 1$. 
By definition, if $\pi_v = \rho_v$, then
$x(\OF,v) = r(\OF,v) = 0$.
Thus $x(\OF,v)+r(\OF,v)$ is congruent to the number of 
transpositions in $S$ (modulo 2), so
$\sign(\pi_v) = (-1)^{x(\OF,v)+r(\OF,v)}$.
Thus
$\sign(\OF) = \vprod(-1)^{x(\OF,v)+r(\OF,v)} =
(-1)^{x(\OF)+r(\OF)}$.
The
$d$-even
case
%where $d$ is even
is exactly analogous,
writing $l$ and $R_v$ in place of $r$ and $e_v$.
\end{proof}
%
We remark here on an essential difference between the
$d$-odd and $d$-even cases. 
The root edge $e_v$ is determined by $\OF$
whereas the root face $R_v$ is defined by $\rho(G)$.
There appears to be no way of resolving this dichotomy.

A {\it plane\/} graph is a specific embedding of a planar
graph in the plane. 
To prove Theorem \ref{eccount} it suffices,
by (\ref{xi<orient}), to show that
$x(\OF)$, $r(\OF)$ and $l(\OF)$ are even, for any
$\OF \in \OOBTF(G)$,
whenever $G$ is plane and $\rho(G)$ is clockwise.
This (essentially) is proved in the next three lemmas.
%
\begin{lemma}\label{x-even}
Let $G$ be a plane $d$-regular multigraph with a clockwise
reference labelling $\rho$. 
Then $x(\OF)$ is even
for any oriented ordered (near) $2$-factorization $\OF$ of $G$.
\end{lemma}
\begin{proof}
Let $x_{ij}$ denote the number of vertices at which two
oriented $2$-factors $\OF_i,\:\OF_j \in \OF$ cross.
As any two edge-disjoint circuits in the plane 
geometrically cross an even number of times,
each $x_{ij}$ is even and thus $x(\OF)=\sum_{ij} x_{ij}$ is even.
\end{proof}

In contrast to $x(\OF)$, 
both $r(\OF)$ and $l(\OF)$ depend on the particular orientation
$\OF$ of the underlying (near) $2$-factorization $F$.
However, their parities are not affected by reorientation,
provided that each of the 2-factors in $F$ is bipartite.
In case $d$ is odd, we use the following simple observation
whose proof is omitted.
%
\begin{proposition}\label{cubplanparity}
Let $G$ be a plane $3$-regular multigraph,
and let $C$ be a circuit of $G$.
Let $i$ be the number of vertices of $C$ incident with an edge inside
$C$, and $j$ the number of vertices of $G$ inside $C$.  Then $i \equiv
j \pmod 2$.
\end{proposition}
%
\begin{lemma}\label{oddbip}
Let $G$ be a $d$-regular plane multigraph, where $d\ge1$ is odd,
and suppose that $\rho(G)$ is clockwise.
Then $r(\OF)$ is even,
for any oriented ordered bipartite near $2$-factorization $\OF$ of $G$.
\end{lemma}
%
\begin{proof}
For $0 \le i \le p-2$, let $r_i$ be the number of vertices $v$
for which the root edge $e_v$ is to the right of
the oriented $2$-factor $\OF_i\in \OF$.
As $r(\OF) = \sum_{i=0}^{p-2} r_i$,
it suffices to show that each $r_i$ is even. 
For each $i$ we argue as follows. 
%As reversing the orientation of any component circuit
%in $\OF_i$ does not affect the parity of $r_i$,
We may assume that each circuit $C$
in $\OF_i$ is oriented clockwise so that
`to the right of $\OF_i$' is equivalent to `inside $C$'.
For any circuit $C$ in $\OF_i$, the vertices of $G$
inside $C$ are the vertices of a union of even circuits in $\OF_i$.
Thus an even number of vertices of $G$ lie inside $C$.
Applying Proposition \ref{cubplanparity} to the 
(undirected) $3$-regular subgraph
of $G$ induced by the edges in $\OF_i\cup\OF_{p-1}$,
there are an even number of vertices $v$ in $C$ for which
$e_v$ lies inside of $C$.  As $\OF_i$ is a disjoint
union of circuits $C$, $r_i$ is even as required.
\end{proof}

For the $d$-even case,
we need some preliminary definitions.
Let $G$ be a plane graph, and $C$ a circuit in $G$.  We say that $C$
{\it surrounds} a vertex $v$ (or face $\RF$) if $v$ (or $\RF$)
is contained within the bounded region of ${\RR}^2 - C$.
If $H$ is a $2$-factor of $G$ and $v$ is a vertex of $G$,
let $s(v,H)$ be
the number of component circuits in $H$ that surround $v$;
define $s(\RF,H)$ similarly for a face $\RF$.
Suppose $G$ is a $d$-regular plane multigraph, where $d=2p$ is even.
Then the plane dual of $G$ is bipartite,
and we can properly $2$-face-colour $G$,
using colours $0$ and $1$, so that the outer face is coloured $0$.
If $G$ has a $2$-factorization $F=\{F_0, F_1, \ldots, F_{p-1}\}$,
then it is not difficult to see that every face $\RF$
receives the colour obtained by reducing
modulo $2$ the sum $s(\RF, F_0)+s(\RF,F_1)+\ldots+s(\RF,F_{p-1})$.
We say that the reference labelling $\rho(G)$ is
{\it $0$-consistent} if it is clockwise and
each root face $R_v$, $v\in V(G)$ is coloured $0$.
%for every vertex $v$, the root face $\RF_v$ is coloured $0$.
%
\begin{lemma}\label{evenbip}
Let $G$ be a $d$-regular plane multigraph,
where $d\ge2$ is even, and suppose that $\rho(G)$ is 
$0$-consistent.
%Let $d\ge 2$ be even and let $G$ be a $d$-regular plane multigraph
%with a clockwise, $0$-consistent reference labelling $\rho$.
Then $l(\OF)$ is even,
for any oriented ordered bipartite $2$-factorization $\OF$ of $G$.
\end{lemma}
%
\begin{proof}
We may assume that each component circuit $C$ in $\OF_i$
is oriented anticlockwise so that
`to the left of $\OF_i$' is equivalent to `inside $C$'.
For $0 \le i \le p-1$ and for each vertex $v$,
let $l_i(v)$ equal $1$ if $\RF_v$ lies inside the
circuit $\OF_i(v)$,
%in $\OF_i$ on which $v$ lies
and $0$ otherwise.
For $v\in V(G)$ we consider the colour of $\RF_v$,
which is the modulo $2$
reduction of $\sum_{i=0}^{p-1} s(\RF_v,\OF_i)$,
and which is also $0$, because $\rho$ is $0$-consistent. 
For each $i$, $s(\RF_v,\OF_i)=s(v,\OF_i)+l_i(v)$. 
Therefore, working modulo $2$, the colour of $\RF_v$ is
\[
0 \quad\equiv\quad
\sum_{i=0}^{p-1} s(v,\OF_i) + \sum_{i=0}^{p-1} l_i(v)
\]
which implies
\[
\sum_{i=0}^{p-1} l_i(v) \;\;\equiv\;\; \sum_{i=0}^{p-1} s(v,\OF_i) .
\]
Therefore,
\begin{eqnarray*}
l(\OF)  &   =    &  \vsum \; \sum_{i=0}^{p-1} l_i(v)      \\
        & \equiv &  \sum_{i=0}^{p-1} \; \vsum s(v,\OF_i) .
\end{eqnarray*}
Since each component circuit $C$ of each $\OF_i$ has an even number
of vertices,
and $s(v, \OF_i)$ is constant for all vertices of $C$, each sum
$\vsum s(v,\OF_i)$ is even,
and so $l(\OF)$ is also even, as required.
\end{proof}



\bigskip
\noindent{\Large\bf Acknowledgments}
\medskip

The authors wish to thank Noga Alon, Roland H\"aggkvist and Jarik
Ne\v setril for useful discussions.

\begin{thebibliography}{99}

\bibitem{Alo} N. Alon, Restricted colorings of graphs,
{\it in\/} ``Surveys in Combinatorics'', Proc. $14^{th}$ British
Combinatorial Conference,  London Mathematical Society Lecture
Notes Series 187, edited by K. Walker, Cambridge University Press,
1993, 1-33.

\bibitem{AloTar} N. Alon and M. Tarsi, Colorings and orientations
of graphs, {\it Combinatorica\/} {\bf 12} (1992), 125--134.

%\bibitem{Blanusa} Danilo Blanu\v sa, Problem Ceteriju Boja (The
%problem of four colours), {\it Hrvatsko Prirodoslovno Dru\v stvo
%Glasnik Mat.-Fiz. Astr. Ser. II\/} {\bf 1} (1946) 31--42 (in
%Croatian).

%\bibitem{BolHar} B. Bollob\'as and A. J. Harris, List-colourings
%of graphs, {\it Graphs Combin.\/} {\bf 1} (1985) 115--127.
%
\bibitem{BolHin} B. Bollob\'as and H. R. Hind, A new upper bound
for the list chromatic number, {\it Discrete Math.\/} {\bf 74}
(1989) 65--75.

\bibitem{CheHag} Amanda Chetwynd and Roland H\"aggkvist,
A note on list-colorings, {\it J. Graph Theory\/} {\bf 13} (1989)
87--95.

%\bibitem{Descartes} Blanche Descartes, Network-colourings, {\it
%Math. Gazette\/} {\bf 32} (1948) 67--69.

\bibitem{ErdRubTay} P. Erd\"os, A. Rubin and H. Taylor,
Choosability in graphs, {\it Congr. Numer.\/} {\bf 26} (1979)
125--157.

%\bibitem{FioWil} S. Fiorini and R. J. Wilson, {\it
%Edge-colourings of graphs\/}, Pitman, London (1977).

\bibitem{FleSti} H. Fleischner and M. Stiebitz, A solution to a
colouring problem of P. Erd\"os, {\it Discrete Math.\/} {\bf 101}
(1992), 39--48.

\bibitem{Gal} F. Galvin, The list chromatic index of a bipartite multigraph,
{\it J. Combin. Theory Ser. B\/} {\bf 63} (1995), 153--159.

%\bibitem{GraLiLi} R. L. Graham, S.-Y. R. Li and W.-C. W. Li, On
%the structure of $t$-designs, {\it SIAM J. Alg. Disc. Meth.\/} {\bf
%1} (1980) 8--14.
%
%\bibitem{HagJan1} R. H\"aggkvist and J. Janssen, On the
%list chromatic index of Bipartite graphs, preprint, 1993.

\bibitem{HagJan2} R. H\"aggkvist and J. Janssen, New bounds
on the list-chromatic index of the complete graph,
submitted.

\bibitem{Jaeger} F. Jaeger, On the Penrose number of cubic
diagrams, {\it Discrete Math.\/} {\bf 74} (1989) 85--97.

\bibitem{LiLi} S.-Y. R. Li and W.-C. W. Li, Independence numbers
of graphs and generators of ideals, {\it Combinatorica\/} {\bf 1}
(1981) 55--61.

\bibitem{Pen} Roger Penrose, Applications of negative dimensional tensors, in
{\sl ``Combinatorial Mathematics and its Applications''\/}
{\it Proc. Conf, Oxford, 1969,\/}
Academic Press, London, 1971, 221-244.

\bibitem{Petersen} Julius Petersen, Die Theorie der regul\"aren
graphs, {\it Acta Math.\/} {\bf 15} (1891) 193--220.

\bibitem{Sab} G. Sabidussi,  Binary invariants and orientations of graphs,
{\it Discrete Math.\/} {\bf 101} (1992), 251--277.

\bibitem{Scheim} David E. Scheim, The number of edge $3$-colorings of
a planar cubic graph as a permanent, {\it Discrete Math.\/} {\bf 8} (1974)
377--382.

\bibitem{Seymour} P. D. Seymour, Some unsolved problems on
one-factorizations of graphs, {\it Graph Theory and Related
Topics\/}, edited by J. A. Bondy and U. S. R. Murty, Academic Press
(1979) 367--368.

%\bibitem{Stahl} Saul Stahl, The embeddings of a graph -- a survey,
%{\it J.\ Graph Theory\/} {\bf 2} (1978) 275--298.

\bibitem{Thom} Andrew Thomason, Cubic graphs with three
hamiltonian cycles are not always uniquely edge colourable,
{\it J.\ Graph Theory\/} {\bf 6} (1982) 219--221.

\bibitem{Vigneron} L. Vigneron, Remarques sur les r\'eseaux
cubiques de classe 3 associ\'es au probl\`eme des quatre
couleurs, {\it C. R. Acad. Sc. Paris\/} {\bf 223} (1946), 770-772.


%\bibitem{Vizing} V. G. Vizing, Critical graphs with a given
%chromatic class (Russian; Kriticheskiye grafy s dannym khromaticheskim
%klassom), {\it Diskret. Analiz\/} {\bf 5} (1965) 9--17.  MR 34\#17.
%
\end{thebibliography}


\end{document}