TRANSACTIONS OF THE AMERICAN MATHEMATICAL SOCIETY Volume 00, Number 0, Pages 000–000 S 0002-9947(XX)0000-0

COLORING-FLOW DUALITY OF EMBEDDED GRAPHS

MATT DEVOS, LUIS GODDYN^{1}, BOJAN MOHAR^{2}, DIRK VERTIGAN^{3}, AND XUDING ZHU^{4}

Abstract. Let G be a directed graph embedded in a surface. A map ϕ : E(G) → ℝ is a tension if for every circuit C ⊆ G, the sum of ϕ on the forward edges of C is equal to the sum of ϕ 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 ϕ is a local tension. If 1 ≤ |ϕ(e)| ≤ α − 1 holds for every e ∈ E(G), we say that ϕ is a (local) α-tension. We define the circular chromatic number and the local circular chromatic number of G by χ_{c}(G) = inf{α ∈ ℝ | G has an α-tension} and χ_{loc}(G) = inf{α ∈ ℝ | G has a local α-tension}, respectively. The invariant χ_{c} is a refinement of the usual chromatic number, whereas χ_{loc} is closely related to Tutte’s flow index and Bouchet’s biflow index of the surface dual G^{∗}.

From the definitions we have χ_{loc}(G) ≤ χ_{c}(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 𝕏 and every ε > 0, there exists an integer M so that χ_{c}(G) ≤ χ_{loc}(G) + ε holds for every graph embedded in 𝕏 with edge-width at least M, where the 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 χ_{loc}, and thus in χ_{c} 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 ≤ 2r, then χ_{c}(G) ∈ [2, 2 + ε] ∪ [ \frac{2r}{r−1} , 4]. Similarly, if G is a triangulation with large edge-width, then χ_{c}(G) ∈ [3, 3+ε]∪[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.

1. Introduction

Our discussion is concerned with tensions, local tensions, and flows on embedded graphs. Although rigorous definitions will be postponed until Section 3, some informal description needs to be stated here. By default all graphs are finite directed

1991 Mathematics Subject Classification. 05C10, 05C15 Received by editors April 7, 2003. Revised version received October 3, 2003.

Key words and phrases. Graph theory, coloring, flow, tension, local tension, circular chromatic number, surface, edge-width, triangulation, quadrangulation, locally bipartite.

1Supported in part by the National Sciences and Engineering Research Council of Canada, and the Pacific Institute for the Mathematical Sciences.

2Supported in part by the Ministry of Science and Technology of Slovenia, Research Program J1–0507–0101.

3Supported in part by the National Security Agency, grant number MDA904-01-0014. 4Supported in part by ROC National Science Council Grant NSC 91-2115-M-110-003.

\begin{matrix}c \\ ◯ \end{matrix}2003 American Mathematical Society

graphs, where loops and multiple edges are allowed. A walk or circuit in a graph G is a walk or circuit in the undirected graph which underlies G. A surface 𝕏 is a closed compact connected 2-manifold. An 𝕏-embedded graph is a graph G which is topologically embedded in 𝕏 in such a way that each connected component of 𝕏 − G, or face, is homeomorphic to a disc. Where no confusion arises, we use G to refer both to an 𝕏-embedded graph, and to the underlying abstract directed graph.

Let G be an embedded directed graph. A map ϕ : E(G) → ℝ is a 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 ϕ is an α-flow if 1 ≤ |ϕ(e)| ≤ α − 1 holds for every e ∈ E(G). Informal definitions of α-tension and local α-tension are given in the abstract. We define three invariants:

χ_{c}(G) = inf{α ∈ ℝ | G admits an α-tension},
χ_{loc}(G) = inf{α ∈ ℝ | G admits a local α-tension},
ϕ_{c}(G) = inf{α ∈ ℝ | G admits an α-flow}.

They are called the circular chromatic number, the local circular chromatic number, and the 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 ∈ E(G), then by replacing ϕ(e) by −ϕ(e) we preserve the property that ϕ is a (local) α-tension or α-flow.

The chromatic number of a graph G is given by χ(G) = ⌈χ_{c}(G)⌉, c.f., e.g. [37]. Thus, we may view χ_{c} as a refinement of the usual notion of chromatic number. There are close connections between χ_{c} and other graph properties involving orientations, homomorphisms and group valued tensions. As such, there has been considerable interest in the invariant χ_{c}(G). We refer the reader to [37] for a survey. All existing literature on χ_{loc}(G) refers to this invariant indirectly, via the dual embedded graph G^{∗}. In particular, if the surface is orientable, then χ_{loc}(G^{∗}) = ϕ_{c}(G) and ⌈χ_{loc}(G^{∗})⌉ is precisely the flow index of Tutte [34]. If the surface is nonorientable, then ⌈χ_{loc}(G^{∗})⌉ is the biflow index of Bouchet [2]. Thus χ_{loc} both unifies and refines these two indices for embedded graphs.

Our main result reveals a close connection between χ_{c}(G) and χ_{loc}(G) for embedded graphs. Based on the above discussion we have

χ_{loc}(G) ≤ χ_{c}(G) ≤ χ(G)  (1.1)

for every embedded graph G. The first two invariants in (1.1) are equal for plane graphs and projective plane graphs, by Corollary 3.3, but they can differ on other surfaces. Our main result is that χ_{loc}(G) and χ_{c}(G) are very close if an 𝕏-embedded graph G has high edge-width. We recall that the edge-width of G, denoted by edgewidth(G), is the length of a shortest circuit in G which forms a noncontractible curve in 𝕏. We define edgewidth(G) = ∞ if 𝕏 is simply connected.

Theorem 1.1 (Main Theorem). For every surface 𝕏 and every ε > 0, there exists an integer M so that every loopless 𝕏-embedded graph G with edgewidth(G) ≥ M satisfies

χ_{loc}(G) ≤ χ_{c}(G) ≤ χ_{loc}(G) + ε.

Theorem 1.1 is proved in Section 4. It is a special case of Theorem 4.1 which is concerned with group-valued tensions.

We apply this result to two families of embedded graphs for which χ_{loc} exhibits interesting behavior. An embedded graph G is even-faced if all its faces have even length. A triangulation is an embedded graph whose faces all have length three. In Section 5, we show that even-faced embedded graphs and triangulations come in two types: odd and even type. In both cases, the 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 χ_{loc}(G).

Theorem 1.2 (Bimodality of χ_{loc}). Let G be an embedded graph.

(a) If G is even-faced with maximum face length 2r, then either

χ_{loc}(G) = 2 (even type) or χ_{loc}(G) ≥ \frac{2r}{r − 1} (odd type).

(b) If G is a triangulation, then either

χ_{loc}(G) = 3 (even type) or χ_{loc}(G) ≥ 4 (odd type).

Applying Theorem 1.1 and some upper bounds from Theorem 2.2, we have the following.

Corollary 1.3 (Bimodality of χ_{c}). For any surface 𝕏 and any ε > 0, there exists an integer M such that, for every 𝕏-embedded graph G with edgewidth(G) ≥ M,

(a) if G is even-faced with maximum face length 2r, then

χ_{c}(G) ∈ [2, 2 + ε] ∪ [2r/(r − 1), 4];

(b) if G is a loopless triangulation, then

χ_{c}(G) ∈ [3, 3 + ε] ∪ [4, 5].

Moreover, we show (cf. Theorem 6.6) 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 [36] that projective plane quadrangulations never have chromatic number three. They also strengthen results on the chromatic number of quadrangulations [1, 26], even-faced graphs [17, 23], and Eulerian triangulations [18].

Remark 1.4. A little more can be said in some special cases:

(1) If 𝕏 is the plane or projective plane, the invariant χ_{c}(G) is relatively well behaved. For example, we may set ε = 0 in Theorem 1.1 and in Corollary 1.3 (cf. Corollary 3.3). If G is even-faced, then there is an exact formula for χ_{c}(G) (cf. Example 6.8). In particular, every projective planar even-faced graph G satisfies χ_{c}(G) = 2 + 2/k for some k ∈ {0, 1, …, ∞} (where we interpret 1/∞ = 0 and 1/0 = ∞).

(2) The upper bound ‘4’ can be replaced by ‘3’ in part (a) of Corollary 1.3 provided all circuits in G have length at least 6 (cf. Theorem 2.2(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.

(3) The interval ‘[4, 5]’ in Corollary 1.3(b) can be replaced by ‘{4}’ if 𝕏 is orientable and G is Eulerian. This is implied by a result of Hutchinson et al. [18] which states that all such triangulations of sufficiently large edgewidth satisfy χ(G) ≤ 4. If 𝕏 is orientable but G has odd-degree vertices, then one would be able to replace ‘[4, 5]’ by ‘[4, 4+ε]’ provided a conjecture of Grünbaum (Conjecture 2.1(b)) holds.

In Section 6 we provide examples that show no further improvements of this type are possible.

When the surface 𝕏 is orientable, these results have consequences involving flows in the surface dual. Let G^{∗} be the unoriented 𝕏-embedded graph which is the surface dual of G. Using a global orientation of 𝕏, we may direct the edges of G^{∗} so that each edge e^{∗} ∈ E(G^{∗}) crosses left to right over the corresponding dual edge e ∈ E(G). It follows from definitions that a function ϕ : E(G) → ℝ is a local α-tension of G if and only if ϕ^{∗} : e^{∗} ↦ ϕ(e) is an α-flow in G^{∗}. Thus, duality exchanges local tensions with flows on orientable surfaces, and we have the relation ϕ_{c}(G^{∗}) = χ_{loc}(G). If 𝕏 is the sphere, every local tension is also a tension, so χ_{c}(G) = χ_{loc}(G) = ϕ_{c}(G^{∗}). Indeed, this is an early observation of Tutte [12], usually recognized as flow-coloring duality, which provided motivation for our work. The following corollary of Theorem 1.1 generalizes this to orientable surfaces.

Corollary 1.5 (Approximate Duality). Let 𝕏 be an orientable surface and let ε > 0. There exists an integer M such that every loopless 𝕏-embedded graph G with edgewidth(G) ≥ M satisfies ϕ_{c}(G^{∗}) ≤ χ_{c}(G) ≤ ϕ_{c}(G^{∗}) + ε.

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 biflow, see, e.g., [2, 5]. 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.

2. Known Results and Conjectures

We briefly survey the state of knowledge regarding the invariants χ_{c}, χ_{loc}, and ϕ_{c}. The bimodal behaviors reported in Corollary 1.3 appear nowhere in the literature except for Youngs’ observation [36] 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 1.3; in any other situation, either ε is positive, or 2 + 2/(r − 1) ≤ 3, so bimodal behaviour is not detectable via the crude invariant χ = ⌈χ_{c}⌉. The circular chromatic number is needed in order to see that Youngs’ example is not an isolated curiosity.

Other than [36], the existing literature consists primarily of proven and conjectured upper bounds on the integer values ⌈ϕ_{c}(G)⌉, ⌈χ_{loc}(G)⌉ and χ(G) = ⌈χ_{c}(G)⌉ for various families of embedded and abstract graphs G. Most of these bounds are best possible due to examples given in Section 6. However, there is now the question as to whether these upper bounds are also best possible for the refined parameters ϕ_{c}, χ_{loc} and χ_{c}.

The girth of G, girth(G), is the minimum length of a circuit in G. The cogirth of G, cogirth(G), is the minimum cardinality of a nonempty edge cut in G. For any graph G we have χ_{c}(G) < ∞ (resp. ϕ_{c}(G) < ∞) if and only if girth(G) ≥ 2 (cogirth(G) ≥ 2). In contrast, it is possible that χ_{loc}(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 χ_{loc}(G) = 2. In general one expects stronger upper bounds on χ_{c}(G) (and ϕ_{c}(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 edgewidth are ‘locally planar’ and thus exhibit bounded chromatic properties. One should keep in mind that 𝕏-embedded graphs G satisfy girth(G) ≤ edgewidth(G), but cogirth(G) is generaly unrelated to edgewidth(G^{∗}).

Most published results and conjectures regarding ϕ_{c}(G) make no reference to a surface, but do refer to cogirth(G). For a positive integer d, we define

ϕ_{c}(d) = sup{ϕ_{c}(G) | G is a graph with cogirth(G) ≥ d}.

Tutte [34] initiated the study of α-flows when he conjectured ϕ_{c}(2) ≤ 5 and ϕ_{c}(4) ≤ 3. Seymour [29] proved that ϕ_{c}(2) ≤ 6, and Jaeger [19] proved that ϕ_{c}(4) ≤ 4. Jaeger [20] further conjectured that ϕ_{c}(4k) ≤ 2 + \frac{1}{k} 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 𝕏-embedded graph G with cogirth(G) ≥ 2 and edgewidth(G^{∗}) ≥ k satisfies ϕ_{c}(G) ≤ 4. We must have k ≥ 4 here because of Example 6.1. Grünbaum [16] has conjectured that k = 3 suffices here, provided that 𝕏 is orientable.

If 𝕏 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ünbaum attractively specialize.

Conjecture 2.1. Let G be an 𝕏-embedded graph where 𝕏 is orientable. (a) If girth(G) ≥ 2, then χ_{loc}(G) ≤ 5.

(b) If girth(G) ≥ 3, then χ_{loc}(G) ≤ 4.

(c) If girth(G) ≥ 4, then χ_{loc}(G) ≤ 3.

When 𝕏 is not orientable, these conjectured upper bounds on χ_{loc} must be weakened. Bouchet [2] conjectures that every loopless 𝕏-embedded graph G satisfies χ_{loc}(G) ≤ 6. DeVos [5] proved that such graphs satisfy χ_{loc}(G) ≤ 12. This is in contrast to the fact there exists no general bound on χ_{c}(G). DeVos [private communication] has proposed that Bouchet’s conjecture can be improved to χ_{loc}(G) ≤ 5 provided edgewidth(G) ≥ k for some absolute constant k (possibly k = 4). Again, Example 6.1 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 [28] asserts that the best upper bound on χ_{c}(G) among loopless 𝕏-embedded graphs is of order Θ(g^{1/2}) where g denotes the genus of 𝕏. Upper bounds on χ_{c}(G) for loopless 𝕏-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.

Theorem 2.2. For any surface 𝕏 there exists an integer M such that for any 𝕏-embedded graph with edgewidth(G) ≥ M we have all of the following.

(a) If girth(G) ≥ 2, then χ_{c}(G) ≤ 5.

(b) If girth(G) ≥ 4, then χ_{c}(G) ≤ 4.

(c) If girth(G) ≥ 5, then χ_{c}(G) ≤ 3.

Statements (a) and (c) were proved by Thomassen [31, 32]. Statement (b) was proved by Fisk and Mohar [8]. Weaker versions of statement (c), requiring that girth(G) ≥ 6, appear in [8, 10, 17]. However, the proof in [8] only requires that M = O(log(genus(𝕏))), whereas Thomassen’s proofs require at least exponential edgewidth. Since there are graphs of arbitrarily large chromatic number and girth [6], and since embedded graphs G satisfy edgewidth(G) ≥ girth(G), the bound M in Theorem 2.2 must depend on the genus of 𝕏.

Examples 6.2 and 6.5 show that none of the bounds in Theorem 2.2 can be improved even fractionally for general surfaces 𝕏. In fact these examples satisfy χ_{loc}(G) = χ_{c}(G), so we can not improve Theorem 2.2 even with χ_{c}(G) replaced by χ_{loc}(G). However, if 𝕏 is orientable, Theorem 1.1 offers two possible improvements. Grünbaum’s Conjecture 2.1(b) would imply that all loopless graphs embedded on a fixed orientable surface with sufficiently high edge-width satisfy χ_{c}(G) ≤ 4+ε. Such a result would be best possible because of the Fisk triangulations (Example 6.7). The truth of Conjecture 2.1(c) would further improve this bound to χ_{c}(G) ≤ 3 + ε provided, additionally, that G is triangle-free.

3. Background and Definitions

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 walk in G refers to a walk in the undirected graph which underlies G. A 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. [24]. However, we shall use a slightly less standard treatment of embedded graphs where each edge and each face is oriented. An 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 faces. Associated with every face R ∈ F (G) is a boundary walk of R, which is a list v_{0}, e_{1}, v_{1}, …, 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 ≤ i ≤ k. We say that the face R has length k, and that R is incident with each vertex and edge in its boundary walk. The 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 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}, …, e_{d} in such a way that e_{i} and e_{i+1} (index modulo d) are consecutive at v for i = 1, …, d. This cyclic order is called the 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}, …, e_{k}, v_{k}, then R is associated with a regular k-gon π(R) ⊆ ℝ^{2}. The vertices and edges of π(R) correspond to those in the boundary of R. We call the ith edge of π(R) a copy of e_{i} ∈ E(G). We obtain |G| from the disjoint union of these polygons by identifying both copies of every edge e ∈ 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 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 π(R) for some R ∈ F (G), one obtains an embedding of G on a closed bordered surface which we denote |G| − R. For any surface 𝕏, we say that G is 𝕏-embedded if |G| is homeomorphic to 𝕏.

For every vertex v ∈ V (G) and edge e ∈ E(G), we define:

⟨v, e⟩ = \{ \begin{matrix}0 & if v and e are not incident \\ −1 & if v is the tail of e \\ 1 & if v is the head of e. \end{matrix}

If W = v_{0}, e_{1}, v_{1}, …, e_{k}, v_{k} is a walk of G, then we define

⟨e, W ⟩ = ∑_{{1≤i≤k|e=e_{i}}}⟨v_{i}, e_{i}⟩.

We say that e is a forward edge of W if ⟨e, W ⟩ > 0, and that e is a backward edge of W if ⟨e, W ⟩ < 0. If W is the boundary walk of a face R, then a forward edge of R is a forward edge of W, and we write ⟨e, R⟩ instead of ⟨e, W ⟩. In this case we have ⟨e, R⟩ ∈ {−2, −1, 0, 1, 2}, where ⟨e, R⟩ ∈ {−2, 0, 2} if e appears twice in the boundary of R. Next, we define the function τ : E(G) → ℤ by the following rule:

τ(e) = \frac{1}{2} ∑_{R∈F (G)}⟨e, R⟩.

Note that τ(e) ∈ {−1, 0, 1} for every e ∈ E(G). Further, τ(e) = 1 if e is a forward edge of two (not necessarily distinct) faces, τ(e) = −1 if e is a backward edge of two faces, and τ(e) = 0 if e is forward in one face and backward in another. Based on this, we define the sign of G to be the map σ : E(G) → ℤ given by the rule

σ(e) = (−1)^{τ(e)}.

The notion of the sign is equivalent to what is known as the signature of the dual graph (cf., e.g., [24]). Figure 1 may help the reader with these definitions.

Figure 1. Effect of edge and face orientations on τ and σ.

For any embedded graph G, we may obtain a new embedded graph by reversing an edge e ∈ E(G). This has the effect of changing the signs of ⟨v, e⟩, ⟨e, R⟩ and τ(e) (for R ∈ F (G) and v ∈ V (G)), but has no effect on σ(e) and |G|. An edgereorientation of G is any graph obtained from G by reversing a subset of E(G). Similarly, we may obtain a new embedded graph by reversing the boundary of a face R. This involves replacing the boundary walk of R by its reverse. Reversing the boundary of R changes ⟨e, R⟩ to −⟨e, R⟩ for every e ∈ E(G) and changes σ(e) to −σ(e) for every edge e with ⟨e, R⟩ = ±1. This change has no effect on |G|. An facereorientation of G is any graph obtained from G by reversing a subset of F (G). We say that |G| is orientable if the function σ 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 𝕊_{i} or ℕ_{j}, where i ≥ 0 and j ≥ 1. The value of i or j (the genus) indicates the number of handles (𝕊_{i}) or crosscaps (ℕ_{j}) that must be added to a sphere to obtain the surface. We have that |G| is orientable if and only if G is 𝕊_{i}-embedded for some i ≥ 0. We write 𝕏 = 𝕏′ to indicate that 𝕏 and 𝕏′ are homeomorphic surfaces.

If G is an embedded graph, we define its 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 ∈ E(G) there corresponds an (unoriented) edge e^{∗} ∈ E(G^{∗}) connecting the two (possibly identical) faces R, R′ ∈ 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 ω = R_{0}e_{1}R_{1}e_{2} … R_{k−1}e_{k}R_{k} of faces and edges of G is called a dual walk of G provided that R_{0}e_{1}^{∗}R_{1}e_{2}^{∗} … R_{k−1}e_{k}^{∗}R_{k} is a walk in G^{∗}. We say that ω is closed if R_{k} = R_{0}, and is simple if R_{i} ≠ R_{j} for 0 ≤ i < j < k. A closed dual walk ω is one-sided if ∏_{i=1}^{k} σ(e_{i}) = −1. Otherwise, ω is two-sided. A two-sided simple closed dual walk ω in G corresponds to the topological cylinder ∪_{R∈F (ω)}π(R) in |G|, whereas one-sided simple closed dual walks correspond to Möbius bands. Let us observe that |G| is orientable if and only if every simple closed dual walk of G is two-sided, cf. [24].

Let G be a directed graph or an embedded graph, and let Γ be an additive abelian group. A 0-chain (with respect to Γ) is a map from V (G) to Γ, a 1-chain (with respect to Γ) is a map from E(G) to Γ, and a 2-chain (with respect to Γ) is a map from F (G) to Γ. For i = 0, 1, 2, the i-chains form a group under componentwise addition, which we denote by C_{i}(G, Γ).

If c ∈ C_{0}(G, Γ), then we define the coboundary of c to be the map δc ∈ C_{1}(G, Γ) given by the rule δc(e) = ∑_{v∈V (G)}⟨v, e⟩c(v). If c ∈ C_{1}(G, Γ), then we define the coboundary of c to be the map δc ∈ C_{2}(G, Γ) given by the rule δc(R) = ∑_{e∈E(G)}⟨e, R⟩c(e). If c ∈ C_{1}(G, Γ), then we define the boundary of c to be the map ∂c ∈ C_{0}(G, Γ) given by the rule ∂c(v) = ∑_{e∈E(G)}⟨v, e⟩c(e). If c ∈ C_{2}(G, Γ), then we define the boundary of c to be the map ∂c ∈ C_{1}(G, Γ) given by the rule ∂c(e) = ∑_{R∈F (G)}⟨e, R⟩c(R).

If c^{1} is a 1-chain and c^{1} = δc^{0} for some 0-chain c^{0}, then we call c^{1} a tension or a Γ-tension. If ∂c^{1} = 0 then we call c^{1} a flow or a Γ-flow. If G is an embedded graph and δc^{1} = 0, then we call c^{1} a local tension or a local Γ-tension. If c^{1} = ∂c^{2} for some c^{2} ∈ C_{2}(G, Γ) then we call c^{1} a facial flow or a facial Γ-flow.

Of particular interest is the additive group of the reals ℝ, because real valued tensions, local tensions and flows are used to define the invariants χ_{c}, χ_{loc} and ϕ_{c}.

We denote the set of tensions, local tensions, flows, and facial-flows by T (G, Γ), L(G, Γ), F(G, Γ), and K(G, Γ), respectively. Note that all four of these sets are subgroups of C_{1}(G, Γ). Further, δδc = 0 for every 0-chain c and ∂∂c = 0 for every 2-chain c, so T (G, Γ) is a subgroup of L(G, Γ) and K(G, Γ) is a subgroup of F(G, Γ).

Let ϕ ∈ C_{1}(G, Γ), let d ∈ C_{1}(G, ℤ), and let g ∈ Γ. We define gd ∈ C_{1}(G, Γ) and d · ϕ ∈ Γ by the following rules:

(gd)(e) = d(e)g ,
d · ϕ = ∑_{e∈E(G)} d(e)ϕ(e).

The following arises from the definitions.

Proposition 3.1.

(a) T (G, Γ) = {ϕ ∈ C_{1}(G, Γ) | d · ϕ = 0 for every d ∈ F(G, ℤ)}.

(b) L(G, Γ) = {ϕ ∈ C_{1}(G, Γ) | d · ϕ = 0 for every d ∈ K(G, ℤ)}.

For any embedded graph G, the function τ ∈ C_{1}(G, ℤ) plays an important role. By its definition, 2τ is an integer sum of facial flows of the form e ↦ ⟨e, R⟩. In particular, τ is an integer valued member of F(G, ℝ). Since the space of integer flows F(G, ℤ) is a regular chain group (cf. Tutte [35]), it follows that

τ ∈ F(G, ℤ) and 2τ ∈ K(G, ℤ).  (3.1)

We define the homology group H_{1}(G, Γ) to be F(G, Γ)/K(G, Γ) and we define the cohomology group H^{1}(G, Γ) to be L(G, Γ)/T (G, Γ). These groups depend only on |G| and not on the particular structure of the graph (see, e.g. [9, 15]), so for a surface 𝕏 one can define H_{1}(𝕏, Γ) (H^{1}(𝕏, Γ)) to be the homology (cohomology) group of some (and hence any) 𝕏-embedded graph. The group H^{1}(G, Γ) 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, Γ) plays a key role.

For any abelian group Γ, we let Inv(Γ) denote the subgroup of Γ consisting of the elements of order at most 2. Then the cohomology groups of the surfaces are (cf., e.g., [15]):

H^{1}(𝕊_{i}, Γ) ≅ Γ^{2i}  and  H^{1}(ℕ_{j}, Γ) ≅ Γ^{j−1} × Inv(Γ).

In particular, any graph G embedded in ℕ_{1} satisfies L(G, Γ)/T (G, Γ) ≅ Inv(Γ). Thus we have the following.

Proposition 3.2. Let G be an ℕ_{1}-embedded graph, and let Γ be an abelian group. Then every local Γ-tension on G is a Γ-tension on G if and only if Inv(Γ) = {0}.

Observing that Inv(ℝ) = {0}, we have the following.

Corollary 3.3. For any graph G embedded on the sphere or projective plane we have χ_{loc}(G) = χ_{c}(G).

It is worth mentioning that on all other surfaces there exist graphs with arbitrarily large edge-width satisfying χ_{loc}(G) < χ_{c}(G).

We will use Proposition 3.1 to detect if a local tension is a tension, so the homology group H_{1}(𝕏, ℤ) also plays a role in our argument. It is well-known [9, 15] that

H_{1}(𝕊_{i}, ℤ) ≅ ℤ^{2i}  and  H_{1}(ℕ_{j}, ℤ) ≅ ℤ^{j−1} × ℤ/2ℤ.

In particular, Inv(H_{1}(𝕏, ℤ)) is trivial if and only if 𝕏 is orientable. For any 𝕏embedded graph G and any flow ψ ∈ F(G, ℤ), let ⟨ψ⟩ denote the coset ψ+K(G, ℤ) ∈ H_{1}(G, ℤ). This coset is called the homology class of ψ. Thus ⟨0⟩ is the set of facial ℤ-flows in G. We have from (3.1) that ⟨τ⟩ ∈ Inv(H_{1}(G, ℤ)). Thus τ ∈ K(G, ℤ) if 𝕏 is orientable. Conversely, if τ ∈ K(G, ℤ), then one can transform τ to be identically zero by reversing some faces of G, so 𝕏 is orientable. Thus we have

Inv(H_{1}(G, ℤ)) = \{ \begin{matrix}\{⟨0⟩\} & if |G| is orientable \\ \{⟨0⟩, ⟨τ⟩\} & if |G| is not orientable. \end{matrix}  (3.2)

For certain groups Γ, it is not true that every local Γ-tension can be modified to a Γ-tension by means of ‘small adjustments’. In Section 5 we offer an example illustrating this. In Theorem 4.1 we show that such an adjustment is possible provided the local tension satisfies an additional property. A local Γ-tension ϕ is strong if it satisfies

τ · ϕ = 0.

Let L^{+}(G, Γ) denote the set of strong local Γ-tensions of G. In view of Proposition 3.1(b) we see that L^{+}(G, Γ) is the subgroup of L(G, Γ) defined by

L^{+}(G, Γ) = {ϕ ∈ C_{1}(G, Γ) | d · ϕ = 0 for every d ∈ {τ} ∪ K(G, ℤ)}.  (3.3)

Of course one may substitute for ‘τ’ in (3.3) any other element of the homology class ⟨τ⟩. Consequently, the definition of ‘strong’ does not depend on a particular face orientation of G. If ϕ is a local Γ-tension of G, then from (3.1) we have 2(τ · ϕ) = (2τ) · ϕ = 0. Thus τ · ϕ ∈ Inv(Γ). Using this, the following is easily proved.

Proposition 3.4. If |G| is orientable or Inv(Γ) = {0}, then L^{+}(G, Γ) = L(G, Γ). In particular, every local ℝ-tension is a strong local ℝ-tension.

The group containment relations are

T (G, Γ) ≤ L^{+}(G, Γ) ≤ L(G, Γ)

with L(G, Γ)/L^{+}(G, Γ) ≅ Inv(Γ). Like the cohomology group, the quotient group H^{+}(G, Γ) = L^{+}(G, Γ)/T (G, Γ) depends only on the surface |G|. So, for a surface 𝕏, we define H^{+}(𝕏, Γ) to be H^{+}(G, Γ) for any 𝕏-embedded graph G. In comparison with the cohomology groups, we have

H^{+}(𝕊_{i}, Γ) ≅ Γ^{2i}  and  H^{+}(ℕ_{j}, Γ) ≅ Γ^{j−1}.

Let G be an embedded graph. For any walk W in G we define the walk indicator map I_{W} ∈ C_{1}(G, ℤ) by the rule

I_{W} (e) = ⟨e, W ⟩.

If W is a closed walk, then I_{W} ∈ F(G, ℤ). If, additionally, W is a contractible curve on |G|, then I_{W} ∈ K(G, ℤ) is a facial flow. If I_{W} ∉ K(G, ℤ), but 2I_{W} ∈ K(G, ℤ), then we say that W is a semifacial walk. By (3.1) and (3.2) of Section 3, W is semifacial if and only if |G| is not orientable and ⟨I_{W} ⟩ = ⟨τ⟩. 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 τ(e) is nonzero (or σ(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 ϕ ∈ C_{1}(G, Γ). A closed walk W is conservative for ϕ if I_{W} · ϕ = 0. Let Y be a set of closed walks in G. We say that Y generates H_{1}(G, ℤ) if {⟨I_{W} ⟩ | W ∈ Y } generates H_{1}(G, ℤ). The following allows one to test whether a local Γ-tension is strong, and whether it is a tension.

Proposition 3.5. Let ϕ ∈ L(G, Γ).

(i) If W is a semifacial walk in G, then ϕ ∈ L^{+}(G, Γ) if and only if W is conservative for ϕ.

(ii) If Y is a set of closed walks that generates H_{1}(G, ℤ), then ϕ ∈ T (G, Γ) if and only if every member of Y is conservative for ϕ.

Proof. Part (i) follows immediately from equation (3.2) and the comment after (3.3) in Section 3. Part (ii) follows from Proposition 3.1(a). □

We define now a class of ‘elementary’ strong local tensions, which will be used to prove the main theorem. Let ω = R_{0}, e_{1}, R_{1}, …, e_{k}, R_{0} be a simple closed dual walk in an embedded graph G. Suppose ω is two-sided, and thus corresponds to a cylinder in |G|. Then ω corresponds to a circuit ω^{∗} in G^{∗}. Using a fixed orientation of the cylinder (which is an orientable bordered surface), we orient the edges of ω^{∗} consistently with ω according to the left-to-right rule. We define a map Ω_{ω} ∈ C_{1}(G, ℤ) according to the rule

Ω_{ω}(e) = \{ \begin{matrix}I_{ω^{∗}}(e^{∗}) & if e ∈ E(ω) \\ 0 & otherwise, \end{matrix}

where I_{ω^{∗}} is the {0, ±1}-valued indicator function of ω^{∗}. By definition we have, for any face R ∈ F (G), that I_{R}·Ω_{ω} = 0. Therefore Ω_{ω} ∈ L(G, ℤ) by Proposition 3.1(b). It is possible to reorient the faces of ω so that τ(e) = 0 for every e ∈ E(ω). For this face-reorientation we have τ · Ω_{ω} = 0. In view of (3.3), we have shown the following.

Proposition 3.6. If ω is a simple closed two-sided dual walk in an embedded graph G, then gΩ_{ω} ∈ L^{+}(G, Γ) for every g ∈ Γ.

4. From strong local tensions to tensions

The goals of this section are to prove the following general result, and then to prove its main application, Theorem 1.1.

Let Γ be an additive abelian group. If Q ⊆ Γ, and k is a positive integer, then we let kQ = ∑_{i=1}^{k} Q. We say that Q is a k-part of Γ if 0 ∈ Q, Q = −Q, and kQ = Γ.

Theorem 4.1. Let 𝕏 be a surface and let k be a positive integer. Then there exists an integer M such that for every 𝕏-embedded graph G with edgewidth(G) ≥ M, every abelian group Γ, every k-part Q of Γ, and every ϕ ∈ L^{+}(G, Γ), there is a ϕ′ ∈ T (G, Γ) with ϕ(e) − ϕ′(e) ∈ 2Q for every e ∈ E(G).

We shall require the notion of a surface minor. Let G be an embedded graph, let e ∈ 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 contracting the edge e. If e occurs in the boundary of distinct faces R_{1} and R_{2}, and σ(e) = 1, then we let G \ 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 \ e is obtained from G by 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 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 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 σ(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 face-width of G, written facewidth(G), to be the minimum cardinality of the point set G ∩ C among all noncontractible curves C in |G|. It is easy to see that facewidth(G) ≤ edgewidth(G). We shall first prove that Theorem 4.1 holds for graphs of high face-width. Later, we describe a reduction that extends the result to graphs of high edge-width.

Theorem 4.2 (Robertson and Seymour [27]). For every 𝕏-embedded graph H, there exists an integer M such that every 𝕏-embedded graph G with facewidth(G) ≥ M contains a surface minor isomorphic to H.

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 subdivision of H.

For h = 1, 2, …, let T_{h} be the 𝕊_{h}-embedded graph which is represented in Figure 2(a) for the case h = 3. The surface is obtained by taking the regular 4h-gon (called the fundamental polygon) with sides a_{1}, b_{1}, a_{1}^{−}, b_{1}^{−}, …, a_{h}, b_{h}, a_{h}^{−}, b_{h}^{−} and identifying each a_{i} with a_{i}^{−} and b_{i} with b_{i}^{−}, i = 1, …, h, using the orientations shown in Figure 2. Similarly, we let U_{h} be the ℕ_{h}-embedded graph as shown in Figure 2(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}^{−}, …, 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}, …, b_{g}^{−}, c, c. Figure 2 also shows a collection of circuits in T_{h}, denoted by A_{1}, B_{1}, …, A_{h}, B_{h}, and a collection of circuits in U_{h}, denoted by A_{1}, B_{1}, …, 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.

Figure 2. Embedded graphs T_{3} and U_{6}

If Q is a circuit of G/e, then exactly one of E(Q) or E(Q) ∪ {e} is the edge set of a circuit Q′ in G. We say that this circuit Q′ corresponds to Q. More generally, if H is a surface minor of G and Q ⊆ H is a circuit, then there is a unique circuit Q′ ⊆ G which corresponds to Q. If Y is a collection of circuits of H, then we say that Y′ = {Q′ ⊆ G | Q′ corresponds to some Q ∈ Y } 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 3 apply.

Lemma 4.3. Let G be a graph embedded in the surface 𝕊_{h} (h ≥ 1) or ℕ_{r}, where r ∈ {2h + 1, 2h + 2} and h ≥ 0. Suppose that G has a surface subgraph which is a subdivision of T_{h} or U_{r}, respectively. Let A′_{1}, B′_{1}, …, A′_{h}, B′_{h} (and C′ and D′ if applicable) be the circuits of G which correspond to A_{1}, B_{1}, …, A_{h}, B_{h} (and C and D if applicable). Then we have:

(i) A′_{1}, B′_{1}, …, A′_{h}, B′_{h} (and C′ and D′ if applicable) generate H_{1}(G, ℤ).

(ii) If |G| = ℕ_{2h+1}, then C′ is semifacial; if |G| = ℕ_{2h+2}, then D′ is semifacial.

Proof. Part (i) follows by construction. Indeed these circuits minimally generate the free homotopy group π_{1}(|G|). For part (ii), suppose 𝕏 = ℕ_{2h+2}. We observe from Figure 2(b) that we may reorient the faces of G so that an edge e ∈ E(G) has τ(e) = ±1 if and only if e ∈ E(D′), so I_{D′} belongs to the homology class ⟨τ⟩. In case 𝕏 = ℕ_{2h+1}, the argument is similar, but with D′ replaced by C′. □

Next we define two families of embedded graphs, T_{h}^{k} and U_{h}^{k} (h ≥ 1, k ≥ 1) as follows. We start with the embedded graph T_{h} or U_{h}. Let g = h for T_{h} and g = ⌊(h − 1)/2⌋ for U_{h}. Then we add, for i = 1, …, g, two families of k + 1 pairwise disjoint circuits of length k + 3 each (as shown in Figure 3) 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 3.

Figure 3. Embedded graph U_{6}^{3} and some dual walks Lemma 4.4. Let k ≥ 1 be an integer. Let G be a graph embedded in the surface 𝕏 = 𝕊_{h} with h ≥ 1, or in 𝕏 = ℕ_{r}, where r ∈ {2h + 1, 2h + 2} and h ≥ 0. Suppose that G contains T_{h}^{k} (or U_{r}^{k}, respectively) as a surface minor. Let A′_{1}, B′_{1}, …, A′_{h}, B′_{h} (and C′ if 𝕏 = ℕ_{2h+1}, and C′, D′ if 𝕏 = ℕ_{2h+2}) be the circuits of G which correspond to A_{1}, B_{1}, …, A_{h}, B_{h} (and C and D if applicable). Let P = ⋃_{i=1}^{h}(E(A′_{i}) ∪ E(B′_{i})) ∪ E(C′) ∪ E(D′) (where E(C′) and E(D′) are added only when applicable). Then there exist in G simple closed dual walks α_{i}^{j}, β_{i}^{j} (and γ^{j} if 𝕏 = ℕ_{2h+2}) for 1 ≤ i ≤ h and 1 ≤ j ≤ k with the following properties:

(i) Every face of G occurs in at most two of the dual walks α_{i}^{j}, β_{i}^{j}, γ^{j}.

(ii) The dual walks α_{i}^{j}, β_{i}^{j}, γ^{j} are all two-sided.

(iii) α_{i}^{j} contains exactly one edge of A′_{i} and no edges in P \ E(A′_{i}).

(iv) β_{i}^{j} contains exactly one edge of B′_{i} and no edges in P \ E(B′_{i}).

(v) If 𝕏 = ℕ_{2h+2}, then γ^{j} contains exactly one edge of C′ and no edges in P \ E(C′).

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 3. 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 dual walks with the stated properties. If an edge was contracted, then the dual walks of G′ are dual walks of G with the required properties. If an edge was deleted to form a face R, then we adjust each dual walk containing R in the obvious manner. It is easy to verify that the resulting dual walks still satisfy (i)–(v). □

We are ready to prove the following lemma, which is identical to Theorem 4.1 except that edge-width is replaced here by face-width.

Lemma 4.5. Let 𝕏 be a surface and let k be a positive integer. Then there exists an integer M, so that for every 𝕏-embedded graph G with facewidth(G) ≥ M, every abelian group Γ, every k-part Q of Γ, and every ϕ ∈ L^{+}(G, Γ), there is a ϕ′ ∈ T (G, Γ) with ϕ(e) − ϕ′(e) ∈ 2Q for every e ∈ E(G).

Proof. We apply Theorem 4.2 to find an integer M so that every 𝕏-embedded graph with face-width ≥ M contains T_{h}^{k} as a minor if 𝕏 = 𝕊_{h}, and so that it contains U_{r}^{k} as a minor if 𝕏 = ℕ_{r}, where r = 2h + 1 or r = 2h + 2. Let G be an 𝕏-embedded graph with facewidth(G) ≥ M, and let ϕ ∈ L^{+}(G, Γ). Let A′_{1}, B′_{1}, …, A′_{h}, B′_{h}, (and C′ if 𝕏 = ℕ_{2h+1}, and C′, D′ if 𝕏 = ℕ_{2h+2}) be the circuits of G which correspond to A_{1}, B_{1}, …, A_{h}, B_{h} (and C and D if applicable) of T_{h}^{k} or U_{r}^{k}. Choose dual walks α_{i}^{j}, β_{i}^{j}, (and γ^{j} if 𝕏 = ℕ_{2h+2}) in accordance with Lemma 4.4. Let x_{i}^{j}, y_{i}^{j}, z^{j} be variables in Γ, for 1 ≤ i ≤ h and 1 ≤ j ≤ k. Consider the function

ϕ′ = ϕ + ∑_{i,j} x_{i}^{j}Ω_{α_{i}^{j}} + ∑_{i,j} y_{i}^{j}Ω_{β_{i}^{j}} + ∑_{j} z_{j}Ω_{γ^{j}},

disregarding inapplicable terms. It follows from Proposition 3.6 that ϕ′ ∈ L^{+}(G, Γ). Furthermore, by properties (ii)–(v) of Lemma 4.4 and the assumption that Q is a k-part, we may choose x_{i}^{j}, y_{i}^{j}, (and z^{j} if 𝕏 = ℕ_{2h+2}) in Q so that A′_{1}, B′_{1}, …, A′_{h}, B′_{h} (and C′ if 𝕏 = ℕ_{2h+2}) are all conservative for ϕ′. By Lemma 4.3(ii) the circuit C′ (if 𝕏 = ℕ_{2h+1}), or D′ (if 𝕏 = ℕ_{2h+2}) is semifacial. Since ϕ′ ∈ L^{+}(G, Γ), we have by Proposition 3.5(i) that C′ and D′ are conservative for ϕ′ in these two cases.

Applying Lemma 4.3(i) and Proposition 3.5(ii) we have that ϕ′ is a tension as claimed. Finally, it follows from Lemma 4.4(i) (and the fact that the dual walks are simple) that ϕ′(e) − ϕ(e) ∈ 2Q for every e ∈ E(G). □

The value of M in the above proof is provided by Theorem 4.2. Although the paper [27] does not provide explicit bounds on M, reasonably small bounds can be obtained using results of [3] and [14], see [22] for more details.

Let R be a face of the embedded graph G whose boundary walk C_{0} has length k ≥ 4. Next we define a graph H embedded 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}, …, C_{k}, each of length k, inside the face R. For 1 ≤ i ≤ k, we add a perfect matching between the vertices of C_{i−1} and C_{i}. The construction is illustrated in Figure 4. For 1 ≤ i ≤ 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 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.

Figure 4. Adding a chimney in a face of length 5

Proposition 4.6. 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.

Proof of Theorem 4.1: Let 𝕏, k, G, Γ, Q, and ϕ ∈ L^{+}(G, Γ) be as stated in the theorem, and let M be the constant of Lemma 4.5. We form the embedded graph G′ by adding a chimney to every face of G of length ≥ 4. Proposition 4.6 shows that Lemma 4.5 can be applied to G′. Define ψ ∈ C_{1}(G′, Γ) so that ψ(e) = ϕ(e) for e ∈ E(G), and for every chimney, each edge of C_{1}, …, 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 ∈ Γ. Then it is easy to see that ψ ∈ L^{+}(G′, Γ). Therefore, we may choose ψ′ ∈ T (G′, Γ) so that ψ′(e) − ψ(e) ∈ 2Q for every e ∈ E(G′). It now follows that ϕ′ = ψ′|_{E(G)} is a tension of G with the required properties. □

Before proving Theorem 1.1, we must express χ_{c}(G) in terms of a group which is suited to the application of Theorem 4.1. We consider the circle group 𝕆 = ℝ/ℤ. We identify 𝕆 with the half open interval [0, 1) in the usual way. For x ∈ 𝕆, we let ∥x∥ = min{x, 1 − x}. The term ‘circular chromatic number’ is etymologically based on the following formula which appears, for example, in [37].

Proposition 4.7. For any graph G we have

\frac{1}{χ_{c}(G)} = max_{ϕ∈T (G,𝕆)} min_{e∈E(G)} ∥ϕ(e)∥.

Proof of Theorem 1.1: Let k = 5+⌈\frac{25}{ε}⌉, and apply Theorem 4.1 to obtain a positive integer M_{0} based on the surface 𝕏 and the integer k. Let M = max(M_{0}, M_{1}) where M_{1} is the integer supplied by Theorem 2.2(a). Let G be a loopless graph embedded in 𝕏 with edge-width at least M. Define α = χ_{loc}(G). By the choice of M_{1}, we have α ≤ χ_{c}(G) ≤ 5.

Let ψ ∈ C_{1}(G, ℝ) be a local α-tension of G. Define ϕ ∈ C_{1}(G, 𝕆) by the rule ϕ(e) = ψ(e)/α, so that ϕ(e) ∈ [\frac{1}{α}, \frac{α−1}{α}], for e ∈ E(G). Since Inv(ℝ) = \{0\}, Proposition 3.4(b) implies that ψ is a strong local ℝ-tension. Consequently ϕ is a strong local 𝕆-tension. The interval [−\frac{1}{2k} , \frac{1}{2k} ] is a k-part of 𝕆, so by choice of M_{0}, there exists an 𝕆-tension ϕ′ such that ϕ(e) − ϕ′(e) ∈ [−\frac{1}{k} , \frac{1}{k} ]. Thus ϕ′(e) ∈ [\frac{1}{α} − \frac{1}{k} , \frac{α−1}{α} + \frac{1}{k} ]. By Proposition 4.7 we have χ_{c}(G) ≤ (\frac{1}{α} − \frac{1}{k} )^{−1}. Therefore

χ_{c}(G) − χ_{loc}(G) ≤ \frac{αk}{k − α} − α = \frac{α^{2}}{k − α} ≤ \frac{25}{k − 5} ≤ ε

as claimed. □

5. Two families of embedded graphs

In this section we study two families of embedded graphs G for which χ_{loc}(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 1.2. When G has large edge-width, we may apply our main theorem to obtain the bimodal behaviour of χ_{c}(G) described in Corollary 1.3.

In both applications, we need a way to deduce lower bounds on χ_{loc}(G). We use a method based on edge-reorientations. For any closed walk W in a directed graph H, we define the imbalance of W in H to be

imbal_{H}(W) = 1 + max \{\frac{w^{+}(W)}{w^{−}(W)}, \frac{w^{−}(W)}{w^{+}(W)}\}

where

w^{+}(W) = ∑{⟨e, W ⟩ | ⟨e, W ⟩ > 0},
w^{−}(W) = ∑{−⟨e, W ⟩ | ⟨e, W ⟩ < 0}.

We allow the value imbal_{H}(W) = ∞ if one of w^{+}(W), w^{−}(W) equals zero. Suppose W = v_{0}e_{1}v_{1} … 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 ≥ 0 we have s = w^{+}(W) + c and t = w^{−}(W) + c. Therefore, one can approximate

imbal_{H}(W) ≥ \frac{s + t}{min(s, t)}  (5.1)

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 [21] that χ(G) can be expressed in terms of circuit imbalance. The following analogous result for χ_{c}(G) appears in [12].

Theorem 5.1. For any graph G we have

χ_{c}(G) = min_{H} max_{W} imbal_{H}(W),  (5.2)

where H ranges over all edge-reorientations of G, and W ranges over the circuits in H.

An analogous ‘Minty-like’ result exists for χ_{loc}(G). It is obtained by restricting the set over which W ranges in equation (5.2). Since we only require lower bounds on χ_{loc} in this paper, we state and prove only the ‘easy direction’ of this analogue. A closed walk W in an embedded graph G is homologically trivial if I_{W} ∈ K(G, ℤ).

Proposition 5.2. Let G be an embedded graph and let α ∈ ℝ. If for every edgereorientation H of G there exists a homologically trivial closed walk W such that imbal_{H}(W) ≥ α, then χ_{loc}(G) ≥ α.

Proof. By the definition of χ_{loc}(G), there exists an edge-reorientation H of G, and ϕ ∈ L(H, ℝ) such that 1 ≤ ϕ(e) ≤ χ_{loc}(G) − 1 for e ∈ E(G). Choose W in H as in the statement. By Proposition 3.1(a) we have

∑_{e∈W}⟨e, W ⟩ϕ(e) = 0.

By separating out those terms in the summation for which ⟨e, W ⟩ < 0, and using 1 ≤ ϕ(e) ≤ χ_{loc}(G) − 1, it follows easily that

imbal_{H}(W) ≤ 1 + max_{e∈E(W)}{ϕ(e)} ≤ χ_{loc}(G).
□

The converse of Proposition 5.2 appears in [13]. We do not present it here since we do not need it and its proof is more involved.

Let G be an 𝕏-embedded even-faced graph. We say that G is of even (odd) type if the number of edges e with σ(e) = −1 is even (odd). Thus the type of G has the same parity as the integers ∑_{e∈E(G)} τ(e) and τ · τ. Since reorienting a face changes σ(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 [1, 23, 26, 36], but under several different, more geometric characterizations. For example Archdeacon et al. [1] 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 [23] show that the type of G can also be expressed as the parity of the number of ‘odd crosscaps’ in 𝕏 = N_{g}, where a crosscap in 𝕏 = 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.

Lemma 5.3. Let G be an even-faced embedded graph with maximum face length 2r. The following are equivalent:

(a) G is of even type.

(b) The edges of G can be reoriented so that each boundary walk has exactly half of its edges oriented in each direction.

(c) Some (and thus every) Euler tour of G^{∗} is a two-sided closed walk.

(d) χ_{loc}(G) = 2.

(e) χ_{loc}(G) < 2 + 2/(r − 1).

Proof. We prove (b) ⇒ (a) ⇒ (c) ⇒ (b) ⇒ (d) ⇒ (e) ⇒ (b). Consider the equation

∑_{R∈F (G)} ∑_{e∈E(G)}⟨e, R⟩ = 2 ∑_{e∈E(G)} τ(e)  (5.3)

By the definitions, G is of even type if and only if the right hand side of (5.3) 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 (5.3) 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}, …, e_{k}, R_{k} be the dual walk of G corresponding to an Euler tour in G^{∗}. For i = 2, 3, …, 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 (5.3) vanish except, possibly, ∑_{e∈E(G)}⟨e, R_{0}⟩. 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 ϕ ≡ 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 (5.1), 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 ≤ r, this implies imbal_{G}(W) ≥ 2 + 2/(r − 1). Applying Lemma 5.2, we have χ_{loc}(G) ≥ 2 + 2/(r − 1). Thus (e) implies (b). □

Remark 5.4.

(1) If embeddings of graphs are represented combinatorially by rotation systems and signatures [24], then statement (c) is equivalent to the dual G^{∗} having an odd number of edges with negative signature.

(2) 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 χ_{c}(G) ≥ 2 + 2/(r − 1) given by part (e) can be improved to χ_{c}(G) ≥ χ_{c}(G′) ≥ 2 + 2/(r′ − 1). It follows that Lemma 5.3 holds true with the weaker hypothesis that some surface subgraph of G has maximum face length 2r.

(3) More can be said about χ_{c}(G) and χ_{loc}(G) in case |G| is the projective plane. In particular, the strengthened version of the previous remark gives an exact formula for χ_{c}(G) in this case (cf. Example 6.8).

Next we shall classify locally 3-colorable triangulations. Let G be a triangulation of a surface 𝕏. We say that G is of even type if for every closed dual walk ω = R_{0}, e_{1}, R_{1}, …, e_{k}, R_{0}, the number of indices i (1 ≤ i ≤ k) with σ(e_{i}) = 1 is even. A triangulation is of odd type if it is not of even type. Reversing a face of G changes σ(e_{i}) for an even number of indices i, so the type of G does not depend on face or edge orientations.

Lemma 5.5. Let G be a triangulation of some surface, such that G has no surfaceseparating loops. The following are equivalent:

(a) G is of even type.

(b) The faces of G can be reoriented so that σ(e) = −1 for every e ∈ E(G).

(c) Every two-sided closed walk in G^{∗} has even length and every one-sided closed walk in G^{∗} has odd length.

(d) χ_{loc}(G) = 3.
(e) χ_{loc}(G) < 4.

Proof. We prove that (b) ⇒ (c) ⇒ (a) ⇒ (b) ⇒ (d) ⇒ (e) ⇒ (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 dual walk R_{0}, e_{1}, R_{1}, …, e_{k}, R_{0}, the number of indices i for which σ(e_{i}) = −1 has the same parity as k. Thus the number of indices i for which σ(e_{i}) = 1 equals k − |{i | σ(e_{i}) = −1}|, which is even. Thus (c) implies (a). Suppose (a) holds. Choose a face R ∈ F (G), and let X be the set of faces Q ∈ F (G) such that there exists a dual walk R_{0}, e_{1}, R_{1}, …, e_{k}, R_{k} with R_{0} = R, R_{k} = Q, and with |{i | 1 ≤ i ≤ k, σ(e_{i}) = 1}| odd. Let Y = F (G) \ X. Since no closed dual walk has an odd number of edges e with σ(e) = 1, it follows that an edge e ∈ E(G) has σ(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 ⊆ E(G^{∗}). Let M′ be the corresponding set of edges in G. Condition (b) implies τ(e) = ±1 for e ∈ E(G). Therefore the map ϕ : E(G) → ℝ given by the rule

ϕ(e) = \{ \begin{matrix}2 τ(e) & if e ∈ M′ \\ −τ(e) & otherwise \end{matrix}

is a local 3-tension. Thus (b) implies (d). Trivially we have (d) implies (e). Finally, suppose that (e) is true. By Lemma 5.2, 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 σ(e) = 1 for some e ∈ 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). □

Remark 5.6. If we wish to allow surface-separating loops in Lemma 5.5, 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) ⇒ (d). Conversely, in the proof of (e) ⇒ (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’.

We make two observations concerning the characterizations of Lemmas 5.3 and 5.5. First, if 𝕏 is orientable, then every 𝕏-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 5.3(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., σ(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 5.5(c).

Proof of Theorem 1.2: This follows from parts (a), (d) and (e) of Lemma 5.3. and from parts (a), (d) and (e) of Lemma 5.5. □

6. Examples

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 χ(G) and ⌈ϕ_{c}(G)⌉. Example 6.1 is classic. Variations and special cases of Exaples 6.2 and 6.5 appear in [1, 17, 18, 23, 36]. Example 6.7 is due to Fisk [7], and Theorem 6.9 is due to Goddyn [11]. Example 6.4 and Theorem 6.6 are new to our knowledge.

Example 6.1. 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 3.3 and the well known fact that χ_{c}(K_{n}) = n, we have χ_{loc}(K) = χ_{c}(K) = 6, whereas ϕ_{c}(K^{∗}) = 5. This example shows that no improvement is possible in conjectures of Bouchet and DeVos regarding χ_{loc}, as discussed after Conjecture 2.1.

Example 6.2. For any nonorientable surface 𝕏, there exist 3-connected quadrangulations Q and hexangulations H of odd type and arbitrarily large edge-width which satisfy χ_{c}(Q) ≥ χ_{loc}(Q) ≥ 4, χ_{c}(H) ≥ χ_{loc}(H) ≥ 3, and ϕ_{c}(Q^{∗}) = ϕ_{c}(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.

Proposition 6.3. For every integer r ≥ 1 and every nonorientable surface 𝕏, there exists an even-faced 𝕏-embedded graph G_{r} of odd type and arbitrarily large edgewidth, such that every shortest circuit bounds a face of length 2r. Furthermore, G_{r} is 3-connected if r ∈ {2, 3}.

By Lemma 5.3(e), we have χ_{c}(G_{r}) ≥ χ_{loc}(G_{r}) ≥ 2 + 2/(r − 1). In fact we have that χ_{c}(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 ∈ {4, 6}, then the upper bounds in parts (b) and (d) of Theorem 2.2 imply that χ(G_{r}) = χ_{c}(G_{r}) = χ_{loc}(G_{r}) = 2 + 2/(r − 1). Therefore one can not improve the bounds in parts (b), (c) and (d) of that Theorem.

Example 6.4. This example shows that Theorem 4.1 is false without the assumption that ϕ ∈ L^{+}(G, Γ). Let G be an even-faced embedded graph of odd type and maximum face length 2r. The constant function ϕ(e) ≡ 1/2 is clearly a local 𝕆tension where 𝕆 = ℝ/ℤ, but ϕ is not strong since τ · ϕ = 1/2. By Theorem 1.2(a) we have χ_{c}(G) ≥ 2r/(r − 1). Thus by Proposition 4.7 every 𝕆-tension ϕ′ satisfies

min_{e∈E(G)} ∥ϕ′(e)∥ ≤ \frac{1}{χ_{c}(G)} ≤ \frac{1}{2} − \frac{1}{2r} .

Thus the conclusion of Theorem 4.1 fails when Q is the k-part [\frac{−1}{2k}, \frac{1}{2k} ] of 𝕆, for any k > r.

Example 6.5. Hutchinson et al. [18] 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.

Theorem 6.6. 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 χ(H) ≥ χ_{c}(H) ≥ χ_{loc}(H) ≥ 5.

Proof. Let H′ be an arbitrary edge-reorientation of H, and let G′ denote the subgraph of H′ corresponding to G. By Lemma 5.3(b) there is a face R of G′ whose boundary walk W satisfies imbal_{G′}(W) ≥ 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′) ≥ 5. The walk W′ is homologically trivial. Therefore χ_{loc}(H) ≥ 5 by Proposition 5.2. □

If, additionally, H has high edge-width, then Theorem 2.2(a) implies that χ(H) = χ_{c}(H) = χ_{loc}(H) = 5. Therefore, this upper bound is best possible in a strong sense.

Example 6.7. The following examples show that for every surface 𝕏 different from the sphere there exist 5-connected triangulations F of odd type and arbitrarily large edge-width which satisfy ϕ_{c}(F^{∗}) = 3 and χ_{c}(F) > 4. It seems likely that when 𝕏 is orientable we have 4 = χ_{loc}(F) < χ_{c}(F) < 4 + ε where ε approaches zero as edge-width increases. Fisk [7] showed that any triangulation G with exactly two odd-degree vertices satisfies χ_{c}(G) > 4 provided the two vertices are adjacent. Such Fisk triangulations exist of arbitrary edge-width on every surface except the sphere (cf., e.g., [33]). We suspect that Fisk triangulations G of orientable surfaces usually satisfy χ_{loc}(G) = 4. This is a special case of Grünbaum’s Conjecture 2.1(b). By Theorem 1.1 this would imply that χ_{c}(G) is vanishingly close to 4 for high edge-width Fisk triangulations of orientable surfaces. In summary, Fisk triangulations have the advantage over Example 6.5 of existing on orientable surfaces (other than the sphere), but the disadvantage of having a smaller local circular chromatic number.

Example 6.8. 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 χ_{c}(G) = χ_{loc}(G) by Corollary 3.3. This allows one to set ε = 0 in the statements of Theorems 1.1, 1.3, and 4.1.

Second, a circuit in G is noncontractible in ℕ_{1} if and only if it is semifacial. Consequently, if G is a triangulation of ℕ_{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 ℕ_{1}-embedded graph has even type if and only if it is bipartite.

Third, the homotopy group of ℕ_{1} is ℤ/2ℤ. This makes it possible to classify the circuits of G and apply the Minty formula, Theorem 5.1. In this way Goddyn [11] has derived an exact formula for even-faced graphs on ℕ_{1}.

Theorem 6.9. Let G be a loopless even-faced ℕ_{1}-embedded graph. Then either χ_{c}(G) = 2 or χ_{c}(G) = 2 + 2/(r − 1) where r is the smallest integer such that some surface subgraph has maximum face length 2r.

For example, a projective planar even-faced graph G has χ_{c}(G) = 4 if and only if it is loopless, nonbipartite and contains a quadrangulation of ℕ_{1} as a surface subgraph. Similarly, χ_{c}(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, χ_{c}(G) ≤ 8/3. Any hexangulation H of ℕ_{1} satisfies χ_{c}(H) ∈ {2, 3, 4, ∞}, and every quadrangulation Q of ℕ_{1} satisfies χ_{c}(Q) ∈ {2, 4, ∞}. The latter result strengthens that of Youngs [36], which considers only χ(Q). Gimbel and Thomassen [10] have proved a related result that holds for embedded graphs which are not even-faced: a loopless ℕ_{1}-embedded graph with no contractible triangles satisfies χ_{c}(G) ≤ 3 if and only if it contains no nonbipartite quadrangulation as a surface subgraph.

One application regards the well-known Mycielski transformation [25], which constructs, from any simple graph G, a new graph μ(G) having the same clique number as G, but χ(μ(G)) = χ(G) + 1. For any odd circuit C_{2k+1}, the graph μ(C_{2k+1}) embeds on ℕ_{1} as a quadrangulation of odd type. Our results imply that χ_{c}(μ(C_{2k+1})) = 4 even though χ_{c}(C_{2k+1}) = 2 + 1/k. This result already appears in [4]. 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 [30].

7. 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 (the interiors of) some of the faces. The boundaries of the removed faces are then called the boundary components of the resulting bordered surface. We do not require that the boundary components be disjoint.

We define the 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 𝕏 with boundary components Q_{1}, …, Q_{r}. Let G̃ be the graph embedded in a (closed) surface 𝕏̃ which is obtained as follows. First, we add a chimney to every boundary component Q_{i} (1 ≤ i ≤ 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 G̃ in 𝕏̃ is equal to the edge-width of G in 𝕏. Moreover, every (local) tension in G determines a (local) tension in 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 1.1 and Corollary 1.3(a).

Theorem 7.1. Let 𝕏 be a bordered surface and let ε > 0. There exists an integer M so that every graph G embedded in 𝕏 with edge-width at least M satisfies

χ_{loc}(G) ≤ χ_{c}(G) ≤ χ_{loc}(G) + ε.

Corollary 7.2. For every fixed bordered surface 𝕏 and every ε > 0, there exists an integer M such that for every even-faced 𝕏-embedded graph G with maximum face length 2r and with edge-width at least M,

χ_{c}(G) ∈ [2, 2 + ε] ∪ [2 + 2/(r − 1), 4].

Let us further remark, for example, that Corollary 7.2 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.

References

[1] 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.

[2] A. Bouchet, Nowhere-zero integral flows on a bidirected graph, J. Combin. Theory Ser. B 34 (1983) 279–292.

[3] 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.

[4] G. Chang, L. Huang, X. Zhu, Circular chromatic numbers of Mycielski’s graphs, Discrete Math. 205 (1999) 23–37.

[5] M. DeVos, Flows on bidirected graph, preprint.

[6] P. Erdős, Graph theory and probability, Canadian J. Math. 11 (1959) 34–38.

[7] S. Fisk, The nonexistence of colorings, J. Combin. Theory Ser. B 24 (1978) 247–248.

[8] S. Fisk, B. Mohar, Coloring graphs without short non-bounding cycles, J. Combin. Theory Ser. B 60 (1994) 268–276.

[9] P. J. Giblin, Graphs, surfaces and homology. An introduction to algebraic topology, Second edition, Chapman and Hall, London-New York, 1981.

[10] J. Gimbel, C. Thomassen, Coloring graphs with fixed genus and girth, Trans. Amer. Math. Soc. 349 (1997), 4555–4564.

[11] L. Goddyn, The circular chromatic of even faced projective plane graphs, Preprint.

[12] L. A. Goddyn, M. Tarsi, C.-Q. Zhang, On (k, d)-colorings and fractional nowhere-zero flows, J. Graph Theory 28 (1998) 155–161.

[13] L. Goddyn, D. Vertigan, X. Zhu, Minty type formulas, preprint.

[14] M. de Graaf, A. Schrijver, Grid minors of graphs on the torus, J. Combin. Theory Ser. B 61 (1994) 57–62.

[15] M. J. Greenberg, J. R. Harper, Algebraic Topology. A First Course, Benjamin/Cummings Publ. Comp., Menlo Park, California, 1981.

[16] B. Grünbaum, Conjecture 6, in “Recent Progress in Combinatorics”, Ed. W. T. Tutte, Academic Press, New York, 1969, p. 343.

[17] J. P. Hutchinson, Three-coloring graphs embedded on surfaces with all faces even-sided, J. Combin. Theory Ser. B 65 (1995) 139–155.

[18] J. Hutchinson, R. B. Richter, P. Seymour, Colouring Eulerian triangulations, J. Combin. Theory Ser. B 84 (2002) 225–239.

[19] F. Jaeger, Flows and generalized coloring theorems in graphs. J. Combin. Theory Ser. B 26 (1979) 205–216.

[20] F. Jaeger, Nowhere-zero flow problems, in, Selected Topics in Graph Theory, Volume 3, Academic Press, 1988, pp. 71–96.

[21] G. J. Minty, A theorem on n-coloring the points of a linear graph, Amer. Math. Monthly 69 (1962) 623-624.

[22] 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.

[23] B. Mohar, P. D. Seymour, Coloring locally bipartite graphs on surfaces, J. Combin. Theory Ser. B 84 (2002) 301–310.

[24] B. Mohar, C. Thomassen, Graphs on Surfaces, Johns Hopkins University Press, Baltimore, 2001.

[25] J. Mycielski, Sur le coloriage des graphs, Colloq. Math. 3 (1955) 161–162.

[26] A. Nakamoto, S. Negami, K. Ota, Chromatic numbers and cycle partitions of quadrangulations on nonorientable surfaces, preprint.

[27] N. Robertson, P. D. Seymour, Graph minors VII. Disjoint paths on a surface, J. Combin. Theory Ser. B 45 (1988) 212–254.

[28] G. Ringel, Map Color Theorem, Springer-Verlag, New York-Heidelberg, 1974.

[29] P. D. Seymour, Nowhere-zero 6-flows, J. Combin. Theory Ser. B 30 (1981) 130–135.

[30] C. Tardif, Fractional chromatic numbers of cones over graphs, J. Graph Theory 38 (2001) 87–94.

[31] C. Thomassen, Five-coloring maps on surfaces, J. Combin. Theory Ser. B 59 (1993) 89–105.

[32] C. Thomassen, The chromatic number of a graph of girth 5 on a fixed surface. J. Combin. Theory Ser. B 87 (2003) 38–71.

[33] C. Thomassen, Color-critical graphs on a fixed surface, J. Combin. Theory Ser. B 70 (1997) 67–100.

[34] W. T. Tutte, A contribution to the theory of chromatic polynomials, Canad. J. Math. 6 (1954) 80–91.

[35] W. T. Tutte, A class of Abelian groups, Canad. J. Math. 8 (1956) 13–28.

[36] D. A. Youngs, 4-chromatic projective graphs, J. Graph Theory 21 (1996) 219–227.

[37] X. Zhu, Circular chromatic number: a survey, Discrete Math. 229 (2001) 371–410.

Department of Mathematics, Princeton University, Princeton, NJ 08544 USA

   E-mail address: matdevos@math.princeton.edu

Department of Mathematics, Simon Fraser University, Burnaby, BC, Canada

   E-mail address: goddyn@math.sfu.ca

Department of Mathematics, University of Ljubljana, Ljubljana, Slovenia

   E-mail address: bojan.mohar@fmf.uni-lj.si

Department of Mathematics, Louisiana State University, Baton Rouge, Louisiana

   E-mail address: vertigan@math.lsu.edu

Department of Applied Mathematics, National Sun Yat-sen University, Kaohsiung, Taiwan

   E-mail address: zhu@math.nsysu.edu.tw