\documentclass[reqno]{tran-l} % % Transactions of the American Mathematical Society % Corresponding author: Luis Goddyn goddyn@math.sfu.ca % Department of Mathematics, % Simon Fraser University, % Burnaby BC V5A 1S6 % CANADA % Authors: DeVos, Goddyn, Mohar, Vertigan, Zhu % Title: Coloring-flow duality of embedded graphs % % Submitted on April 7 2003 % Revision history % ================ % First version by Luis and Matt, received 01/8/27 % First revision by Bojan 01/9/1 % Another big revision by Matt, May 02 % Hopefully the final big revision by Bojan, July 02 and August 02 % A reorganized version by Luis Jan/Feb 03 % Version 14 produced by Bojan on March 24-28, 2003 % Minor update by Luis just prior to submission Apr a,7 2003. % Final corrections after referee Oct 2, 2003 \copyrightinfo{2003} {American Mathematical Society} \usepackage{latexsym} \usepackage{amssymb} \usepackage{epsf} \renewcommand{\subjclassname}{% \textup{2000} Mathematics Subject Classification} \newtheorem{theorem}{Theorem}[section] \newtheorem{lemma}[theorem]{Lemma} \newtheorem{corollary}[theorem]{Corollary} \newtheorem{proposition}[theorem]{Proposition} \newtheorem{conjecture}[theorem]{Conjecture} \theoremstyle{definition} \newtheorem{definition}[theorem]{Definition} %\newtheorem{example}{Example}[section] \newtheorem{example}[theorem]{Example} %AMS Trans required \theoremstyle{remark} \newtheorem{remark}[theorem]{Remark} \numberwithin{equation}{section} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % % Authors' definitions % \newcommand{\DEF}[1]{{\em #1\/}} % used for definitions, e.g. \DEF{flow} % Centering the EPS graphics inside the FIGURE environment \def\centeredgraphics #1{\begin{center}\hskip 0.1mm\epsffile{#1}\end{center}} % Use for figures as follows: % \begin{figure}[htb] % \centeredgraphics{FileName1.eps} % \caption{Text of the caption} % \label{fig:1} % \end{figure} \newcommand\chic {\mathop{\chi_{\rm c}}} % circular chromatic number \newcommand\chiloc{\mathop{\chi_{\rm loc}}} % local chromatic number \newcommand\phic {\mathop{\phi_{\rm c}}} % circular flow number %\newcommand\fw {\mathop{\hbox{\bf{fw}}}} % face-width %\newcommand\ew {\mathop{\hbox{\bf{ew}}}} % edge-width \newcommand\fw {\mathop{\hbox{\rm{facewidth}}}} % face-width \newcommand\ew {\mathop{\hbox{\rm{edgewidth}}}} % edge-width \newcommand\pg {\mathop{\hbox{\rm{pointgirth}}}}% point-girth \newcommand\mf {\mathop{\hbox{\rm{maxface}}}} % max-face \newcommand\st {\mathop{\hbox{\rm{strength}}}} % strength \newcommand\Inv {\mathop{\hbox{{\rm Inv}}}} % involutive subgroup \newcommand\imbal{ {\hbox{{\rm imbal}}}} % imbalance function \newcommand\girth{\mathop{\hbox{{\rm girth}}}} % girth function \newcommand\cogirth{\mbox{{\rm cogirth}}} % cogirth function \newcommand{\RR}{\ensuremath{\mathbb R}} % real numbers %\newcommand{\NN}{\ensuremath{\mathbb N}} % natural numbers \newcommand{\ZZ}{\ensuremath{\mathbb Z}} % integers %\newcommand{\CG}{\ensuremath{\mathbb {R/Z}}} % the circle group \newcommand{\CG}{\ensuremath{\mathbb O}} % the circle group \newcommand\surf{\ensuremath{\mathbb X}} % generic surface \newcommand\N {\ensuremath{\mathbb N}} % Nonorientable surface \renewcommand\S {\ensuremath{\mathbb S}} % Orientable surface \renewcommand\epsilon{\varepsilon} \newcommand\faceordual{dual\ } % Change to {face\ } if we decide for `face walk' %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \begin{document} \title{Coloring-flow duality of embedded graphs} \author[M. DeVos]{Matt DeVos} \address{Department of Mathematics\\ Princeton University\\ Princeton, NJ 08544 USA} \email{matdevos@math.princeton.edu} \author[L. Goddyn]{Luis Goddyn$^1$} \address{Department of Mathematics\\ Simon Fraser University\\ Burnaby, BC, Canada} \email{goddyn@math.sfu.ca} \thanks{$^1$Supported in part by the National Sciences and Engineering Research Council of Canada, and the Pacific Institute for the Mathematical Sciences.} \author[B. Mohar]{Bojan Mohar$^2$} \address{Department of Mathematics\\ University of Ljubljana\\ Ljubljana, Slovenia} \email{bojan.mohar@fmf.uni-lj.si} \thanks{$^2$Supported in part by the Ministry of Science and Technology of Slovenia, Research Program J1--0507--0101.} \author[D. Vertigan]{Dirk Vertigan$^3$} \address{Department of Mathematics\\ Louisiana State University\\ Baton Rouge, Louisiana} \email{vertigan@math.lsu.edu} \thanks{$^3$Supported in part by the National Security Agency, grant number MDA904-01-0014.} \author[X. Zhu]{Xuding Zhu$^4$} \address{Department of Applied Mathematics\\ National Sun Yat-sen University \\ Kaohsiung, Taiwan} \email{zhu@math.nsysu.edu.tw} \thanks{$^4$Supported in part by ROC National Science Council Grant NSC 91-2115-M-110-003.} \keywords{Graph theory, coloring, flow, tension, local tension, circular chromatic number, surface, edge-width, triangulation, quadrangulation, locally bipartite.} \subjclass{05C10, 05C15\\ Received by editors April 7, 2003. Revised version received October 3, 2003.} \date{} \begin{abstract} Let $G$ be a directed graph embedded in a surface. A map $\phi : E(G) \rightarrow \RR$ is a \DEF{tension} if for every circuit $C \subseteq G$, the sum of $\phi$ on the forward edges of $C$ is equal to the sum of $\phi$ on the backward edges of $C$. If this condition is satisfied for every circuit of $G$ which is a contractible curve in the surface, then $\phi$ is a \DEF{local tension}. If $1 \le |\phi(e)| \le \alpha-1$ holds for every $e \in E(G)$, we say that $\phi$ is a (\DEF{local}) \DEF{$\alpha$-tension}. We define the \DEF{circular chromatic number} and the \DEF{local circular chromatic number} of $G$ by $\chic(G) =\inf \{\alpha \in \RR \mid \mbox{$G$ has an $\alpha$-tension} \}$ and $\chiloc(G) = \inf \{ \alpha \in \RR \mid \mbox{$G$ has a local $\alpha$-tension} \}$, respectively. The invariant $\chic$ is a refinement of the usual chromatic number, whereas $\chiloc$ is closely related to Tutte's flow index and Bouchet's biflow index of the surface dual~$G^*$. From the definitions we have $\chiloc(G) \le \chic(G)$. The main result of this paper is a far reaching generalization of Tutte's coloring-flow duality in planar graphs. It is proved that for every surface $\surf$ and every $\epsilon > 0$, there exists an integer $M$ so that $\chic(G) \le \chiloc(G) + \epsilon$ holds for every graph embedded in $\surf$ with edge-width at least $M$, where the \DEF{edge-width} is the length of a shortest noncontractible circuit in $G$. In 1996, Youngs discovered that every quadrangulation of the projective plane has chromatic number 2 or 4, but never 3. As an application of the main result we show that such `bimodal' behavior can be observed in $\chiloc$, and thus in $\chic$ for two generic classes of embedded graphs: those that are triangulations and those whose face boundaries all have even length. In particular, if $G$ is embedded in some surface with large edge-width and all its faces have even length $\le 2r$, then $\chic(G)\in [2,2+\epsilon] \cup [\frac{2r}{r-1},4]$. Similarly, if $G$ is a triangulation with large edge-width, then $\chic(G)\in [3,3+\epsilon] \cup [4,5]$. It is also shown that there exist Eulerian triangulations of arbitrarily large edge-width on nonorientable surfaces whose circular chromatic number is equal to 5. \end{abstract} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \maketitle %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \section{Introduction} \label{sect:intro} Our discussion is concerned with tensions, local tensions, and flows on embedded graphs. Although rigorous definitions will be postponed until Section \ref{sect:def}, some informal description needs to be stated here. By default all graphs are finite directed graphs, where loops and multiple edges are allowed. A \DEF{walk} or \DEF{circuit} in a graph~$G$ is a walk or circuit in the undirected graph which underlies $G$. A \DEF{surface} $\surf$ is a closed compact connected $2$-manifold. An \DEF{$\surf$-embedded graph} is a graph $G$ which is topologically embedded in $\surf$ in such a way that each connected component of $\surf - G$, or \DEF{face}, is homeomorphic to a disc. Where no confusion arises, we use $G$ to refer both to an $\surf$-embedded graph, and to the underlying abstract directed graph. Let $G$ be an embedded directed graph. A map $\phi: E(G) \rightarrow \RR$ is a \DEF{flow} if at every vertex the sum of the values on the incoming edges is equal to the sum on the outgoing edges. We say that $\phi$ is an \DEF{$\alpha$-flow} if $1 \le |\phi(e)| \le \alpha - 1$ holds for every $e \in E(G)$. %Luis added Informal definitions of \DEF{$\alpha$-tension} and \DEF{local $\alpha$-tension} are given in the abstract. % We define three invariants: % \begin{eqnarray*} \chic(G) & = & \inf \{ \alpha \in \RR \mid \mbox{$G$ admits an $\alpha$-tension} \}, \\ \chiloc(G) & = & \inf \{ \alpha \in \RR \mid \mbox{$G$ admits a local $\alpha$-tension} \}, \\ \phic(G) & = & \inf \{ \alpha \in \RR \mid \mbox{$G$ admits an $\alpha$-flow} \}. \end{eqnarray*} They are called the \DEF{circular chromatic number}, the \DEF{local circular chromatic number}, and the \DEF{circular flow index}, respectively. These invariants, and most results in this paper, are independent of the graph orientation. For example, if we reverse the orientation of $e \in E(G)$, then by replacing $\phi(e)$ by $-\phi(e)$ we preserve the property that $\phi$ is a (local) $\alpha$-tension or $\alpha$-flow. The chromatic number of a graph $G$ is given by $\chi(G) = \lceil \chic(G) \rceil$, c.f., e.g.~\cite{Zhu}. Thus, we may view $\chic$ as a refinement of the usual notion of chromatic number. There are close connections between $\chic$ and other graph properties involving orientations, homomorphisms and group valued tensions. As such, there has been considerable interest in the invariant $\chic(G)$. We refer the reader to \cite{Zhu} for a survey. All existing literature on $\chiloc(G)$ refers to this invariant indirectly, via the dual embedded graph $G^*$. In particular, if the surface is orientable, then $\chiloc(G^*) = \phic(G)$ and $\lceil \chiloc(G^*) \rceil$ is precisely the \DEF{flow index} of Tutte \cite{Tu54}. If the surface is nonorientable, then $\lceil \chiloc(G^*) \rceil$ is the \DEF{biflow index} of Bouchet \cite{Bo}. Thus $\chiloc$ both unifies and refines these two indices for embedded graphs. Our main result reveals a close connection between $\chic(G)$ and $\chiloc(G)$ for embedded graphs. Based on the above discussion we have \begin{equation} \label{invariants} \chiloc(G) \le \chic(G) \le \chi(G) \end{equation} for every embedded graph $G$. The first two invariants in (\ref{invariants}) are equal for plane graphs and projective plane graphs, by Corollary \ref{cor:chiloc=chic}, but they can differ on other surfaces. Our main result is that $\chiloc(G)$ and $\chic(G)$ are very close if an $\surf$-embedded graph $G$ has high edge-width. We recall that the \DEF{edge-width} of $G$, denoted by $\ew(G)$, is the length of a shortest circuit in $G$ which forms a noncontractible curve in $\surf$. We define $\ew(G)=\infty$ if $\surf$ is simply connected. \begin{theorem}[Main Theorem] \label{thm:chilt} For every surface $\surf$ and every $\epsilon > 0$, there exists an integer $M$ so that every %Luis inserted "loopless" loopless $\surf$-embedded graph $G$ with $\ew(G) \ge M$ satisfies $$ \chiloc(G) \le \chic(G) \le \chiloc(G) + \epsilon. $$ \end{theorem} Theorem \ref{thm:chilt} is proved in Section \ref{sect:proof}. It is a special case of Theorem \ref{thm:main} which is concerned with group-valued tensions. We apply this result to two families of embedded graphs for which $\chiloc$ exhibits interesting behavior. An embedded graph $G$ is \DEF{even-faced} if all its faces have even length. A \DEF{triangulation} is an embedded graph whose faces all have length three. In Section \ref{sect:families}, we show that even-faced embedded graphs and triangulations come in two types: odd and even type. In both cases, the \DEF{type} of~$G$ depends on the `signature parity' of certain closed walks in the dual $G^*$ (although, in strikingly different ways). We shall see that this distinction is reflected in the value of~$\chiloc(G)$. \begin{theorem} [Bimodality of $\chiloc$] \label{thm:bimodality} Let $G$ be an embedded graph. \renewcommand{\theenumi}{{\rm \alph{enumi}}} \begin{enumerate} % \item If $G$ is even-faced with maximum face length $2r$, then either \[ \chiloc(G) = 2 \mbox{ (even type) \quad or \quad} \chiloc(G) \ge \frac{2r}{r-1} \mbox{ (odd type).} \] % \item If $G$ is a triangulation, then either \[ \chiloc(G) = 3 \mbox{ (even type) \quad or \quad} \chiloc(G) \ge 4 \mbox{ (odd type).}\quad\;\; \] \end{enumerate} \end{theorem} % Applying Theorem \ref{thm:chilt} and some upper bounds from Theorem \ref{thm:upper bounds}, we have the following. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \begin{corollary} [Bimodality of $\chic$] \label{cor:bimodality} For any surface $\surf$ and any $\epsilon>0$, there exists an integer $M$ such that, for every $\surf$-embedded graph $G$ with $\ew(G) \ge M$, \renewcommand{\theenumi}{{\rm \alph{enumi}}} \begin{enumerate} \item if $G$ is even-faced with maximum face length $2r$, then \[ %Luis: Pick one % \chic(G) \in [ 2, 2+\epsilon ] \cup [ 2+ 2/(r-1) , 4 ] , %\chic(G) \in [ 2, 2+\epsilon ] \cup \left[ \frac{2r}{r-1},4 \right] , \chic(G) \in [ 2, 2+\epsilon ] \cup [ 2r/(r-1) , 4 ] ; \] \item if $G$ is a loopless triangulation, then \[ \chic(G) \in [ 3, 3+\epsilon ] \cup [ 4, 5 ] . \] \end{enumerate} \end{corollary} Moreover, we show (cf.\ Theorem \ref{thm:chi5}) that certain Eulerian triangulations of large edge-width on nonorientable surfaces have circular chromatic number equal to 5. These results completely generalize and explain Youngs' observation~\cite{Yo} that projective plane quadrangulations never have chromatic number three. They also strengthen results on the chromatic number of quadrangulations \cite{AHN, NNO}, even-faced graphs \cite{ Hu, MS}, and Eulerian triangulations \cite{HRS}. \begin{remark} A little more can be said in some special cases: \begin{enumerate} \item If $\surf$ is the plane or projective plane, the invariant $\chic(G)$ is relatively well behaved. For example, we may set $\epsilon=0$ in Theorem \ref{thm:chilt} and in Corollary~\ref{cor:bimodality} (cf.~Corollary~\ref{cor:chiloc=chic}). If $G$ is even-faced, then there is an exact formula for $\chic(G)$ (cf. Example~\ref{eg:PP}). %For example, loopless projective plane quadrangulations~$Q$ %and hexangulations~$H$ satisfy $\chic(Q) \in \{ 2,4\}$, %$\chic(H) \in \{ 2,3\}$, %strengthening Youngs' result regarding~$\chi(Q)$ In particular, every projective planar even-faced graph~$G$ satisfies $\chic(G) = 2 + 2/k$ for some $k \in \{0,1,\ldots, \infty\}$ (where we interpret $1/\infty =0$ and $1/0 = \infty$). \item The upper bound `$4$' can be replaced by `$3$' in part (a) of Corollary~\ref{cor:bimodality} provided all circuits in~$G$ have length at least $6$ (cf.~Theorem \ref{thm:upper bounds}(d)). More generally, it might be true that we can replace `$4$' with `$ 2 + 2/(g-1) $' provided all circuits have length at least~$2g$. \item The interval `$[4,5]$' in Corollary~\ref{cor:bimodality}(b) can be replaced by `$\{4\}$' if $\surf$ is orientable and $G$ is Eulerian. This is implied by a result of Hutchinson et al.~\cite{HRS} which states that all such triangulations of sufficiently large edge-width satisfy $\chi(G) \le 4$. If~$\surf$ is orientable but $G$ has odd-degree vertices, then one would be able to replace `$[4,5]$' by `$[4,4+\epsilon]$' provided a conjecture of Gr\"unbaum (Conjecture~\ref{conj:orientable upper bounds}(b)) holds. \end{enumerate} % In Section~\ref{sect:egs} we provide examples that show no further improvements of this type are possible. \end{remark} When the surface $\surf$ is orientable, these results have consequences involving flows in the surface dual. Let $G^*$ be the unoriented $\surf$-embedded graph which is the surface dual of $G$. Using a global orientation of $\surf$, we may direct the edges of~$G^*$ so that each edge $e^* \in E(G^*)$ crosses left to right over the corresponding dual edge $e \in E(G)$. % It follows from definitions that a function $\phi : E(G) \rightarrow \RR$ is a local $\alpha$-tension of $G$ if and only if $\phi^* : e^* \mapsto \phi(e)$ is an $\alpha$-flow in $G^*$. Thus, duality exchanges local tensions with flows on orientable surfaces, and we have the relation $\phi_c(G^*) = \chiloc(G)$. If $\surf$ is the sphere, every local tension is also a tension, so %Luis: deleted %duality exchanges flows and tensions and we have that $\chic(G) = \chiloc(G) = \phi_c(G^*)$. Indeed, this is an early observation of %Luis: added reference Tutte~\cite{GTZ}, usually recognized as flow-coloring duality, which provided motivation for our work. The following corollary of Theorem~\ref{thm:chilt} generalizes this to orientable surfaces. \begin{corollary} [Approximate Duality] \label{cor:flow version} Let\/ $\surf$ be an orientable surface and let $\epsilon > 0$. There exists an integer $M$ such that every loopless $\surf$-embedded graph $G$ with $\ew(G) \ge M$ satisfies $\phi_c(G^*) \le \chic(G) \le \phi_c(G^*) + \epsilon$. %where $G^*$ denotes the surface dual graph of $G$. \end{corollary} % When $G$ and $G^*$ are embedded in a surface which is not orientable, $G^*$ cannot be consistently oriented, and the duality between local tensions of~$G$ and flows of~$G^*$ no longer holds. In this case, local tension is the dual notion of a \DEF{biflow}, see, e.g., \cite{Bo,De}. Thus, any results about local tensions for $G$ can be formulated as results about flows (respectively, biflows) for the dual graph $G^*$ in the orientable (respectively, nonorientable) case. In order to get a unified treatment of the orientable and nonorientable surfaces, we will henceforth concentrate on tensions and local tensions. \section{Known Results and Conjectures} \label{sect:known} We briefly survey the state of knowledge regarding the invariants $\chic$, $\chiloc$, and $\phic$. The bimodal behaviors reported in Corollary~\ref{cor:bimodality} appear nowhere in the literature except for Youngs' observation \cite{Yo} that a projective plane quadrangulation has chromatic number either $2$ or $4$. The apparent singularity of Youngs' example is explained by an inspection of Corollary~\ref{cor:bimodality}; in any other situation, either $\epsilon$ is positive, or $2+2/(r-1) \le 3$, so bimodal behaviour is not detectable via the crude invariant $\chi=\lceil \chic \rceil$. The circular chromatic number is needed in order to see that Youngs' example is not an isolated curiosity. Other than \cite{Yo}, the existing literature consists primarily of proven and conjectured upper bounds on the integer values $\lceil \phic(G) \rceil$, $\lceil\chiloc(G)\rceil$ and $\chi(G) = \lceil \chic(G) \rceil$ for various families of embedded and abstract graphs~$G$. Most of these bounds are best possible due to examples given in Section~\ref{sect:egs}. However, there is now the question as to whether these upper bounds are also best possible for the refined parameters $\phic$, $\chiloc$ and $\chic$. The \DEF{girth} of $G$, $\girth(G)$, is the minimum length of a circuit in $G$. The \DEF{cogirth} of $G$, $\cogirth(G)$, is the minimum cardinality of a nonempty edge cut in~$G$. For any graph~$G$ we have $\chic(G) <\infty$ (resp.\ $\phic(G) <\infty$) if and only if $\girth(G)\ge 2$ ($\cogirth(G)\ge 2$). In contrast, it is possible that $\chiloc(G)$ is finite for an embedded graph $G$ with loops. For example, the unique graph~$G$ embedded on the Klein bottle consisting of one vertex and two one-sided loops has $\chiloc(G)=2$. In general one expects stronger upper bounds on $\chic(G)$ (and $\phic(G)$) when higher girth (and cogirth) requirements are imposed upon a family of graphs. For embedded graphs, one often forbids short noncontractible circuits; embedded graphs with high edge-width are `locally planar' and thus exhibit bounded chromatic properties. One should keep in mind that $\surf$-embedded graphs $G$ satisfy $\girth(G) \le \ew(G)$, but $\cogirth(G)$ is generaly unrelated to $\ew(G^*)$. Most published results and conjectures regarding $\phic(G)$ make no reference to a surface, but do refer to $\cogirth(G)$. For a positive integer~$d$, we define $$ \phic(d) = \sup \{\phic(G) \mid G \mbox{ is a graph with }\cogirth(G)\ge d \}. $$ Tutte \cite{Tu54} initiated the study of $\alpha$-flows when he conjectured $\phic(2) \le 5$ and $\phic(4) \le 3$. %Petersen's graph meets the first bound. Seymour \cite{Se} proved that $\phic(2) \le 6$, and Jaeger \cite{Ja} proved that $\phic(4) \le 4$. Jaeger \cite{Ja1} further conjectured that $\phic(4k) \le 2+\frac1k$ for any positive integer~$k$. Little progress has been made on these beautiful conjectures. % Two more conjectures involve embedded graphs. At a meeting in Donovaly in 1992, Neil Robertson proposed that there exists an absolute constant $k$ such that every $\surf$-embedded graph $G$ with $\cogirth(G) \ge 2$ and $\ew(G^*) \ge k$ satisfies $\phic(G) \le 4$. %Luis: Robertson refers to face-width, but this is equivalent % (via dual chimneys), and more in the spirit of this paper We must have $k\ge4$ here because of Example~\ref{eg:P}. Gr\"unbaum \cite{Gr69} has conjectured that $k=3$ suffices here, provided that $\surf$ is orientable. %Luis: relevant but too embarrassingly easy in this special case %It has been proved \cite{GGH} that, for any fixed $\surf$ and $\epsilon >0$, %we have $\phic(G) \le 2+\epsilon$ for any $\surf$-embedded graph %$G$ with large enough cogirth. If $\surf$ is orientable, then all results and conjectures regarding flows may be restated in terms of the local chromatic number. For example, the above conjectures of Tutte and Gr\"unbaum attractively specialize. % \begin{conjecture} \label{conj:orientable upper bounds} Let $G$ be an $\surf$-embedded graph where $\surf$ is orientable. \renewcommand{\theenumi}{{\rm \alph{enumi}}} \begin{enumerate} \item If $\girth(G) \ge 2$, then $\chiloc(G) \le 5$. \item If $\girth(G) \ge 3$, then $\chiloc(G) \le 4$. \item If $\girth(G) \ge 4$, then $\chiloc(G) \le 3$. \end{enumerate} \end{conjecture} % When $\surf$ is not orientable, these conjectured upper bounds on $\chiloc$ must be weakened. Bouchet \cite{Bo} conjectures that every loopless $\surf$-embedded graph $G$ satisfies $\chiloc(G) \le 6$. DeVos \cite{De} proved that such graphs satisfy $\chiloc(G) \le 12$. This is in contrast to the fact there exists no general bound on $\chic(G)$. DeVos [private communication] has proposed that Bouchet's conjecture can be improved to $\chiloc(G) \le 5$ provided $\ew(G) \ge k$ for some absolute constant~$k$ (possibly $k=4$). Again, Example~\ref{eg:P} shows this is false when $k=3$. It is possible that these conjectured upper bounds can be further tightened by imposing an edge-width requirement on~$G$. Ringel's map color theorem \cite{Ring} asserts that the best upper bound on $\chic(G)$ among loopless $\surf$-embedded graphs is of order $\Theta(g^{1/2})$ where $g$ denotes the genus of $\surf$. Upper bounds on $\chic(G)$ for loopless $\surf$-embedded graphs must depend on the genus also when we consider graphs of any given girth. However, the situation changes for `locally planar' graphs. We state together four relevant results. \begin{theorem} \label{thm:upper bounds} For any surface $\surf$ there exists an integer $M$ such that for any $\surf$-embedded graph with $\ew(G) \ge M$ we have all of the following. \begin{enumerate} \renewcommand{\theenumi}{{\rm \alph{enumi}}} \item If $\girth(G) \ge 2$, then $\chic(G) \le 5$. \item If $\girth(G) \ge 4$, then $\chic(G) \le 4$. \item If $\girth(G) \ge 5$, then $\chic(G) \le 3$. \end{enumerate} \end{theorem} Statements~(a) and~(c) were proved by Thomassen \cite{Th5, Th1}. Statement~(b) was proved by Fisk and Mohar \cite{FM}. Weaker versions of statement~(c), requiring that $\girth(G) \ge 6$, appear in~\cite{FM,GT,Hu}. However, the proof in~\cite{FM} only requires that $M=O(\log(\mbox{\textrm{genus}}(\surf)))$, whereas Thomassen's proofs require at least exponential edge-width. %Luis: put together two sentences. %If $G$ is a graph of girth $t$, then every embedding of $G$ has edge-width %at least $t$. Since there are graphs of arbitrarily large chromatic number %and girth \cite{Er}, Since there are graphs of arbitrarily large chromatic number and girth~\cite{Er}, and since embedded graphs~$G$ satisfy $\ew(G) \ge \girth(G)$, %% the bound $M$ in Theorem~\ref{thm:upper bounds} must depend on the genus of $\surf$. Examples~\ref{eg:QH} and~\ref{eg:T} show that none of the bounds in Theorem~\ref{thm:upper bounds} can be improved even fractionally for general surfaces $\surf$. In fact these examples satisfy $\chiloc(G) = \chic(G)$, so we can not improve Theorem~\ref{thm:upper bounds} even with $\chic(G)$ replaced by $\chiloc(G)$. However, if $\surf$ is orientable, Theorem~\ref{thm:chilt} offers two possible improvements. Gr\"unbaum's Conjecture~\ref{conj:orientable upper bounds}(b) would imply that all loopless graphs embedded on a fixed orientable surface with sufficiently high edge-width satisfy $\chic(G) \le 4+\epsilon$. Such a result would be best possible because of the Fisk triangulations (Example~\ref{eg:F}). The truth of Conjecture~\ref{conj:orientable upper bounds}(c) would further improve this bound to $\chic(G) \le 3+\epsilon$ provided, additionally, that $G$ is triangle-free. \section{Background and Definitions} \label{sect:def} Again, all graphs considered in this paper are finite and directed with possible multiple edges and loops. Loops are understood to be directed, with an outgoing and an incoming end incident with the same vertex. A \DEF{walk} in $G$ refers to a walk in the undirected graph which underlies $G$. A \DEF{circuit} of $G$ is a nontrivial simple closed walk in $G$. As usual, the origin and direction of a circuit are often irrelevant. We assume basic knowledge about (2-cell) embeddings of graphs in surfaces, cf.~\cite{MT}. However, we shall use a slightly less standard treatment of embedded graphs where each edge and each face is oriented. An \DEF{embedded graph} $G$ is a triple $(V(G),E(G),F(G))$ where $(V(G),E(G))$ is a connected directed graph and $F(G)$ is a finite set of \DEF{faces}. Associated with every face $R \in F(G)$ is a \DEF{boundary walk} of~$R$, which is a list $v_0,e_1,v_1,\ldots,e_k,v_k$ of vertices and edges such that $v_0 = v_k$ and such that $v_{i-1}$ and $v_i$ are the endpoints of the edge $e_i$ for every $1 \le i \le k$. We say that the face $R$ has \DEF{length} $k$, and that $R$ is \DEF{incident} with each vertex and edge in its boundary walk. The \DEF{boundary} of $R$ is just the boundary walk of $R$, but without specific reference to the direction or origin of the walk. There are two conditions that the set of face boundaries should satisfy. First, every edge occurs precisely twice overall among the boundaries of all of the faces, either once in two distinct boundaries, or twice in one. Two edges $e$ and $f$ are \DEF{consecutive} at $v$ if either $e,v,f$ or $f,v,e$ is a consecutive subsequence of some boundary walk. The second requirement is that for each vertex $v$, the edges incident with $v$ can be enumerated $e_1,e_2,\dots,e_d$ in such a way that $e_i$ and $e_{i+1}$ (index modulo~$d$) are consecutive at $v$ for $i=1,\dots,d$. This cyclic order is called the \DEF{local rotation} at $v$. For every embedded graph $G$, we construct a topological space denoted by $|G|$ as follows. If $R$ is a face with boundary walk $v_0,e_1,v_1,\ldots,e_k,v_k$, then $R$ is associated with a regular $k$-gon $\pi(R) \subseteq \RR^2$. The vertices and edges of $\pi(R)$ correspond to those in the boundary of $R$. We call the $i$th edge of $\pi(R)$ a \DEF{copy} of $e_i \in E(G)$. We obtain $|G|$ from the disjoint union of these polygons by identifying both copies of every edge $e \in E(G)$ according to their orientations. Because of the local rotation condition, the topological space $|G|$ is a compact connected 2-manifold without boundary, which is hereafter called a \DEF{surface}. Each vertex of $G$ is associated with a point in $|G|$, and each edge of $G$ is associated with an arc in $|G|$. By deleting from $|G|$ the interior of $\pi(R)$ for some $R\in F(G)$, one obtains an embedding of $G$ on a closed \DEF{bordered} surface which we denote $|G|-R$. For any surface $\surf$, we say that $G$ is \DEF{$\surf$-embedded} if $|G|$ is homeomorphic to $\surf$. For every vertex $v \in V(G)$ and edge $e \in E(G)$, we define: \[ \langle v,e \rangle = \left\{ \begin{array}{rl} 0 & \mbox{if $v$ and $e$ are not incident} \\ -1 & \mbox{if $v$ is the tail of $e$} \\ 1 & \mbox{if $v$ is the head of $e$.} \end{array} \right. \] If $W=v_0,e_1,v_1,\ldots,e_k,v_k$ is a walk of $G$, then we define \[ \langle e,W \rangle = \sum_{ \{ 1 \le i \le k \mid e = e_i \} } \langle v_i, e_i \rangle. \] We say that $e$ is a \DEF{forward edge} of $W$ if $\langle e,W \rangle > 0$, and that $e$ is a \DEF{backward edge} of $W$ if $\langle e,W \rangle < 0$. If $W$ is the boundary walk of a face~$R$, then a \DEF{forward edge} of $R$ is a forward edge of $W$, and we write $\langle e,R \rangle$ instead of $\langle e,W \rangle$. In this case we have $\langle e,R \rangle \in \{-2, -1, 0, 1, 2\}$, %where $\langle e,R \rangle \in \{-2,2\}$ if where $\langle e,R \rangle \in \{-2,0,2\}$ if $e$ appears twice in the boundary of $R$. Next, we define the function $\tau: E(G) \rightarrow \ZZ$ by the following rule: \[ \tau(e) = \frac{1}{2} \sum_{R \in F(G)} \langle e,R \rangle. \] Note that $\tau(e) \in \{-1,0,1\}$ for every $e \in E(G)$. Further, $\tau(e) = 1$ if $e$ is a forward edge of two (not necessarily distinct) faces, $\tau(e) = -1$ if $e$ is a backward edge of two faces, and $\tau(e) = 0$ if $e$ is forward in one face and backward in another. Based on this, we define the \DEF{sign} of $G$ to be the map $\sigma : E(G) \rightarrow \ZZ$ given by the rule \[\sigma(e) = (-1)^{\tau(e)}.\] The notion of the sign is equivalent to what is known as the \DEF{signature} of the dual graph (cf., e.g., \cite{MT}). Figure~\ref{fig:4} may help the reader with these definitions. \begin{figure}[htb] \epsfxsize=11.5truecm \centeredgraphics{DGMVZ4.eps} \caption{Effect of edge and face orientations on $\tau$ and $\sigma$.} \label{fig:4} \end{figure} For any embedded graph $G$, we may obtain a new embedded graph by \DEF{reversing} an edge $e \in E(G)$. This has the effect of changing the signs of $\langle v,e \rangle$, $\langle e,R \rangle$ and~$\tau(e)$ (for $R \in F(G)$ and $v \in V(G)$), but has no effect on $\sigma(e)$ and~$|G|$. An \DEF{edge-reorientation} of $G$ is any graph obtained from~$G$ by reversing a subset of $E(G)$. % Similarly, we may obtain a new embedded graph by \DEF{reversing} the boundary of a face $R$. This involves replacing the boundary walk of $R$ by its reverse. Reversing the boundary of $R$ changes $\langle e,R \rangle$ to $- \langle e,R \rangle$ for every $e \in E(G)$ and changes $\sigma(e)$ to $-\sigma(e)$ for every edge $e$ with $\langle e,R \rangle = \pm 1$. This change has no effect on $|G|$. %Luis: I distinguish the two types of reorientation throughout An \DEF{face-reorientation} of $G$ is any graph obtained from~$G$ by reversing a subset of $F(G)$. We say that $|G|$ is \DEF{orientable} if the function $\sigma$ may be changed into the constant $1$ map by some face-reorientation of $G$. Although edge and face orientations are essential for our definitions, all of our results will be independent of these orientations. The surface classification theorem states that every surface is homeomorphic to exactly one of $\S_i$ or $\N_j$, where~$i\ge 0$ and~$j \ge 1$. The value of~$i$ or~$j$ (the \DEF{genus}) indicates the number of handles ($\S_i$) or crosscaps ($\N_j$) that must be added to a sphere to obtain the surface. We have that $|G|$ is orientable if and only if $G$ is $\S_i$-embedded for some $i\ge 0$. We write $\surf = \surf'$ to indicate that $\surf$ and $\surf'$ are homeomorphic surfaces. If $G$ is an embedded graph, we define its \DEF{surface dual} graph $G^*$ which is an unoriented graph embedded in the same surface. The vertices of $G^*$ are the faces of $G$. For every $e \in E(G)$ there corresponds an (unoriented) edge $e^* \in E(G^*)$ connecting the two (possibly identical) faces $R,R' \in V(G^*)$ whose boundaries contain~$e$. The edge $e^*$ is drawn in the natural way on the surface. Face boundary walks in $G^*$ correspond to local rotations at vertices of $G$, and vice versa. A sequence $\omega = R_0e_1R_1e_2\dots R_{k-1}e_kR_k$ of faces and edges of $G$ is called a \DEF{\faceordual walk} of~$G$ provided that $R_0e_1^*R_1e_2^*\dots R_{k-1}e_k^*R_k$ is a walk in~$G^*$. We say that $\omega$ is \DEF{closed} if $R_k = R_0$, and is \DEF{simple} if $R_i \ne R_j$ for $0 \le i < j < k$. A closed \faceordual walk~$\omega$ is \DEF{one-sided} if $\prod_{i=1}^k \sigma(e_i) =-1$. Otherwise, $\omega$ is \DEF{two-sided}. A two-sided simple closed \faceordual walk $\omega$ in~$G$ corresponds to the topological cylinder $\cup_{R \in F(\omega)} \pi(R)$ in~$|G|$, whereas one-sided simple closed \faceordual walks correspond to M\"obius bands. Let us observe that $|G|$ is orientable if and only if every simple closed \faceordual walk of $G$ is two-sided, cf.~\cite{MT}. Let $G$ be a directed graph or an embedded graph, and let $\Gamma$ be an additive abelian group. A $0$-\DEF{chain} (with respect to $\Gamma$) is a map from $V(G)$ to $\Gamma$, a $1$-\DEF{chain} (with respect to $\Gamma$) is a map from $E(G)$ to $\Gamma$, and a $2$-\DEF{chain} (with respect to $\Gamma$) is a map from $F(G)$ to $\Gamma$. For $i=0,1,2$, the $i$-chains form a group under componentwise addition, which we denote by $C_i(G,\Gamma)$. If $c \in C_0(G,\Gamma)$, then we define the \DEF{coboundary} of $c$ to be the map $\delta c \in C_1(G,\Gamma)$ given by the rule $\delta c (e) = \sum_{v \in V(G)} \langle v,e \rangle c(v)$. If $c \in C_1(G,\Gamma)$, then we define the \DEF{coboundary} of $c$ to be the map $\delta c \in C_2(G,\Gamma)$ given by the rule $\delta c (R) = \sum_{e \in E(G)} \langle e,R \rangle c(e)$. % If $c \in C_1(G,\Gamma)$, then we define the \DEF{boundary} of $c$ to be the map $\partial c \in C_0(G,\Gamma)$ given by the rule $\partial c (v) = \sum_{e \in E(G)} \langle v,e \rangle c(e)$. If $c \in C_2(G,\Gamma)$, then we define the \DEF{boundary} of $c$ to be the map $\partial c \in C_1(G,\Gamma)$ given by the rule $\partial c (e) = \sum_{R \in F(G)} \langle e,R \rangle c(R)$. If $c^1$ is a $1$-chain and $c^1 = \delta c^0$ for some 0-chain $c^0$, then we call $c^1$ a \DEF{tension} or a $\Gamma$-\DEF{tension}. If $\partial c^1 = 0$ then we call $c^1$ a \DEF{flow} or a $\Gamma$-\DEF{flow}. If $G$ is an embedded graph and $\delta c^1 = 0$, then we call $c^1$ a \DEF{local tension} or a \DEF{local $\Gamma$-tension}. If $c^1 = \partial c^2$ for some $c^2 \in C_2(G,\Gamma)$ then we call $c^1$ a \DEF{facial flow} or a \DEF{facial $\Gamma$-flow}. Of particular interest is the additive group of the reals $\RR$, because real valued tensions, local tensions and flows are used to define the invariants $\chic$, $\chiloc$ and $\phic$. We denote the set of tensions, local tensions, flows, and facial-flows by $\mathcal T(G,\Gamma)$, $\mathcal L(G,\Gamma)$, $\mathcal F(G,\Gamma)$, and $\mathcal K(G,\Gamma)$, respectively. Note that all four of these sets are subgroups of $C_1(G,\Gamma)$. Further, $\delta \delta c = 0$ for every $0$-chain $c$ and $\partial \partial c = 0$ for every $2$-chain $c$, so $\mathcal T(G,\Gamma)$ is a subgroup of $\mathcal L(G,\Gamma)$ and $\mathcal K(G,\Gamma)$ is a subgroup of $\mathcal F(G,\Gamma)$. Let $\phi \in C_1(G,\Gamma)$, let $d \in C_1(G,\ZZ)$, and let $g \in \Gamma$. We define $ g d \in C_1(G,\Gamma)$ and $d \cdot \phi \in \Gamma$ by the following rules: \begin{eqnarray*} (g d) (e) & = & d(e) g\,, \\[1mm] d \cdot \phi & = & \sum_{e \in E(G)} d(e) \phi(e). \end{eqnarray*} The following arises from the definitions. % \begin{proposition} \label{prop:orth} \samepage{ \ \begin{enumerate} \renewcommand{\theenumi}{{\rm \alph{enumi}}} \item $\mathcal T(G,\Gamma) = \{ \phi \in C_1(G,\Gamma) \mid \mbox{$d \cdot \phi = 0$ for every $d \in \mathcal F(G,\ZZ)$} \}$. \item $\mathcal L(G,\Gamma) = \{ \phi \in C_1(G,\Gamma) \mid \mbox{$d \cdot \phi = 0$ for every $d \in \mathcal K(G,\ZZ)$} \}$. \end{enumerate} } \end{proposition} For any embedded graph $G$, the function $\tau \in C_1(G,\ZZ)$ plays an important role. By its definition, $2\tau$ is an integer sum of facial flows of the form $e \mapsto \langle e,R \rangle$. In particular, $\tau$ is an integer valued member of $\mathcal F(G,\RR)$. Since the space of integer flows $\mathcal F(G,\ZZ)$ is a \DEF{regular chain group} (cf. Tutte \cite{Tu56}), it follows that \begin{equation} \label{eq:tau} \tau \in \mathcal F(G,\ZZ) \mbox{\quad and \quad} 2\tau \in \mathcal K(G,\ZZ). \end{equation} We define the \DEF{homology group} $H_1(G,\Gamma)$ to be $\mathcal F(G,\Gamma) / \mathcal K(G,\Gamma)$ and we define the \DEF{cohomology group} $H^1(G,\Gamma)$ to be $\mathcal L(G,\Gamma) / \mathcal T(G,\Gamma)$. These groups depend only on~$|G|$ and not on the particular structure of the graph (see, e.g.\ \cite{Giblin,GH81}), so for a surface~$\surf$ one can define $H_1(\surf,\Gamma)$ ($H^1(\surf,\Gamma)$) to be the homology (cohomology) group of some (and hence any) $\surf$-embedded graph. The group $H^1(G,\Gamma)$ may be viewed as a measure of the difference between the spaces of local tensions and tensions of $G$. The point of this paper is to show that under the right circumstances, it is possible to change a local tension of an embedded graph to a tension by `small adjustments' on each edge. As such, the cohomology group $H^1(G,\Gamma)$ plays a key role. For any abelian group $\Gamma$, we let $\Inv(\Gamma)$ denote the subgroup of $\Gamma$ consisting of the elements of order at most $2$. Then the cohomology groups of the surfaces are (cf., e.g.,~\cite{GH81}): $$ H^1(\S_i,\Gamma) \cong \Gamma^{2i} \qquad \hbox{and} \qquad H^1(\N_j,\Gamma) \cong \Gamma^{j-1} \times \Inv(\Gamma). $$ In particular, any graph $G$ embedded in $\N_1$ satisfies $\mathcal L(G,\Gamma) / \mathcal T(G,\Gamma) \cong \Inv(\Gamma)$. Thus we have the following. \begin{proposition} \label{ppTensions} Let $G$ be an $\N_1$-embedded graph, and let $\Gamma$ be an abelian group. Then every local\/ $\Gamma$-tension on $G$ is a $\Gamma$-tension on $G$ if and only if\/ $\Inv(\Gamma) = \{ 0 \}$. \end{proposition} % Observing that $\Inv(\RR) = \{ 0 \}$, we have the following. % \begin{corollary} \label{cor:chiloc=chic} For any graph $G$ embedded on the sphere or projective plane we have $\chiloc(G) = \chic(G)$. \end{corollary} %% %This fails (cf.\ Example~\ref{eg:chic>chiloc}) for graphs on other surfaces. % Bojan: That example has been removed. It is worth mentioning that on all other surfaces there exist graphs with arbitrarily large edge-width satisfying $\chiloc(G) < \chic(G)$. We will use Proposition \ref{prop:orth} to detect if a local tension is a tension, so the homology group $H_1(\surf,\ZZ)$ also plays a role in our argument. It is well-known \cite{Giblin,GH81} that $$ H_1(\S_i,\ZZ) \cong \ZZ^{2i} \qquad \hbox{and} \qquad H_1(\N_j,\ZZ) \cong \ZZ^{j-1} \times \ZZ / 2\ZZ. $$ %Luis adds In particular, $\Inv(H_1(\surf,\ZZ))$ is trivial if and only if $\surf$ is orientable. For any $\surf$-embedded graph $G$ and any flow $\psi \in \mathcal F(G,\ZZ)$, let $\langle \psi \rangle$ denote the coset $\psi + \mathcal K(G,\ZZ) \in H_1(G,\ZZ)$. This coset is called the \DEF{homology class} of $\psi$. Thus $\langle 0 \rangle$ is the set of facial $\ZZ$-flows in $G$. We have from (\ref{eq:tau}) that $\langle\tau\rangle \in \Inv(H_1(G,\ZZ))$. Thus $\tau \in \mathcal K(G,\ZZ)$ if $\surf$ is orientable. Conversely, if $\tau \in \mathcal K(G,\ZZ)$, then one can transform $\tau$ to be identically zero by reversing some faces of $G$, so $\surf$ is orientable. Thus %for any embedded graph $G$ we have \begin{equation} \label{eq:InvH_1} \Inv(H_1(G,\ZZ)) = \left\{ \begin{array}{ll} \{\langle 0 \rangle\} &\mbox{if $|G|$ is orientable}\\ \{\langle 0 \rangle,\langle \tau \rangle\}&\mbox{if $|G|$ is not orientable.} \end{array}\right. \end{equation} %% For certain groups $\Gamma$, it is not true that every local $\Gamma$-tension can be modified to a $\Gamma$-tension by means of `small adjustments'. In Section~\ref{sect:families} we offer an example illustrating this. In Theorem \ref{thm:main} we show that such an adjustment \emph{is} possible provided the local tension satisfies an additional property. A local $\Gamma$-tension $\phi$ is \DEF{strong} if it satisfies %Luis: no need to label, nor to expand the sum, $$ \tau \cdot \phi = 0. $$ Let $\mathcal L^+(G,\Gamma)$ denote the set of strong local $\Gamma$-tensions of~$G$. In view of Proposition~\ref{prop:orth}(b) we see that $\mathcal L^+(G,\Gamma)$ is the subgroup of $\mathcal L(G,\Gamma)$ defined by \begin{equation} \label{eq:sltFormula} \mathcal L^+(G,\Gamma) = \{ \phi \in C_1(G,\Gamma) \mid \mbox{$d \cdot \phi = 0$ for every $d \in \{\tau\}\cup\mathcal K(G,\ZZ)$}\}. \end{equation} Of course one may substitute for `$\tau$' in~(\ref{eq:sltFormula}) any other element of the homology class~$\langle \tau \rangle$. Consequently, the definition of `strong' does not depend on a particular face orientation of~$G$. % If $\phi$ is a local $\Gamma$-tension of $G$, then from~(\ref{eq:tau}) we have $ 2(\tau \cdot \phi) = (2\tau) \cdot \phi = 0$. Thus $\tau \cdot \phi \in \Inv(\Gamma)$. Using this, the following is easily proved. % \begin{proposition} \label{prop:slt} If\/ $|G|$ is orientable or $\Inv(\Gamma)=\{0\}$, then $\mathcal L^+(G,\Gamma) = \mathcal L(G,\Gamma)$. In particular, every local\/ $\RR$-tension is a strong local\/ $\RR$-tension. \end{proposition} % The group containment relations are \[ \mathcal T(G,\Gamma) \leq \mathcal L^+(G,\Gamma) \leq \mathcal L(G,\Gamma) \] with $\mathcal L(G,\Gamma) / \mathcal L^+(G,\Gamma) \cong \Inv(\Gamma)$. % Like the cohomology group, the quotient group $H^+(G,\Gamma) = \mathcal L^+(G,\Gamma) / \mathcal T(G,\Gamma)$ depends only on the surface $|G|$. % and not on the structure of the graph. So, for a surface $\surf$, we define $H^+(\surf,\Gamma)$ to be $H^+(G,\Gamma)$ for any $\surf$-embedded graph~$G$. In comparison with the cohomology groups, we have $$ H^+(\S_i,\Gamma) \cong \Gamma^{2i} \qquad \hbox{and} \qquad H^+(\N_j,\Gamma) \cong \Gamma^{j-1}. $$ Let $G$ be an embedded graph. For any walk $W$ in $G$ we define the \DEF{walk indicator} map $I_W \in C_1(G,\ZZ)$ by the rule $$ I_W(e) = \langle e, W \rangle . $$ If $W$ is a closed walk, then $I_W \in \mathcal F(G,\ZZ)$. If, additionally, $W$ is a contractible curve on~$|G|$, then $I_W \in \mathcal K(G,\ZZ)$ is a facial flow. % If $I_W \notin \mathcal K(G,\ZZ)$, but $2I_W \in \mathcal K(G,\ZZ)$, then we say that $W$ is a \DEF{semifacial walk}. By~(\ref{eq:tau}) and~(\ref{eq:InvH_1}) of Section~\ref{sect:def}, $W$ is semifacial if and only if $|G|$ is not orientable and $\langle I_W \rangle = \langle\tau\rangle$. If $W$ is semifacial, then so is its reverse, so we may speak of a semifacial walk without reference to its orientation. A circuit $C$ is semifacial if and only if there is some face-reorientation of~$G$ so that $\tau(e)$ is nonzero (or $\sigma(e)$ is negative) exactly on the edges $e$ of $C$. Deleting from $|G|$ the closed arcs corresponding to the edges of a semifacial circuit results in an orientable (bordered) surface. Let $\phi \in C_1(G,\Gamma)$. A closed walk $W$ is \DEF{conservative for $\phi$} if $I_W \cdot \phi = 0$. Let~$Y$ be a set of closed walks in $G$. We say that $Y$ {\it generates} $H_1(G,\ZZ)$ if $\{ \langle I_W \rangle \mid W \in Y \}$ generates $H_1(G,\ZZ)$. % The following allows one to test whether a local $\Gamma$-tension is strong, and whether it is a tension. % \begin{proposition} \label{prop:conservative} Let $\phi \in \mathcal L(G,\Gamma)$. {\rm (i)} If $W$ is a semifacial walk in $G$, then $\phi \in \mathcal L^+(G,\Gamma)$ if and only if~$W$ is conservative for $\phi$. {\rm (ii)} If\/ $Y$ is a set of closed walks that generates $H_1(G,\ZZ)$, then $\phi \in \mathcal T(G,\Gamma)$ if and only if every member of\/ $Y$ is conservative for $\phi$. \end{proposition} \begin{proof} Part (i) follows immediately from equation (\ref{eq:InvH_1}) and the comment after (\ref{eq:sltFormula}) in Section~\ref{sect:def}. Part (ii) follows from Proposition \ref{prop:orth}(a). \end{proof} We define now a class of `elementary' strong local tensions, which will be used to prove the main theorem. Let $\omega = R_0,e_1,R_1,\ldots,e_k,R_0$ be a simple closed \faceordual walk in an embedded graph $G$. Suppose $\omega$ is two-sided, and thus corresponds to a cylinder in~$|G|$. Then $\omega$ corresponds to a circuit $\omega^*$ in $G^*$. Using a fixed orientation of the cylinder (which is an orientable bordered surface), we orient the edges of~$\omega^*$ consistently with $\omega$ according to the left-to-right rule. We define a map $\Omega_\omega \in C_1(G, \ZZ)$ according to the rule $$ \Omega_\omega(e) = \left\{ \begin{array}{ll} I_{\omega^*}(e^*) & \mbox{if $e \in E(\omega)$} \\ 0 & \mbox{otherwise,} \end{array} \right. $$ where $I_{\omega^*}$ is the $\{0,\pm 1\}$-valued indicator function of $\omega^*$. By definition we have, for any face $R \in F(G)$, that $ I_R \cdot \Omega_\omega = 0. $ Therefore $\Omega_\omega \in \mathcal L(G,\ZZ)$ by Proposition~\ref{prop:orth}(b). It is possible to reorient the faces of $\omega$ so that $\tau(e) = 0$ for every $e \in E(\omega)$. For this face-reorientation we have $\tau \cdot \Omega_\omega=0$. In view of~(\ref{eq:sltFormula}), we have shown the following. % \begin{proposition} \label{prop:cylinder} If\/ $\omega$ is a simple closed two-sided \faceordual walk in an embedded graph~$G$, then $g \Omega_\omega \in \mathcal L^+(G,\Gamma)$ for every $g \in \Gamma$. \end{proposition} \section{From strong local tensions to tensions} \label{sect:proof} The goals of this section are to prove the following general result, and then to prove its main application, Theorem~\ref{thm:chilt}. % Let $\Gamma$ be an additive abelian group. If $Q \subseteq \Gamma$, and $k$ is a positive integer, then we let $kQ = \sum_{i=1}^k Q$. We say that $Q$ is a $k$-\DEF{part} of $\Gamma$ if $0 \in Q$, $Q = -Q$, and $kQ = \Gamma$. \begin{theorem} \label{thm:main} Let\/ $\surf$ be a surface and let $k$ be a positive integer. Then there exists an integer $M$ such that for every $\surf$-embedded graph $G$ with $\ew(G) \ge M$, every abelian group\/ $\Gamma$, every $k$-part\/ $Q$ of\/ $\Gamma$, and every $\phi \in \mathcal L^+(G,\Gamma)$, there is a $\phi' \in \mathcal T(G,\Gamma)$ with $\phi(e)-\phi'(e) \in 2Q$ for every $e \in E(G)$. \end{theorem} We shall require the notion of a surface minor. Let $G$ be an embedded graph, let $e \in E(G)$ have ends $u,v$, and let $R_1,R_2$ be the faces incident with $e$. If $e$ is not a loop, then we let $G / e$ denote the embedded graph obtained from~$G$ by identifying $u$ and $v$ to a single new vertex, say $w$, removing $e$ from $E(G)$, and replacing occurrences of $v,e,u$ or $u,e,v$ in the boundary walks of $R_1$ and $R_2$ by $w$. We say that $G / e$ is obtained from~$G$ by \DEF{contracting} the edge $e$. If $e$ occurs in the boundary of distinct faces $R_1$ and $R_2$, and $\sigma(e) = 1$, then we let $G \setminus e$ denote the embedded graph obtained from $G$ by removing $e$ from $E(G)$, and identifying $R_1$ and $R_2$ in a natural way to a single new face whose boundary orientation is inherited from $R_1$ and $R_2$. We say that $G \setminus e$ is obtained from $G$ by \DEF{deleting} the edge $e$. Any embedded graph $H$ obtained from $G$ by a sequence of switching orientations of edges and faces, deleting and contracting edges is called a \DEF{surface minor} of $G$. A surface minor of~$G$ which can be obtained by only deleting edges and switching orientations of edges and faces is called a \DEF{surface subgraph} of~$G$. When making a surface subgraph, we allow one other special operation: one may contract an edge provided that one of its ends is a vertex of degree one. The reader may observe that our definition of a surface minor seems more restrictive than the usual one. For example, if $e$ is an edge incident with two distinct faces, then we cannot delete $e$ if $\sigma(e)=-1$. This type of restriction is inessential as we may simply switch the orientation of a face incident with $e$ first and then delete $e$. The second difference is that we are neither permitted to delete an edge which is incident with only one face, nor dually, to contract a loop. However, these are standard assumptions to avoid degeneracies. We define the \DEF{face-width} of $G$, written $\fw(G)$, to be the minimum cardinality of the point set $G \cap C$ among all noncontractible curves $C$ in $|G|$. It is easy to see that $\fw(G) \le \ew(G)$. We shall first prove that Theorem~\ref{thm:main} holds for graphs of high face-width. Later, we describe a reduction that extends the result to graphs of high edge-width. \begin{theorem}[Robertson and Seymour \cite{GM7}] \label{RS} For every $\surf$-embedded graph $H$, there exists an integer $M$ such that every $\surf$-embedded graph $G$ with $\fw(G) \ge M$ contains a surface minor isomorphic to $H$. \end{theorem} If $G,H$ are embedded graphs and $H$ can be obtained from $G$ by a sequence of contracting edges incident with vertices of degree $2$, then $G$ is a \DEF{subdivision} of $H$. For $h=1,2,\dots$, let $T_h$ be the $\S_h$-embedded graph which is represented in Figure~\ref{fig:1}(a) for the case $h=3$. The surface is obtained by taking the regular $4h$-gon (called the \DEF{fundamental polygon}) with sides $a_1,b_1,a_1^-,b_1^-, \dots, \allowbreak a_h, b_h, a_h^-, b_h^-$ and identifying each $a_i$ with $a_i^-$ and $b_i$ with $b_i^-$, $i=1,\dots,h$, using the orientations shown in Figure \ref{fig:1}. Similarly, we let $U_h$ be the $\N_h$-embedded graph as shown in Figure \ref{fig:1}(b) for the case $h=6$. For an even value $h=2g+2$, the fundamental polygon has sides $a_1,b_1,a_1^-,b_1^-, \dots, \allowbreak a_g, b_g, a_g^-, b_g^-, c,d,c,d^-$, while for $h=2g+1$, the sides labeled $d$ and $d^-$ are missing: $a_1,\dots, b_g^-, c,c$. Figure \ref{fig:1} also shows a collection of circuits in $T_h$, denoted by $A_1,B_1,\dots,\allowbreak A_h,B_h$, and a collection of circuits in $U_h$, denoted by $A_1,B_1,\dots,\allowbreak A_g,B_g$ and $C$ (and $D$ for $U_{2g+2}$). Since the graphs $T_h$ and~$U_h$ have maximum degree three, any graph which has a $T_h$ or $U_h$ as a surface minor has a surface subgraph which is a subdivision of $T_h$ or $U_h$, respectively. \begin{figure}[htb] \epsfxsize=11.5truecm \centeredgraphics{DGMVZ1.eps} \caption{Embedded graphs $T_3$ and $U_6$} \label{fig:1} \end{figure} If $Q$ is a circuit of $G / e$, then exactly one of $E(Q)$ or $E(Q) \cup \{e\}$ is the edge set of a circuit $Q'$ in $G$. We say that this circuit $Q'$ {\it corresponds} to $Q$. More generally, if $H$ is a surface minor of $G$ and $Q \subseteq H$ is a circuit, then there is a unique circuit $Q' \subseteq G$ which {\it corresponds} to $Q$. If $Y$ is a collection of circuits of $H$, then we say that $Y' = \{ Q' \subseteq G \mid \mbox{$Q'$ corresponds to some $Q\in Y$} \}$ \DEF{corresponds} to $Y$. We shall regard all these circuits to be simple closed walks so that the terms `semifacial', `conservative' and `generates' defined in Section~\ref{sect:def} apply. \begin{lemma} \label{lem:H_1} Let $G$ be a graph embedded in the surface $\S_h$ $(h\ge1)$ or\/ $\N_r$, where $r\in \{2h+1,2h+2\}$ and $h\ge0$. Suppose that $G$ has a surface subgraph which is a subdivision of $T_h$ or $U_r$, respectively. Let $A_1',B_1',\ldots,\allowbreak A_h',B_h'$ (and $C'$ and $D'$ if applicable) be the circuits of $G$ which correspond to $A_1,B_1,\ldots,\allowbreak A_h,B_h$ (and~$C$ and~$D$ if applicable). Then we have: % \begin{enumerate} \renewcommand{\theenumi}{{\rm \roman{enumi}}} \item $A_1',B_1',\ldots,A_h',B_h'$ (and $C'$ and $D'$ if applicable) generate $H_1(G,\ZZ)$. \item If $|G| = \N_{2h+1}$, then $C'$ is semifacial; if $|G| = \N_{2h+2}$, then $D'$ is semifacial. \end{enumerate} \end{lemma} \begin{proof} %Luis: elaborated a bit Part (i) follows by construction. Indeed these circuits minimally generate the free homotopy group $\pi_1(|G|)$. For part (ii), suppose $\surf = \N_{2h+2}$. We observe from Figure~\ref{fig:1}(b) that we may reorient the faces of $G$ so that an edge $e \in E(G)$ has %$\sigma(e) = -1$ $\tau(e) = \pm 1$ if and only if $e \in E(D')$, so $I_{D'}$ belongs to the homology class $\langle \tau \rangle$. In case $\surf = \N_{2h+1}$, the argument is similar, but with~$D'$ replaced by~$C'$. \end{proof} Next we define two families of embedded graphs, $T_h^k$ and $U_h^k$ ($h\ge1$, $k\ge1$) as follows. We start with the embedded graph $T_h$ or $U_h$. Let $g=h$ for $T_h$ and $g=\lfloor (h-1)/2\rfloor$ for $U_h$. Then we add, for $i=1,\dots,g$, two families of $k+1$ pairwise disjoint circuits of length $k+3$ each (as shown in Figure \ref{fig:2}) such that each circuit from the first family and each circuit from the second family intersect once. In the case of $U_h$, where $h=2g+2$ is even, we add one additional family of $k+1$ disjoint circuits, each of length 2. See Figure \ref{fig:2}. \begin{figure}[htb] \epsfxsize=6truecm \centeredgraphics{DGMVZ2.eps} \caption{Embedded graph $U_6^3$ and some \faceordual walks} \label{fig:2} \end{figure} \begin{lemma} \label{lem:face walk} Let $k\ge 1$ be an integer. Let\/ $G$ be a graph embedded in the surface $\surf = \S_h$ with $h\ge1$, or in $\surf = \N_r$, where $r\in\{2h+1,2h+2\}$ and $h\ge0$. Suppose that $G$ contains $T_h^k$ (or $U_r^k$, respectively) as a surface minor. Let $A_1',B_1',\ldots,\allowbreak A_h',B_h'$ (and~$C'$ if\/ $\surf=\N_{2h+1}$, and $C',D'$ if\/ $\surf=\N_{2h+2}$) be the circuits of $G$ which correspond to $A_1,B_1,\ldots,\allowbreak A_h,B_h$ (and~$C$ and~$D$ if applicable). Let $P = \bigcup_{i=1}^h (E(A_i') \cup E(B_i')) \cup E(C') \cup E(D')$ (where $E(C')$ and $E(D')$ are added only when applicable). Then there exist in $G$ simple closed \faceordual walks $\alpha_i^j,\beta_i^j$ (and $\gamma^j$ if\/ $\surf=\N_{2h+2}$) for $1 \le i \le h$ and\/ $1 \le j \le k$ with the following properties: \begin{enumerate} \renewcommand{\theenumi}{{\rm \roman{enumi}}} \item Every face of $G$ occurs in at most two of the \faceordual walks $\alpha_i^j, \beta_i^j, \gamma^j$. \item The \faceordual walks $\alpha_i^j, \beta_i^j, \gamma^j$ are all two-sided. \item $\alpha_i^j$ contains exactly one edge of $A_i'$ and no edges in $P \setminus E(A_i')$. \item $\beta_i^j$ contains exactly one edge of $B_i'$ and no edges in $P \setminus E(B_i')$. \item If $\surf = \N_{2h+2}$, then $\gamma^j$ contains exactly one edge of $C'$ and no edges in $P \setminus E(C')$. \end{enumerate} \end{lemma} \begin{proof} We proceed by induction on $|E(G)|$. The base case is when $G = T_h^k$ or $G = U_r^k$, and here the walks are as indicated in Figure \ref{fig:2}. For the inductive step, contract or delete an edge $e$ of $G$ so that the resulting minor~$G'$ still has $T_h^k$ or $U_r^k$ as a surface minor. By the induction hypothesis, $G'$ has \faceordual walks with the stated properties. If an edge was contracted, then the \faceordual walks of~$G'$ are \faceordual walks of~$G$ with the required properties. If an edge was deleted to form a face $R$, then we adjust each \faceordual walk containing $R$ in the obvious manner. It is easy to verify that the resulting \faceordual walks still satisfy (i)--(v). \end{proof} We are ready to prove the following lemma, which is identical to Theorem~\ref{thm:main} except that edge-width is replaced here by face-width. \begin{lemma} \label{lem:main} Let\/ $\surf$ be a surface and let $k$ be a positive integer. Then there exists an integer $M$, so that for every $\surf$-embedded graph $G$ with $\fw(G) \ge M$, every abelian group $\Gamma$, every $k$-part $Q$ of\/ $\Gamma$, and every $\phi \in \mathcal L^+(G,\Gamma)$, there is a $\phi' \in \mathcal T(G,\Gamma)$ with $\phi(e)-\phi'(e) \in 2Q$ for every $e \in E(G)$. \end{lemma} \begin{proof} We apply Theorem \ref{RS} to find an integer $M$ so that every $\surf$-embedded graph with face-width $\ge M$ contains $T_h^k$ as a minor if $\surf = \S_h$, and so that it contains $U_r^k$ as a minor if $\surf=\N_r$, where $r=2h+1$ or $r=2h+2$. Let $G$ be an $\surf$-embedded graph with $\fw(G) \ge M$, and let $\phi \in \mathcal L^+(G,\Gamma)$. Let $A_1',B_1',\ldots,A_h',B_h'$, (and~$C'$ if $\surf = \N_{2h+1}$, and $C',D'$ if $\surf = \N_{2h+2}$) be the circuits of $G$ which correspond to $A_1,B_1,\ldots,A_h,B_h$ (and $C$ and $D$ if applicable) of $T_h^k$ or $U_r^k$. Choose \faceordual walks $\alpha_i^j$, $\beta_i^j$, (and $\gamma^j$ if $\surf = \N_{2h+2}$) in accordance with Lemma \ref{lem:face walk}. Let $x_i^j,y_i^j,z^j$ be variables in $\Gamma$, for $1 \le i \le h$ and $1 \le j \le k$. Consider the function \[ \phi' = \phi + \sum_{i,j} x_i^j \Omega_{\alpha_i^j} + \sum_{i,j} y_i^j \Omega_{\beta_i^j} + \sum_{j} z_j \Omega_{\gamma^j}, \] disregarding inapplicable terms. It follows from Proposition~\ref{prop:cylinder} that $\phi' \in \mathcal L^+(G,\Gamma)$. Furthermore, by properties (ii)--(v) of Lemma~\ref{lem:face walk} and the assumption that $Q$ is a $k$-part, we may choose $x_i^j$, $y_i^j$, (and $z^j$ if $\surf = \N_{2h+2}$) in $Q$ so that $A_1',B_1',\ldots,A_h',B_h'$ %Luis: Fix - The semifacial walk is C' in one case and D' in the other. % This was the main source of our C', D' confusion before! (and $C'$ if $\surf = \N_{2h+2}$) are all conservative for~$\phi'$. By Lemma~\ref{lem:H_1}(ii) the circuit $C'$ (if $\surf = \N_{2h+1}$), or $D'$ (if $\surf = \N_{2h+2}$) is semifacial. Since $\phi' \in \mathcal L^+(G,\Gamma)$, we have by Proposition \ref{prop:conservative}(i) that $C'$ and $D'$ are conservative for $\phi'$ in these two cases. Applying Lemma \ref{lem:H_1}(i) and Proposition~{\ref{prop:conservative}}(ii) we have that $\phi'$ is a tension as claimed. Finally, it follows from Lemma \ref{lem:face walk}(i) (and the fact that the \faceordual walks are simple) that $\phi'(e) - \phi(e) \in 2Q$ for every $e\in E(G)$. \end{proof} The value of $M$ in the above proof is provided by Theorem~\ref{RS}. Although the paper \cite{GM7} does not provide explicit bounds on $M$, reasonably small bounds can be obtained using results of \cite{BMR} and~\cite{GS94}, see \cite{BCC} for more details. Let $R$ be a face of the embedded graph $G$ whose boundary walk~$C_0$ has length $k \ge 4$. Next we define a graph $H$ embedded %in the same surface as $G$ in~$|G|$ such that~$H$ contains~$G$ as an embedded subgraph and such that the only face of $G$ which is not a face of $H$ is $R$. We start by drawing $k$ nested circuits $C_1,C_2,\ldots,C_k$, each of length $k$, inside the face $R$. For $1 \le i \le k$, we add a perfect matching between the vertices of~$C_{i-1}$ and~$C_i$. The construction is illustrated in Figure \ref{fig:3}. For $1 \le i \le k$, we orient each new matching edge from $C_{i-1}$ to $C_i$, and we orient each edge of $C_i$ to coincide with the corresponding edge on~$C_0$. % We say that this new embedded graph is obtained from $G$ by adding a \DEF{chimney} to $R$. Let us observe that $C_0$ may not be a circuit, but all new faces are bounded by circuits of length either~$4$ or~$k$. The following proposition is easy to verify. \begin{figure}[htb] \epsfxsize=9.2truecm \centeredgraphics{DGMVZ3.eps} \caption{Adding a chimney in a face of length 5} \label{fig:3} \end{figure} \begin{proposition} \label{chimney} Let $G'$ be obtained from an embedded graph~$G$ by adding a chimney to every face of length at least $4$. Then the face-width of~$G'$ is equal to the edge-width of~$G$. %Then $\fw(G') = \ew(G)$. \end{proposition} \noindent{\bf Proof of Theorem \ref{thm:main}:} Let $\surf, k, G, \Gamma, Q$, and $\phi \in \mathcal L^+(G,\Gamma)$ be as stated in the theorem, and let $M$ be the constant of Lemma \ref{lem:main}. We form the embedded graph~$G'$ by adding a chimney to every face of $G$ of length~$\ge 4$. Proposition \ref{chimney} shows that Lemma \ref{lem:main} can be applied to $G'$. Define $\psi \in C_1(G',\Gamma)$ so that $\psi(e) = \phi(e)$ for $e\in E(G)$, and for every chimney, %the edges on $C_1,\dots,C_k$ have each edge of $C_1,\dots,C_k$ has the same value as the corresponding edge on $C_0$, while edges joining $C_{i-1}$ and $C_i$ all have the value $0 \in\Gamma$. Then it is easy to see that $\psi \in \mathcal L^+(G',\Gamma)$. Therefore, we may choose $\psi' \in \mathcal T(G',\Gamma)$ so that $\psi'(e) - \psi(e) \in 2Q$ for every $e \in E(G')$. It now follows that $\phi' = \psi'|_{E(G)}$ is a tension of $G$ with the required properties. %% %Luis: Made to look consistent to ajour.cls style %\hspace{1em}\rule{.6ex}{1.9ex} %Luis: Made to look consistent to trans-l.cls style \hfill$\Box$ Before proving Theorem~\ref{thm:chilt}, we must express $\chic(G)$ in terms of a group which is suited to the application of Theorem~\ref{thm:main}. We consider the \DEF{circle group} $\CG = \RR/\ZZ$. We identify $\CG$ with the half open interval $[0,1)$ in the usual way. For $x \in \CG$, we let $\Vert x\Vert = \min \{ x,1-x \}$. The term `circular chromatic number' is etymologically based on the following formula which appears, for example, in~\cite{Zhu}. \begin{proposition} \label{prop:CG chic} For any graph $G$ we have $$ \frac1{\chic(G)} = \max_{\phi \in \mathcal T(G,\CG)} \min_{e \in E(G)} \Vert \phi(e) \Vert. $$ \end{proposition} % \noindent{\bf Proof of Theorem \ref{thm:chilt}:} Let $k = 5 + \left\lceil \frac{25}{\epsilon} \right\rceil$, and apply Theorem \ref{thm:main} to obtain a positive integer $M_0$ based on the surface $\surf$ and the integer $k$. Let $M = \max ( M_0, M_1 )$ where $M_1$ is the integer supplied by Theorem~\ref{thm:upper bounds}(a). Let $G$ be a loopless graph embedded in $\surf$ with edge-width at least $M$. Define $\alpha = \chiloc(G)$. By the choice of~$M_1$, we have $\alpha \le \chic(G) \le 5$. Let $\psi \in C_1(G,\RR)$ be a local $\alpha$-tension of $G$. Define $\phi \in C_1(G,\CG)$ by the rule $\phi(e) = \psi(e)/\alpha$, so that $\phi(e) \in \left[ \frac{1}{\alpha} , \frac{\alpha-1}{\alpha} \right]$, for $e \in E(G)$. Since $\Inv(\RR) = \{0\}$, Proposition \ref{prop:slt}(b) implies that $\psi$ is a strong local $\RR$-tension. Consequently $\phi$ is a strong local $\CG$-tension. The interval $\left[ -\frac{1}{2k} , \frac{1}{2k} \right]$ is a $k$-part of $\CG$, so by choice of~$M_0$, there exists an $\CG$-tension $\phi'$ such that $\phi(e) - \phi'(e) \in \left[ -\frac{1}{k} , \frac{1}{k} \right]$. Thus $\phi'(e) \in \left[ \frac{1}{\alpha} - \frac{1}{k}, \frac{\alpha-1}{\alpha} + \frac{1}{k} \right]$. By Proposition~\ref{prop:CG chic} we have $\chic(G) \le \left(\frac{1}{\alpha} - \frac{1}{k}\right)^{-1}$. Therefore \[ \chic(G) - \chiloc(G) \le \frac{\alpha k}{k - \alpha} - \alpha = \frac{\alpha^2}{k - \alpha} \le \frac{25}{k-5} \le \epsilon \] as claimed. %\hspace{1em}\rule{.6ex}{1.9ex} %Luis: Made to look consistent to trans-l.cls style \hfill$\Box$ \section{Two families of embedded graphs} \label{sect:families} In this section we study two families of embedded graphs $G$ for which $\chiloc(G)$ exhibits `bimodal' behaviour: even-faced graphs, and triangulations. We characterize the bipartition of each family into odd and even types, and give a proof of Theorem~\ref{thm:bimodality}. When $G$ has large edge-width, we may apply our main theorem to obtain the bimodal behaviour of $\chic(G)$ described in Corollary~\ref{cor:bimodality}. In both applications, we need a way to deduce lower bounds on $\chiloc(G)$. %We use a method pioneered by Minty~\cite{Min}. We use a method based on edge-reorientations. For any closed walk $W$ in a directed graph~$H$, we define the \DEF{imbalance} of $W$ in $H$ to be $$ %\imbal_H(W) = 1 + \max \{ w^+(W)/w^-(W), w^-(W)/w^+(W) \} \imbal_H(W)=1 + \max \left\{ \frac{w^+(W)}{w^-(W)}, \frac{w^-(W)}{w^+(W)} \right\} $$ where % %\textit{ %\begin{eqnarray*} %w^+(W) &=& \sum \{ \langle e,W \rangle \mid \langle e,W \rangle >0 \},\\ %w^-(W) &=& \sum \{ \langle e,W \rangle \mid \langle e,W \rangle <0 \}. %\end{eqnarray*} %% %We allow the value $\imbal_H(W)=\infty$ if one of $w^+(W)$, $w^-(W)$ equals zero. %Suppose~$W$ has $s$ forward edges and $t$ backward edges, %where $W$ has length $s+t$. %Then %\begin{equation} %\label{eq:imbal approx} %\imbal_H(W) \ge \frac{s+t}{\min(s,t)} %\end{equation} %with equality holding if and only if no edge in $H$ is traversed %at least once in each direction. %} % \begin{eqnarray*} w^+(W) &=& \sum \{ \langle e,W \rangle \mid \langle e,W \rangle >0 \},\\ w^-(W) &=& \sum \{ - \langle e,W \rangle \mid \langle e,W \rangle <0 \}. \end{eqnarray*} % We allow the value $\imbal_H(W)=\infty$ if one of $w^+(W)$, $w^-(W)$ equals zero. Suppose~$W = v_0 e_1 v_1 \ldots e_k v_k$ has $s$ indices $i$ for which $e_i$ is a forward edge in $W$, and let $t=k-s$. Then for some $c \ge 0$ we have $s=w^+(W)+c$ and $t=w^-(W)+c$. Therefore, one can approximate \begin{equation} \label{eq:imbal approx} \imbal_H(W) \ge \frac{s+t}{\min(s,t)} \end{equation} with equality holding if and only if no edge in $H$ is traversed at least once in each direction. % It was first observed by Minty \cite{Min} that $\chi(G)$ can be expressed in terms of circuit imbalance. The following analogous result for~$\chic(G)$ appears in~\cite{GTZ}. % \begin{theorem} \label{thm:minty} For any graph $G$ we have % \begin{equation} \label{eq:minty} \chic(G) = \min_H \: \max_W \: \imbal_H(W), \end{equation} % where $H$ ranges over all edge-reorientations of $G$, and~$W$ ranges over the circuits in~$H$. \end{theorem} % An analogous `Minty-like' result exists for $\chiloc(G)$. It is obtained by restricting the set over which $W$ ranges in equation~(\ref{eq:minty}). Since we only require lower bounds on~$\chiloc$ in this paper, we state and prove only the `easy direction' of this analogue. A closed walk $W$ in an embedded graph~$G$ is \DEF{homologically trivial} if $I_W \in \mathcal K(G,\ZZ)$. % \begin{proposition} \label{prop:chiloc lower} Let $G$ be an embedded graph and let $\alpha \in \RR$. If for every edge-reorientation $H$ of $G$ there exists a homologically trivial closed walk~$W$ such that $\imbal_H(W) \ge \alpha$, then $\chiloc(G) \ge \alpha$. \end{proposition} \begin{proof} By the definition of $\chiloc(G)$, there exists an edge-reorient\-ation~$H$ of~$G$, and $\phi \in \mathcal L(H,\RR)$ such that $1 \le \phi(e) \le \chiloc(G)-1$ for $e\in E(G)$. Choose $W$ in $H$ as in the statement. By Proposition \ref{prop:orth}(a) we have $$ \sum_{e\in W} \langle e,W \rangle \phi(e) = 0. $$ By separating out those terms in the summation for which $\langle e,W \rangle <0$, and using $ 1 \le \phi(e) \le \chiloc(G)-1$, it follows easily that $$ \imbal_H(W) \le 1+\max_{e\in E(W)}\{\phi(e)\} \le \chiloc(G). $$ %Thus $\chiloc(G) \ge \imbal_H( G )$. \end{proof} %% The converse of Proposition~\ref{prop:chiloc lower} appears in~\cite{GVZ}. We do not present it here since we do not need it and its proof is more involved. %%%%%%%%%%%%%%%%%%%%%%%%%%Begin Loc. Bipartite Section Let $G$ be an $\surf$-embedded even-faced graph. We say that $G$ is of \DEF{even (odd) type} if the number of edges $e$ with $\sigma(e) = -1$ is even (odd). Thus the type of $G$ has the same parity as the integers $\sum_{e\in E(G)} \tau(e)$ and $\tau \cdot \tau$. Since reorienting a face changes $\sigma(e)$ for an even number of edges, the type of $G$ is invariant under reorienting faces and edges of $G$. This classification of $G$ appears in several papers~\cite{AHN, MS, NNO,Yo}, but under several different, more geometric characterizations. For example Archdeacon et al.\ \cite{AHN} describe the type of $G$ as being the `parity of the length of a circuit in $G$ with the property that cutting the surface along it results in an orientable surface.' Alternatively, Mohar and Seymour \cite{MS} show that the type of $G$ can also be expressed as the parity of the number of `odd crosscaps' in $\surf = N_g$, where a crosscap in $\surf = N_g$ is even or odd according to the length of a circuit separating that crosscap from all the others. We do not use either of these definitions here since the circuits they refer to may not exist if $G$ has small edge-width. \begin{lemma} \label{lem:lbl} Let $G$ be an even-faced embedded graph with maximum face length~$2r$. The following are equivalent: \renewcommand{\theenumi}{{\rm \alph{enumi}}} \begin{enumerate} \item $G$ is of even type. \item The edges of $G$ can be reoriented so that each boundary walk has exactly half of its edges oriented in each direction. \item Some (and thus every) Euler tour of $G^*$ is a two-sided closed walk. \item $\chiloc(G) = 2$. \item $\chiloc(G) < 2 + 2/(r-1)$. \end{enumerate} \end{lemma} % \begin{proof} We prove (b)~$\Rightarrow$~(a)~$\Rightarrow$~(c)~\ $\Rightarrow$~(b)~$\Rightarrow$~(d)~$\Rightarrow$~(e)~$\Rightarrow$~(b). Consider the equation \begin{equation} \label{E:tau eqn} \sum_{R \in F(G)} \sum_{e \in E(G)} \langle e,R \rangle = 2 \sum_{e \in E(G)} \tau(e) \end{equation} By the definitions, $G$ is of even type if and only if the right hand side of~(\ref{E:tau eqn}) is divisible by $4$. We recall that reversing some edges of $G$ does not change its type. If~(b) holds then the left hand side of~(\ref{E:tau eqn}) vanishes for some edge-reorientation of $G$, whence $G$ has even type. Thus~(b) implies~(a). % It is immediate from the definitions and the fact $G^*$ is Eulerian that~(a) implies~(c). % Suppose~(c) holds. Let $R_0, e_1, R_1, e_2, \ldots ,e_k, R_k$ be the \faceordual walk of $G$ corresponding to an Euler tour in $G^*$. For $i=2,3, \ldots, k$ we reorient $e_i$ so that $e_i$ and $e_{i-1}$ are oppositely oriented relative to $R_i$. Then each face except possibly $R_0 = R_k$ has equal numbers of edges oriented in each direction. Thus all the terms in the left hand side of~(\ref{E:tau eqn}) vanish except, possibly, $\sum_{e \in E(G)} \langle e,R_0 \rangle$. By construction, this sum has magnitude at most~$2$, yet it is divisible by $4$, so it equals zero. Thus~(c) implies~(b). If~(b) holds, then the function $\phi \equiv 1$ is a local $2$-tension for this edge-reorientation of $G$, so~(b) implies~(d). Trivially~(d) implies~(e). % Finally, suppose that~(b) is false. Then, in view of~(\ref{eq:imbal approx}), for every edge-reorientation of $G$ there exists a face boundary walk $W$ of length $2k$ with imbalance at least $2k/(k-1)$. Since $k \le r$, this implies $\imbal_G(W) \ge 2 + 2/(r-1)$. Applying Lemma~\ref{prop:chiloc lower}, we have $\chiloc(G) \ge 2 + 2/(r-1)$. Thus~(e) implies~(b). \end{proof} % %\noindent \textsc{Remarks:} \begin{remark}\ \begin{enumerate} \item If embeddings of graphs are represented combinatorially by \DEF{rotation systems} and \DEF{signatures}~\cite{MT}, then statement (c) is equivalent to the dual~$G^*$ having an odd number of edges with negative signature. \item Suppose $G$ is even-faced of odd type. Then every surface subgraph $G'$ of~$G$ is also even-faced of odd type. (This follows from the rule that a loop incident with only one face may not be deleted in a surface minor.) If additionally, $G'$ has maximum face length $2r' < 2r$. Then the bound $\chic(G) \ge 2+2/(r-1)$ given by part (e) can be improved to $\chic(G) \ge \chic(G') \ge 2+2/(r'-1)$. It follows that Lemma~\ref{lem:lbl} holds true with the weaker hypothesis that some surface subgraph of $G$ has maximum face length~$2r$. \item More can be said about $\chic(G)$ and $\chiloc(G)$ in case $|G|$ is the projective plane. In particular, the strengthened version of the previous remark gives an exact formula for $\chic(G)$ in this case (cf. Example~\ref{eg:PP}). \end{enumerate} \end{remark} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%Begin Triangulations Next we shall classify locally 3-colorable triangulations. Let $G$ be a triangulation of a surface $\surf$. We say that $G$ is of \DEF{even} type if for every closed \faceordual walk $\omega = R_0, e_1, R_1, \ldots ,e_k, R_0$, the number of indices $i$ ($1 \le i \le k$) with $\sigma(e_i)=1$ is even. A triangulation is of \DEF{odd} type if it is not of even type. Reversing a face of $G$ changes $\sigma(e_i)$ for an even number of indices $i$, so the type of $G$ does not depend on face or edge orientations. %As far as we know, this classification does not appear in the literature. %\comment{Luis: Is this true?} \begin{lemma} \label{lem:triang} Let $G$ be a triangulation of some surface, such that $G$ has no surface-separating loops. The following are equivalent: \renewcommand{\theenumi}{{\rm \alph{enumi}}} \begin{enumerate} \item $G$ is of even type. \item The faces of $G$ can be reoriented so that $\sigma(e) = -1$ for every $e \in E(G)$. \item Every two-sided closed walk in $G^*$ has even length and every one-sided closed walk in $G^*$ has odd length. \item $\chiloc(G)=3$. \item $\chiloc(G)<4$. \end{enumerate} \end{lemma} % \begin{proof} We prove that~(b)~$\Rightarrow$~(c)~$\Rightarrow$~(a)~$\Rightarrow$~(b)~\ $\Rightarrow$~(d)~$\Rightarrow$~(e)~$\Rightarrow$~(b). % We observe that property~(c) is invariant under reorienting faces of $G$. It follows immediately that~(b) implies~(c). % Suppose now that (c) holds. Then for any closed \faceordual walk $R_0, e_1, R_1, \ldots ,e_k, R_0$, the number of indices $i$ for which $\sigma(e_i) = -1$ has the same parity as $k$. Thus the number of indices $i$ for which $\sigma(e_i)=1$ equals $k - | \{ i \mid \sigma(e_i) = -1 \} |$, which is even. Thus~(c) implies~(a). % Suppose~(a) holds. Choose a face $R \in F(G)$, and let $X$ be the set of faces $Q \in F(G)$ such that there exists a \faceordual walk $R_0,e_1,R_1,\ldots,e_k,R_k$ with $R_0 = R$, $R_k = Q$, and with $| \{ i\mid 1 \le i \le k, \sigma(e_i) = 1 \}|$ odd. Let $Y = F(G) \setminus X$. Since no closed \faceordual walk has an odd number of edges~$e$ with $\sigma(e)=1$, it follows that an edge $e \in E(G)$ has $\sigma(e)=1$ if and only if $e$ is incident with one face in $X$ and one face in $Y$. Thus, the orientation obtained by reversing the faces in $X$ satisfies~(b). Suppose~(b) holds. If $G^*$ is the dual graph, then $G^*$ is cubic. Since $G$ has no surface separating loops, $G^*$ is 2-edge-connected. It follows from Petersen's theorem that there exists a perfect matching $M \subseteq E(G^*)$. Let $M'$ be the corresponding set of edges in $G$. Condition~(b) implies $\tau(e) = \pm 1$ for $e \in E(G)$. Therefore the map $\phi : E(G) \rightarrow \RR$ given by the rule \[ \phi(e) = \left\{ \begin{array}{ll} 2\, \tau(e) & \mbox{if $e \in M'$} \\ - \tau(e) & \mbox{otherwise} \end{array} \right. \] is a local 3-tension. Thus~(b) implies~(d). %% Trivially we have~(d) implies~(e). Finally, suppose that~(e) is true. By Lemma~\ref{prop:chiloc lower}, there is an edge-reorientation $G'$ of $G$ such that every homologically trivial closed walk in $G'$ has imbalance less than $4$. In particular, each boundary walk has at least one edge in each direction. Let $G''$ be obtained from $G$ by reorienting faces in such a way that each boundary walk has exactly two forward edges with respect to $G'$. We claim that $G''$ satisfies~(b). If $\sigma(e)=1$ for some $e\in E(G'')$, then $e$ must bound two distinct faces. One easily checks that the boundary of the union of these faces is a homologically trivial walk of length~$4$ whose imbalance in $G'$ equals $4$, a contradiction. Thus~(e) implies~(b). \end{proof} %\noindent \textsc{Remark: } \begin{remark} If we wish to allow surface-separating loops in Lemma \ref{lem:triang}, then the theorem is false unless we append the phrase, ``and $G^*$ has a perfect matching'' to each of the conditions~(a),~(b) and~(c). This perfect matching is used in proving (b)~$\Rightarrow$~(d). Conversely, in the proof of~(e) $\Rightarrow$~(b), a perfect matching of $G^*$ can be recovered by selecting from each face $R$ the unique edge in $G'$ which is backward with respect to the orientation of $R$ in $G''$. The smallest triangulation with loops which satisfies~(b) but not~(d) is the graph $G_0$ having one vertex and six loops embedded on $N_3$ in such a way that $G_0^*$ is the $3$-regular graph obtained from $K_{1,3}$ by adding three loops. With this remark in mind, it may be technically more accurate to add the perfect matching condition in the definition of `even type'. \end{remark} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%End Triangulations We make two observations concerning the characterizations of Lemmas~\ref{lem:lbl} and~\ref{lem:triang}. First, if $\surf$ is orientable, then every $\surf$-embedded even-faced graph is of even type. This is false for triangulations; a single odd-degree vertex already implies the type is odd. Furthermore, Eulerian triangulations of both types exist on any surface different from the sphere. A triangulation of an orientable surface is of even type if and only if its dual graph $G^*$ is bipartite. It is easy to check if a given even-faced graph (respectively, a triangulation) is of even or odd type. To determine the type of an even-faced embedded graph, one needs only perform a single parity check involving all of its edges, by Lemma~\ref{lem:lbl}(c). For a triangulation, one has to consider the dual graph $G^*$. First of all, we subdivide every edge $e^*$ of~$G^*$ whose signature is negative (i.e., $\sigma(e)=-1$). If $H$ is the resulting graph, then $G$ is of even type if and only if $H$ is bipartite. This follows easily from Lemma~\ref{lem:triang}(c). \medskip\noindent\textbf{Proof of Theorem~\ref{thm:bimodality}:} This follows from parts~(a),~(d) and~(e) of Lemma~\ref{lem:lbl}. and from parts~(a),~(d) and~(e) of Lemma~\ref{lem:triang}. %\hspace{1em}\rule{.6ex}{1.9ex} %Luis: Made to look consistent to trans-l.cls style \hfill$\Box$ %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \section{Examples} \label{sect:egs} In this section we present several examples and special cases which are relevant to this paper. Most of these examples are not new. However their study has hitherto been confined to the invariants $\chi(G)$ and $\lceil\phic(G)\rceil$. Example~\ref{eg:P} is classic. Variations and special cases of Exaples \ref{eg:QH} and \ref{eg:T} appear in \cite{AHN, Hu, HRS, MS, Yo}. Example~\ref{eg:F} is due to Fisk~\cite{fisk}, and Theorem~\ref{thm:PP chic} is due to Goddyn~\cite{G}. Example~\ref{eg:not strong phi} and Theorem~\ref{thm:chi5} are new to our knowledge. \begin{example} % 6.1 \label{eg:P} \rm There is an embedding $K$ of $K_6$ with edge-width~$3$ on the projective plane. The dual $K^*$ is Petersen's graph. By Corollary~\ref{cor:chiloc=chic} and the well known fact that $\chic(K_n)=n$, we have $\chiloc(K) = \chic(K) = 6$, whereas $\phic(K^*)=5$. This example shows that no improvement is possible in conjectures of Bouchet and DeVos regarding~$\chiloc$, as discussed after Conjecture~\ref{conj:orientable upper bounds}. %Petersen's graph shows that %Tutte's $5$-flow conjecture (that $\phic(2) \le 5$) %can not be improved even fractionally. \end{example} %%%%%%%%%%%%%%%%%% \begin{example} % 6.2 \label{eg:QH} \rm For any nonorientable surface $\surf$, there exist $3$-connected quadrangulations $Q$ and hexangulations $H$ of odd type and arbitrarily large edge-width which satisfy $\chic(Q) \ge \chiloc(Q) \ge 4$, $\chic(H) \ge \chiloc(H) \ge 3$, and $\phic(Q^*) = \phic(H^*) = 2$. To construct such examples, we proceed as follows. By patching together square or hexagonal grids appropriately, and then subdividing edges if desired, it is not difficult to construct even-faced embedded graphs of odd type with additional properties. We omit a proof of the following. % \begin{proposition} \label{P:egs} For every integer $r \ge 1$ and every nonorientable surface $\surf$, there exists an even-faced\/ $\surf$-embedded graph $G_r$ of odd type %~$G_r$ has girth $2r$ and arbitrarily large edge-width, such that every shortest circuit bounds a face of length~$2r$. Furthermore, $G_r$ is $3$-connected if\/ $r\in\{2,3\}$. \end{proposition} % By Lemma \ref{lem:lbl}(e), we have $\chic(G_r) \ge \chiloc(G_r)\ge 2+2/(r-1)$. In fact we have that $\chic(G_r) = 2+2/(r-1)$ provided the edge-width is large enough, but we do not prove this here. If, additionally, we have $2r \in \{4,6\}$, then the upper bounds in parts (b) and (d) of Theorem~\ref{thm:upper bounds} imply that $\chi(G_r) = \chic(G_r) = \chiloc(G_r) = 2+2/(r-1)$. Therefore one can not improve %no improvement is possible in the bounds in parts (b), (c) and (d) of that Theorem. \end{example} %%%%%%%%%%%%%%%%%% \begin{example} % 6.3 \label{eg:not strong phi} \rm % This example shows that Theorem~\ref{thm:main} is false without the assumption that $\phi \in \mathcal L^+(G,\Gamma)$. Let $G$ be an even-faced embedded graph of odd type and maximum face length $2r$. The constant function $\phi(e) \equiv 1/2$ is clearly a local $\CG$-tension where $\CG = \RR/\ZZ$, but $\phi$ is not strong since $\tau \cdot \phi = 1/2$. By Theorem~\ref{thm:bimodality}(a) we have $\chic(G) \ge 2r/(r-1)$. Thus by Proposition~\ref{prop:CG chic} every $\CG$-tension~$\phi'$ satisfies $$ %\min_{e \in E(G)} \Vert \phi'(e) \Vert \le 1/\chic(G) \le 1/2-1/2r. \min_{e \in E(G)} \Vert \phi'(e) \Vert \le \frac1{\chic(G)} \le \frac12-\frac1{2r}. $$ Thus the conclusion of Theorem~\ref{thm:main} fails when $Q$ is the $k$-part %$[ -1/2k, 1/2k]$ $\left[ \frac{-1}{2k}, \frac1{2k}\right]$ of~$\CG$, for any $k> r$. \end{example} %%%%%%%%%%%%%%%%%% \begin{example} % 6.4 \label{eg:T} \rm % Hutchinson et al.\ \cite{HRS} proved that the graph obtained from a nonbipartite quadrangulation of the projective plane by adding a new vertex in every face adjacent to all four vertices on the boundary has chromatic number at least $5$. This property extends to the circular chromatic number, and examples exist on all nonorientable surfaces. \begin{theorem} \label{thm:chi5} Let $G$ be an odd type quadrangulation of some surface. Let~$H$ be obtained from~$G$ by adding a new vertex in each face adjacent to all four vertices on the boundary. Then $\chi(H) \ge \chic(H) \ge \chiloc(H) \ge 5$. \end{theorem} % \begin{proof} Let $H'$ be an arbitrary edge-reorientation of $H$, and let $G'$ denote the subgraph of $H'$ corresponding to $G$. By Lemma \ref{lem:lbl}(b) there is a face $R$ of $G'$ whose boundary walk $W$ satisfies $\imbal_{G'}(W) \ge 4$. Consider now the subgraph of $H'$ consisting of $W$ together with the vertex added in $R$ and all of its incident edges. It is easy to verify that~$H'$ contains another walk~$W'$ with $\imbal_{H'}(W') \ge 5$. The walk $W'$ is homologically trivial. Therefore $\chiloc(H) \ge 5$ by Proposition~\ref{prop:chiloc lower}. \end{proof} % If, additionally, $H$ has high edge-width, then Theorem~\ref{thm:upper bounds}(a) implies that $\chi(H) = \chic(H) = \chiloc(H)=5$. Therefore, this upper bound is best possible in a strong sense. \end{example} %%%%%%%%%%%%%%%%%% \begin{example} % 6.5 \label{eg:F} \rm The following examples show that for every surface $\surf$ different from the sphere there exist $5$-connected triangulations $F$ of odd type and arbitrarily large edge-width which satisfy $\phic(F^*) = 3$ and $\chic(F) > 4$. It seems likely that when $\surf$ is orientable we have $4 = \chiloc(F) < \chic(F) < 4+\epsilon$ where $\epsilon$ approaches zero as edge-width increases. % Fisk \cite{fisk} showed that any triangulation $G$ with exactly two odd-degree vertices satisfies $\chic(G) > 4$ provided the two vertices are adjacent. Such \DEF{Fisk triangulations} exist of arbitrary edge-width on every surface except the sphere (cf.,\ e.g.,\ \cite{Th}). We suspect that Fisk triangulations~$G$ of orientable surfaces usually satisfy $\chiloc(G)=4$. %Luis: What is the point of including this? %\comment{Luis: I have convinced myself of this for certain % We have verified this statement for various % instances of Fisk construction, such as the one presented % by Thomassen, but it is too messy to present here} This is a special case of Gr\"unbaum's Conjecture~\ref{conj:orientable upper bounds}(b). By Theorem~\ref{thm:chilt} this would imply that $\chic(G)$ is vanishingly close to $4$ for high edge-width Fisk triangulations of orientable surfaces. In summary, Fisk triangulations have the advantage over Example~\ref{eg:T} of existing on orientable surfaces (other than the sphere), but the disadvantage of having a smaller local circular chromatic number. \end{example} \begin{example} % 6.6 \label{eg:PP} \rm % There are several improvements to results in this paper in the case when $G$ is embedded in the projective plane. First, such embedded graphs satisfy $\chic(G) = \chiloc(G)$ by Corollary~\ref{cor:chiloc=chic}. This allows one to set $\epsilon = 0$ in the statements of Theorems~\ref{thm:chilt}, \ref{cor:bimodality}, and~\ref{thm:main}. % Second, a circuit in~$G$ is noncontractible in~$\N_1$ if and only if it is semifacial. %(see Sections~\ref{sect:def} and~\ref{sect:proof} for definitions). Consequently, if $G$ is a triangulation of~$\N_1$, then $G$ is of even type if and only if its dual~$G^*$ is even-faced of odd type. This statement is false on any other surface. Additionally, an even-faced $\N_1$-embedded graph has even type if and only if it is bipartite. % Third, the homotopy group of $\N_1$ is $\ZZ/2\ZZ$. This makes it possible to classify the circuits of $G$ and apply the Minty formula, Theorem~\ref{thm:minty}. In this way Goddyn~\cite{G} has derived an exact formula for even-faced graphs on $\N_1$. %%%%%%%%%%%%%%%%%%%%%%%% % \begin{theorem} \label{thm:PP chic} Let $G$ be a loopless even-faced\/ $\N_1$-embedded graph. Then either $\chic(G)=2$ or $\chic(G) = 2 + 2/(r-1)$ where~$r$ is the smallest integer such that some surface subgraph has maximum face length $2r$. \end{theorem} %In particular For example, a projective planar even-faced graph $G$ has $\chic(G)=4$ if and only if it is loopless, nonbipartite and contains a quadrangulation of $\N_1$ as a surface subgraph. % Similarly, $\chic(G)=3$ if and only if $G$ is loopless, nonbipartite, contains no quadrangulation, but contains a surface subgraph with all faces of length 4 or 6. % Otherwise, $\chic(G) \le 8/3$. % Any hexangulation $H$ of $\N_1$ satisfies $\chic(H) \in \{2,3,4,\infty\}$, and every quadrangulation~$Q$ of $\N_1$ satisfies $\chic(Q) \in \{2,4,\infty\}$. The latter result strengthens that of Youngs~\cite{Yo}, which considers only~$\chi(Q)$. % Gimbel and Thomassen~\cite{GT} have proved a related result that holds for embedded graphs which are not even-faced: a loopless $\N_1$-embedded graph with no contractible triangles satisfies $\chic(G)\le 3$ if and only if it contains no nonbipartite quadrangulation as a surface subgraph. One application regards the well-known Mycielski transformation~\cite{Myc}, % %given a graph~$G$, we join a new copy $v'$ of each $ v \in V(G)$ %to the neighbours of $v$, %then we join a new vertex $x$ to all vertices of the form $v'$. which constructs, from any simple graph $G$, a new graph $\mu(G)$ having the same clique number as~$G$, %and such that but $\chi(\mu(G)) = \chi(G)+1$. % For any odd circuit~$C_{2k+1}$, the graph $\mu(C_{2k+1})$ embeds on~$\N_1$ as a quadrangulation of odd type. %(Here $\mu(C_5)$ is the famous Gr\"otzsch graph.) Our results imply that $\chic(\mu(C_{2k+1}))=4$ even though $\chic(C_{2k+1})=2+1/k$. This result already appears in~\cite{CHZ}. %and uses the case $r=2$ of Theorem~\ref{thm:PP chic}. Let us remark that a similar statement also holds for the `generalized Mycielski construction', a variation which which has recently gained attention with regard to graph homomorphisms~\cite{tardif}. \end{example} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%5 \section{Bordered surfaces} It is possible to define embeddings of graphs in bordered surfaces. We shall refrain from giving a formal definition here. For our purpose, a bordered surface embedding can be obtained from an embedding of a graph $G$ in a closed surface by removing %Luis: more precise, and it has been defined (the interiors of) some of the faces. The boundaries of the removed faces are then called the \DEF{boundary components} of the resulting bordered surface. We do not require that the boundary components be disjoint. We define the \DEF{edge-width} of a graph embedded in a bordered surface as the length of a shortest noncontractible circuit in $G$. Observe that the circuits on the boundary are noncontractible except when the surface is the disk (sphere with one boundary component). Let $G$ be a graph embedded in a bordered surface $\surf$ with boundary components $Q_1,\dots,Q_r$. Let $\tilde G$ be the graph embedded in a (closed) surface $\widetilde{\surf}$ which is obtained as follows. First, we add a chimney to every boundary component $Q_i$ ($1\le i\le r$) and denote by $Q_i'$ the new boundary component obtained this way. Now, we take two copies of the resulting graph and identify each boundary component $Q_i'$ in the first copy with the corresponding boundary component in the second copy. Then it is easy to see that the edge-width of $\tilde G$ in $\widetilde{\surf}$ is equal to the edge-width of $G$ in~$\surf$. Moreover, every (local) tension in $G$ determines a (local) tension in $\tilde G$, and vice versa. We leave the details to the reader. The above remarks show that the results of this paper can also be formulated for graphs on bordered surfaces. As an example, we state analogues of Theorem~\ref{thm:chilt} and Corollary \ref{cor:bimodality}(a). \begin{theorem} \label{thm:chiltBordered} Let $\surf$ be a bordered surface and let $\epsilon > 0$. There exists an integer~$M$ so that every graph $G$ embedded in\/ $\surf$ with edge-width at least $M$ satisfies $$ \chiloc(G) \le \chic(G) \le \chiloc(G) + \epsilon. $$ \end{theorem} \vspace{-1ex} % too much space \begin{corollary} \label{cor:bimodalityBordered} For every fixed bordered surface $\surf$ and every $\epsilon > 0$, there exists an integer $M$ such that %$\chic(G) \le 2 + \epsilon$ for every even-faced $\surf$-embedded graph $G$ with maximum face length $2r$ and with edge-width at least $M$, \[ \chic(G) \in [ 2, 2+\epsilon ] \cup [ 2+ 2/(r-1) , 4 ]. \] % \end{corollary} % Let us further remark, for example, that Corollary \ref{cor:bimodalityBordered} can be applied to graphs in closed surfaces whose faces are of even length except for a bounded number of faces of large odd length, which one can remove to get an even-faced embedding in a bordered surface. \begin{thebibliography}{99} \bibitem{AHN} D.~Archdeacon, J.~Hutchinson, A. Nakamoto, S. Negami, and K. Ota, Chromatic numbers of quadrangulations on closed surfaces, J. Graph Theory 37 (2001) 100--114. \bibitem{Bo} A. Bouchet, Nowhere-zero integral flows on a bidirected graph, J. Combin.\ Theory Ser.~B 34 (1983) 279--292. \bibitem{BMR} R.~Brunet, B.~Mohar, R.~B.~Richter, Separating and nonseparating disjoint homotopic cycles in graph embeddings, J.~Combin. Theory Ser.~B 66 (1996) 201--231. \bibitem{CHZ} G.~Chang, L.~Huang, X.~Zhu, Circular chromatic numbers of Mycielski's graphs, Discrete Math.\ 205 (1999) 23--37. \bibitem{De} M. DeVos, Flows on bidirected graph, preprint. \bibitem{Er} P. Erd\H{o}s, Graph theory and probability, Canadian J. Math.\ 11 (1959) 34--38. \bibitem{fisk} S.~Fisk, The nonexistence of colorings, J.~Combin. Theory Ser.~B 24 (1978) 247--248. \bibitem{FM} S.~Fisk, B.~Mohar, Coloring graphs without short non-bounding cycles, J.~Combin. Theory Ser.~B 60 (1994) 268--276. \bibitem{Giblin} P.~J.~Giblin, Graphs, surfaces and homology. An introduction to algebraic topology, Second edition, Chapman and Hall, London-New York, 1981. %\bibitem{GGH} %A.~Galluccio, L.~Goddyn, P.~Hell, %High-girth graphs avoiding a minor are nearly bipartite, %J.~Combin. Theory Ser.~B 83 (2001), 1--14. \bibitem{GT} J.~Gimbel, C.~Thomassen, Coloring graphs with fixed genus and girth, Trans. Amer. Math. Soc. 349 (1997), 4555--4564. \bibitem{G} L.~Goddyn, The circular chromatic of even faced projective plane graphs, Preprint. \bibitem{GTZ} L.~A.~Goddyn, M.~Tarsi, C.-Q.~Zhang, On $(k,d)$-colorings and fractional nowhere-zero flows, J. Graph Theory 28 (1998) 155--161. \bibitem{GVZ} L.~Goddyn, D.~Vertigan, X.~Zhu, Minty type formulas, preprint. \bibitem{GS94} M.~de Graaf, A.~Schrijver, Grid minors of graphs on the torus, J.~Combin. Theory Ser.~B 61 (1994) 57--62. \bibitem{GH81} M.~J.~Greenberg, J.~R.~Harper, Algebraic Topology. A First Course, Benjamin/Cummings Publ.\ Comp., Menlo Park, California, 1981. \bibitem{Gr69} B.~Gr\"unbaum, Conjecture 6, in ``Recent Progress in Combinatorics'', Ed. W.~T.~Tutte, Academic Press, New York, 1969, p.~343. \bibitem{Hu} J.~P.~Hutchinson, Three-coloring graphs embedded on surfaces with all faces even-sided, J.~Combin. Theory Ser.~B 65 (1995) 139--155. \bibitem{HRS} J. Hutchinson, R. B. Richter, P. Seymour, Colouring Eulerian triangulations, J. Combin. Theory Ser.~B 84 (2002) 225--239. \bibitem{Ja} F.~Jaeger, Flows and generalized coloring theorems in graphs. J. Combin. Theory Ser. B 26 (1979) 205--216. \bibitem{Ja1} F.~Jaeger, Nowhere-zero flow problems, in, \textit{Selected Topics in Graph Theory}, Volume 3, Academic Press, 1988, pp.~71--96. \bibitem{Min} G.~J.~Minty, A theorem on $n$-coloring the points of a linear graph, Amer. Math. Monthly 69 (1962) 623-624. \bibitem{BCC} B.~Mohar, Graph minors and graphs on surfaces, in ``Surveys in Combinatorics, 2001'', Ed.~J.~W.~P.~Hirschfeld, London Mathematical Society Lecture Note Series 288, Cambridge Univ.\ Press, Cambridge, 2001, pp.~145--163. \bibitem{MS} B.~Mohar, P.~D.~Seymour, Coloring locally bipartite graphs on surfaces, J. Combin. Theory Ser.~B 84 (2002) 301--310. \bibitem{MT} B.~Mohar, C.~Thomassen, Graphs on Surfaces, Johns Hopkins University Press, Baltimore, 2001. \bibitem{Myc} J.~Mycielski, Sur le coloriage des graphs, Colloq.\ Math.\ 3 (1955) 161--162. \bibitem{NNO} A.~Nakamoto, S.~Negami, K.~Ota, Chromatic numbers and cycle partitions of quadrangulations on nonorientable surfaces, preprint. \bibitem{GM7} N.~Robertson, P.~D.~Seymour, Graph minors VII. Disjoint paths on a surface, J.~Combin. Theory Ser.~B 45 (1988) 212--254. \bibitem{Ring} G.~Ringel, Map Color Theorem, Springer-Verlag, New York-Heidelberg, 1974. \bibitem{Se} P.~D. Seymour, Nowhere-zero 6-flows, J. Combin. Theory Ser.~B 30 (1981) 130--135. \bibitem{tardif} C.~Tardif, Fractional chromatic numbers of cones over graphs, J. Graph Theory 38 (2001) 87--94. \bibitem{Th5} C.~Thomassen, Five-coloring maps on surfaces, J.~Combin. Theory Ser.~B 59 (1993) 89--105. \bibitem{Th1} C.~Thomassen, The chromatic number of a graph of girth 5 on a fixed surface. J.~Combin. Theory Ser.~B 87 (2003) 38--71. \bibitem{Th} C.~Thomassen, Color-critical graphs on a fixed surface, J.~Combin. Theory Ser.~B 70 (1997) 67--100. \bibitem{Tu54} W.~T.~Tutte, A contribution to the theory of chromatic polynomials, Canad. J. Math. 6 (1954) 80--91. \bibitem{Tu56} W.~T.~Tutte, A class of Abelian groups, Canad. J. Math. 8 (1956) 13--28. \bibitem{Yo} D.~A.~Youngs, 4-chromatic projective graphs, J.~Graph Theory 21 (1996) 219--227. % \bibitem{Zhu1} X. Zhu, % Planar graphs with circular chromatic numbers between $3$ and $4$, % J.~Combin. Theory Ser.~B 76 (1999), 170--200. \bibitem{Zhu} X. Zhu, Circular chromatic number: a survey, Discrete Math. 229 (2001) 371--410. % \bibitem{Zhu2} X. Zhu, % Construction of graphs with given circular flow number, % preprint. \end{thebibliography} \end{document}