High Girth Graphs Avoiding a Minor are Nearly Bipartite

Anna Galluccio^{∗}

Istituto di Analisi dei Sistemi ed

Informatica - CNR Roma, Italy galluccio@iasi.rm.cnr.it

Luis A. Goddyn^{†}

Department of Mathematics and Statistics Simon Fraser University Burnaby, B.C., Canada goddyn@math.sfu.ca

Pavol Hell^{‡}

Department of Mathematics and Statistics and School of Computing Science Simon Fraser University Burnaby, B.C., Canada pavol@cs.sfu.ca

AMS classifications (2000): 05C15, (05C10, 05C83).

Proposed running head: High girth nearly bipartite graphs.

∗Supported by NATO-CNR Fellowship; this work was done mainly while the author was visiting the Dept. of Mathematics and Statistics at Simon Fraser University, Canada;

†Supported by a National Sciences and Engineering Research Council Research Grant ‡Supported by a National Sciences and Engineering Research Council Research Grant

Abstract

Let H be a fixed graph. We show that any H-minor free graph of high enough girth has a circular-chromatic number arbitrarily close to two. Equivalently, such graphs have homomorphisms into a large odd circuit. In particular, graphs of high girth and of bounded genus or bounded tree width are “nearly bipartite” in this sense. For example, any planar graph of girth at least 16 admits a homomorphism onto a pentagon. We also obtain tight bounds in a few specific cases of small forbidden minors.

Keywords: homomorphisms, circular chromatic number, star chromatic number, girth, genus, series-parallel graphs.

Contact authors: Anna Galluccio Istituto di Analisi dei Sistemi ed Informatica - CNR viale Manzoni 30 00185 Roma, Italy galluccio@iasi.rm.cnr.it

or: Luis A. Goddyn Department of Mathematics and Statistics Simon Fraser University Burnaby, B.C., Canada goddyn@math.sfu.ca

1 Introduction

A homomorphism from a graph G into a graph H is a mapping f : V (G) → V (H) such that uv ∈ E(G) implies f(u)f(v) ∈ E(H). If G admits a homomorphism to H we write G → H. The girth of a graph G is the minimum length of a circuit in G. The odd girth of a graph G is the minimum length of an odd circuit in G. Both girth and odd girth can be viewed as measures of “sparsity” in a graph. A minor of G is any graph H obtained from G by contracting and deleting edges. A graph is H-minor free if it has no minor isomorphic to H. The circular chromatic number (sometimes called the “star chromatic number”) of a graph G, denoted by χ_{c}(G), is the infimum of the set of real numbers r for which there exists a map from V (G) to the set of unit-length open arcs of a circle having circumference r, such that adjacent vertices map to disjoint arcs. It turns out that if we replace ‘circle’ by ‘interval’ (and ‘circumference’ by ‘length’) the resulting parameter is precisely the usual chromatic number χ(G); that the infimum in this definition can be achieved (and hence is the minimum); and that χ(G) = ⌈χ_{c}(G)⌉; cf. the excellent survey article of X. Zhu [25].

We investigate the connections between the properties of embeddability and sparsity of a graph and its (circular) chromatic number. The first result of this flavour is probably due to Grötzsch [9], who proved that every planar graph with no triangle can be 3-coloured. Some years later, Kronk and White [13] showed that every toroidal graph of girth at least 6 can be 3-coloured, while Cook [5] proved that if G is a graph of genus γ and the girth of G is at least max{9, 6 + 2 log_{2}(γ)} then G is 3-colourable. Thomassen [21] improved this bound for toroidal graphs by showing that every toroidal graph of girth at least 5 can be 3-coloured. Let C_{ℓ} denote a circuit of length ℓ. A 3-colouring of a graph G is precisely a homomorphism to C_{3}. Thus we are lead to ask analogous questions about other odd circuits.

Question 1.1 Does there exist an integer g_{0} such that any planar graph with girth at least g_{0} admits a homomorphism to C_{5}?

An example by Albertson and Moore [1] (see Figure 1) shows that if such an integer g_{0} exists, then g_{0} ≥ 8. Jaeger’s “circular flow conjecture” [11] would imply that g_{0} ≤ 8 suffices for the above question. It will follow from our results that answer is affirmative and that g_{0} ≤ 16.

We shall generalize these results to graphs of higher genus and to graphs avoiding a fixed minor. To this purpose we define two parameters.

Definition 1.2 Let ℓ be any odd integer greater than one, γ any positive integer and H any

Figure 1: Albertson-Moore graph

fixed graph. We define g_{γ}(ℓ) as the infimum of integers g such that every graph G of genus at most γ and girth at least g is homomorphic to C_{ℓ}.

We further define g_{H} (ℓ) as the infimum of integers g such that every H-minor free graph G of girth at least g is homomorphic to C_{ℓ}.

Thus g_{0}(5) is the smallest value of g_{0} which suffices for Question 1.1.

We shall show that both the above parameters are finite and we give some explicit bounds on them in Sections 2, 3 and 4.

Let C_{ℓ} denote the class of all graphs G with G → C_{ℓ}. It is easy to see that

C_{3} C_{5} C_{7} ⋯

and that ⋂ C_{ℓ} is the class of bipartite graphs. Thus we view a graph in C_{ℓ} (ℓ ≫ 1, ℓ odd) as being “nearly bipartite” with ℓ being a measure of the “bipartiteness” of the graph. This notion can be equivalently formulated in terms of circular chromatic numbers.

Proposition 1.3 For any graph G and integer k, the following are equivalent:

1. χ_{c}(G) ≤ 2 + \frac{1}{k}

2. G → C_{2k+1}

Thus a graph is “nearly bipartite” if its circular chromatic number is close to two.

The subject of this paper is the study of classes of graphs for which high girth implies low circular chromatic number. Formally, we say that a class G of graphs is girth-bipartite if for any ϵ > 0 there exists an integer g(ϵ) such that every graph in G having girth at least g(ϵ) satisfies χ_{c}(G) ≤ 2 + ϵ. (We use term “girth-bipartite” to distinguish from other variants of the intuitive notion of “near bipartiteness” in the literature.) The main result of this paper is the following.

Theorem 1.4 For every graph H, the class of H-minor free graphs is girth-bipartite.

In particular, no minor-closed class of graphs whose members have unbounded girth can have its circular chromatic numbers bounded away from two. The condition that the graphs be H-minor free cannot be omitted, since there exist graphs having arbitrary girth and chromatic number.

A special case of Theorem 1.4 concerns classes of graphs having bounded genus. In Theorem 3.2 we give a specific upper bound on the circular chromatic number of graphs having a given girth and genus. The bound g_{0} ≤ 16 mentioned above for the planar graphs is a special case of Theorem 3.2.

The special case of Theorem 1.4 where H is planar was proved in 1996 by Nešetřil and Zhu [15, Corollary 2]. In fact they prove something stronger, replacing the girth condition with a weaker hypothesis. The odd girth of a graph is the length of its shortest odd circuit (the odd girth of a bipartite graph is infinite). Consider the following three properties of a graph G and integer k:

P1: G has girth at least k

P2: G has a homomorphism into some graph having girth at least k

P3: G has odd girth at least k.

Proposition 1.5 For any graph G and any integer k, P1 implies P2, and P2 implies P3.

By considering C_{4}, and the Grötzsch graph with k = 5, we see that P_{2} does not imply P_{1} and P_{3} does not imply P_{2}. Hence, analogously to the definition of “girth-bipartite”, we may define two stronger properties of a class G of graphs by replacing P1 by P2 (or P3 ) in the definition: G is hom-girth-bipartite (odd-girth-bipartite) if for some function g(ϵ) and all ϵ > 0, every graph in G satisfying P2 (P3 ) with k ≥ g(ϵ) satisfies χ_{c}(G) < 2 + ϵ. When H is planar, the H-minor free graphs have bounded tree width [16]. Thus we may state the Nešetřil–Zhu result as follows.

Theorem 1.6 Any class of graphs with bounded tree width is hom-girth-bipartite.

This gives rise to a possible common generalization of the two results.

Question 1.7 Is it true that for every graph H, the class of H-minor free graphs is hom-girth-bipartite?

We do not know the answer here even in the special case of graphs of bounded genus. The above question has a negative answer if we replace “hom-girth-bipartite” with “odd-girth-bipartite” for there are projective planar graphs [23] with arbitrary odd girth and chromatic number 4. However, it is known [24] that the class of planar graphs is odd-girth-bipartite. Also it is proved in [6] that for any orientable surface Σ there exists an integer r = r(Σ) such that the set of locally bipartite graphs embeddable on Σ with representativity at least r is odd-girth-bipartite.

The concepts “girth-bipartite” and “odd-girth-bipartite” are easily dualized in the matroid sense. A circulation in a directed graph is a real-valued function on its arcs satisfying the usual flow-conservation law. The circular flow number of a graph G = (V, E) is defined by

ϕ_{c}(G) = inf{r ∈ : G has an orientation G⃗ and a circulation f : E(G⃗) → [1, r − 1]}.

For finite 2-edge connected graphs the infimum is attained at a rational number since for such graphs [8]

ϕ_{c}(G) = min_{G⃗} max_{X⊆V} \frac{|δ(X)|}{|δ^{+}(X)|}

where the minimum is over all strong orientations of G. (Here δ^{+}(X) denotes the set of arcs in G⃗ with tails in X and heads in V − X, and δ(X) = δ^{+}(X) + δ^{+}(V − X).) Analogously to chromatic numbers, the usual flow number of a graph G [8] is given by ⌈ϕ_{c}(G)⌉. The cogirth (resp. odd-cogirth) of G is the minimum size of a (odd-size) nonempty edge cut of G. By planar duality, our answer to Question 1.1 is equivalent to the statement: any planar graph of cogirth at least 16 has circular flow number at most \frac{5}{2}.

A class of graphs G is cogirth-even (odd-cogirth-even) if for some function λ(ϵ) and all ϵ > 0, every graph in G with cogirth (odd-cogirth) at least λ(ϵ) satisfies ϕ_{c}(G) < 2 + ϵ. In general, flow numbers behave better than chromatic numbers. For example, all bridgeless graphs G satisfy 2 ≤ ϕ_{c}(G) ≤ 6, and all graphs of cogirth at least four have 2 ≤ ϕ_{c}(G) ≤ 4 [18, p.297]. Jaeger has proposed the following “circular flow conjecture” [11]:

Conjecture 1.8 The class of all graphs is cogirth-even.

In fact, he proposes that λ(1/k) = 4k suffices for integers k ≥ 1. By planar duality, this would imply that g_{0}(5) = λ(\frac{1}{2}) = 8 suffices in Question 1.1. However, it is possible that a stronger statement holds.

Question 1.9 Is the class of all graphs odd-cogirth-even?

Zhang [24] has shown that any class of graphs of bounded genus is odd-cogirth-even, but little else is known about this problem.

2 Proof of Theorem 1.4

Our results rely on the simple observation that deleting a long induced path in a graph does not affect its circular chromatic number. That is, deleting the internal points of such a path from a graph will not change its circular chromatic number.

Lemma 2.1 Let P be an induced path of length p in a graph G, let U be the set of internal vertices of P, and let ℓ be any odd integer with ℓ ≤ p + 1. Then G → C_{ℓ} if and only if (G − U) → C_{ℓ}

Proof. The “only if” direction is trivial. Conversely, suppose that ϕ′ is a homomorphism from G − U into C_{ℓ}. Let x, y ∈ V (G) be the end-vertices of P. Since ℓ is odd and p ≥ ℓ − 1, it is straightforward to check that, regardless of the values of ϕ′(x) and ϕ′(y), ϕ′ can be extended to a homomorphism from G into C_{ℓ}. □

A graph G is p-path degenerate if there is a sequence G = G_{0}, G_{1}, …, G_{t} of 2-connected subgraphs where G_{t} is bipartite, and where each G_{i} (i > 0) is obtained by deleting from G_{i−1} the internal vertices of an induced path of length at least p. By repeatedly applying Lemma 2.1 and observing that bipartite graphs have circular chromatic number 2, we obtain the following.

Corollary 2.2 If G is p-path degenerate, then there is a homomorphism from G into any odd circuit having length at most p + 1, whence χ_{c}(G) ≤ 2 + \frac{1}{⌊ \frac{p}{2} ⌋}.

Next, we show that every graph avoiding any fixed minor and having “high enough” girth is p-path degenerate. For this, we rely on an observation of Thomassen [20, p. 115].

Lemma 2.3 For any graph H there exists an integer k such that every H-minor free graph with minimum degree at least 3 has girth at most k.

Definition 2.4 Let k_{H} denote the least integer k satisfying Lemma 2.3.

Lemma 2.5 For any graph H and integer p, every H-minor free graph with girth at least (p − 1)k_{H} + 1 is p-path degenerate.

Proof. Let G be an H-minor free graph having girth at least (p−1)k_{H} +1. We claim that G is p-path degenerate. We may assume that G is 2-connected since G is p-path degenerate if each of its 2-connected blocks is. If G is a circuit, then this circuit has length at least (p−1)k_{H} +1 ≥ p+1 and thus G is p-path degenerate. Henceforth we assume that G is a 2-connected graph different from an edge or a circuit, and so there is a unique graph G′ with minimum degree at least 3 which is homeomorphic to G. In other words, G can be obtained from G′ by replacing each edge e ∈ E(G′) with a path P (e) having length at least one. As G′ has no H-minor, G has a circuit C′ of length at most k_{H}. The circuit C in G corresponding to C′ has length at least (p−1)k_{H} +1 so C contains an induced path P (e_{0}) having length at least p, for some e_{0} ∈ E(C′). Deleting the internal vertices of P (e_{0}) from G leaves a smaller H-minor free graph with girth at least (p − 1)k_{H} + 1. By induction we have that G is p-path degenerate. □

Proof of Theorem 1.4. The result follows immediately from Corollary 2.2 and Lemma 2.5. □

Indeed we have that every H-minor free graph G with girth at least (p − 1)k_{H} + 1 has a homomorphism onto any odd circuit of length ℓ ≤ p + 1, and thus χ_{c}(G) ≤ 2 + \frac{1}{⌊ \frac{p}{2} ⌋}. An upper bound for χ_{c}(G), is obtained by choosing p as large as possible in Lemma 2.5. Thus:

Corollary 2.6 For any H-minor free graph G of girth g

G → C_{ℓ} for any odd integer ℓ ≤ \frac{g−1}{k_{H}} + 2 .

Determining k_{H} is difficult in general, however, in the following, we provide an upper bound on it when H = K_{t}.

Mader [14] (see [22, p. 333] for an English language version) proved that:

Lemma 2.7 For each positive integer t there exists an integer d(t) such that every simple graph with minimum degree at least d(t) contains K_{t} as a minor.

Later, Kostochka [12] showed that any simple graph with average degree at least 2t has a K_{η}- minor where η ≥ .064t/\sqrt{log_{2} t}. This implies d(t) = 66t\sqrt{log_{2} t} suffices in Lemma 2.7 for t ≥ 3. Finally, Thomason [19] proved that the constant 66 may be lowered to 5.36 if t is large.

Lemma 2.8 If H = K_{t}, t ≥ 3, then k_{H} < 4c_{1}t\sqrt{log_{2} t}, where c_{1} = 66.

Proof. Consider a graph G with minimum degree at least 3 and girth at least 4c_{1}t\sqrt{log_{2} t}. By Thomassen’s proof of Lemma 2.3, G contains as a minor a simple subgraph F whose minimum degree δ(F) is at least c_{1}t\sqrt{log_{2} t}. Hence by the remark following Lemma 2.7, there exists a K_{t}-minor in G. □

For any simple graph H of order t, the above lemma yields an upper bound for k_{H} depending only on t and on the girth of G. Thus, by replacing this bound into the formula in Corollary 2.6, we get the following bound for the smallest girth which ensures that any H-minor free graph admits a homomorphism to C_{ℓ}:

Corollary 2.9 Let H be a fixed graph of order t and let ℓ > 1 be an odd integer. Then,

g_{H} (ℓ) ≤ 264(ℓ − 2)t\sqrt{log_{2} t} + 1.

Finding better upper bounds on g_{H} (ℓ) for specific forbidden minors H is the topic of Section 4. It is worth noticing that a result analougous to Lemma 2.7 holds true [3] when K_{t} is contained

as a topological minor, i.e., a subgraph isomorphic to a subdivision of K_{t}. All results in this paper may be stated in this setting, including our main theorem:

Theorem 2.10 For every graph H, the class of graphs which do not contain H as a topological minor is girth-bipartite.

3 Graphs of bounded genus

The (orientable) genus of a graph G is the mimimum number of “handles” which must be added to a sphere in order to obtain a surface into which G has an embedding. Thus planar graphs have genus zero. We refer the reader to [22] for further details on graph embeddings. All graphs of genus at most γ are H-minor free for any graph H having genus greater than γ. Thus any class of graphs of bounded genus is girth-bipartite. In this section we specialize the bounds of the previous section to graphs having bounded genus.

Definition 3.1 Let k_{γ} denote the least integer such that all graphs with genus at most γ with minimum degree at least 3 have girth at most k_{γ}.

For example, it is well known that k_{0} = 5 and k_{1} = 7. By exactly the same argument as the proof of Lemma 2.5, any graph of genus at most γ and girth at least (p − 1)k_{γ} + 1 is p-path degenerate. Thus any graph of genus at most γ satisfies the inequalities of Theorem 2.6 with k_{H} replaced by k_{γ}. The goal of this section is to derive the following upper bound on k_{γ}.

Theorem 3.2 For any γ ≥ 0, we have

k_{γ} ≤ 4 + ⌊2 log_{2}(γ + 3/2)⌋.  (1)

Corollary 3.3 For any graph G of girth g and genus at most γ,

1. G → C_{ℓ} for any odd integer ℓ ≤ 2 + \frac{g−1}{4+⌊2 log_{2}(γ+3/2)⌋};

2. g_{γ}(ℓ) ≤ (ℓ − 2)(4 + ⌊2 log_{2}(γ + 3/2)⌋) + 1.

In particular, any planar graph with girth at least 16 has a homomorphism into a pentagon, which answers Question 1.1.

We note here that the dependence on genus arises only through Euler’s characteristic formula. Thus a similar formula holds regarding the unoriented genus of G: if G embeds on N_{γ′}, the sphere with γ′ crosscaps, then conclusion of Corollary 3.3 holds upon substituting 2γ′ for γ.

A (g, k)-cage is a graph having minimum degree at least k and girth at least g with the fewest possible number of vertices. There is a well-known lower bound (see [2]) for the number n(g, k) of vertices in a (g, k)-cage. In particular,

n(g, 3) ≥ \{ \begin{matrix}2 · 2^{g/2} − 2 & if g is even \\ 3 · 2^{(g−1)/2} & if g is odd \end{matrix} \} ≥ 2 · 2^{g/2} − 2.  (2)

Lemma 3.4 If G is a graph having minimum degree at least 3, girth g ≥ 6 and genus γ, then

γ ≥ 1 + ⌈\frac{g − 6}{4g}n(g, 3)⌉.  (3)

Proof. Let G be a graph with n vertices, e edges, girth g, genus γ and minimum degree at least 3. If g = 6, then G is not planar and we are done, so we may assume g ≥ 7. Suppose G has r regions when embedded onto S_{γ}. We follow Cook’s argument in [4] which uses Euler’s formula and the inequalities gr ≤ 2e ≤ 3n to derive

n ≤ \frac{4g(γ − 1)}{g − 6}.

On the other hand we have by definition of a cage, n ≥ n(g, 3). The two inequalities imply (3). □

Proof of Theorem 3.2. Let G be a graph having minimum degree at least 3 and genus γ. Let h(γ) be the function expressed in the right hand side of (1). Our goal is to show that the girth g of G is smaller than or equal to h(γ). We have h(0) = 5, h(1) = 7 which are well known upper bounds for planar and toroidal graphs. We may assume that G has genus γ ≥ 2 and apply Lemma 3.4. From (2) and (3) we have

γ ≥ 1 + \frac{1}{2}(1 − \frac{6}{g})(2^{g/2} − 1).  (4)

If 7 ≤ g ≤ 11, then we verify the corollary numerically by checking that g ≤ h(γ) when the right hand side of (4) is substituted for γ. If g ≥ 12, then we have from (4)

4(γ + \frac{3}{2}) ≥ 4 + (2^{g/2} + 2^{g/2} − 2) − \frac{12}{g}(2^{g/2} − 1) + 6 > 2^{g/2}

and the result follows by taking logarithms. □

The upper bound (1) compares quite well to the best upper bound to k_{γ} that can be possibly be derived from (3) and the first inequality in (2). In fact, the two bounds are equal for γ ≤ 7, they differ by at most one when γ ≤ 11, and they never differ by more than two. The exact value of k_{γ} appears to be very difficult to determine.

The best upper bound to g_{γ}(ℓ) in terms of the girth and genus of G appears to be extremely hard to determine, even for planar graphs.

4 Bounds for specific forbidden minors H

The bound defined in the previous sections can be improved in case specific minors are forbidden. This problem has been considered by Hell and Zhu [10] for the class of series-parallel graphs. They proved that any series-parallel graph G of girth at least 2⌊(3k − 1)/2⌋ is homomorphic to C_{2k−1}. Since each 2-connected component of a K_{4}-minor free graph is a series-parallel graph, the same bound holds for the class of K_{4}-minor free graphs, i.e., g_{K_{4}} (ℓ) ≤ \frac{3ℓ+1}{2}.

It was pointed out by Gerards [7] that the subdivisions of K_{4} play an important role in homomorphisms to odd circuits. An odd-K_{4} and an odd-K_{3}^{2} are shown in Fig. 4, where the word “odd” inside a face means that the length of that face is odd.

In fact, he proved [7] that:

Theorem 4.1 Let G be a nonbipartite graph. If G contains neither an odd-K_{4} nor an odd-K_{3}^{2} then G admits a homomorphism onto its shortest odd circuit.

Clearly, an odd-K_{3}^{2} contains as a K_{3}^{2} as a minor (where K_{3}^{2} is a K_{3} with all edges doubled). On the other hand, K_{3}^{2}-minor free graphs may contain an odd-K_{4}-minor, and hence, constitute a non trivial class where to consider homomorphisms to odd circuit.

Figure 2: a) Odd-K_{4}, b) Odd-K_{3}^{2}

By dualizing the characterization of Seymour [17] of K_{2,3}-minor free graphs, we may state the following:

Theorem 4.2 Let G be a 2-connected K_{3}^{2}-minor free graph. Then either G does not contain a K_{4}-minor or G is a subdivision of a K_{4}.

By the above theorem and Gerards’ theorem, we expect that odd-K_{4}’s are obstructions to finding homomorphisms onto odd circuits. The next lemma confirms this. We denote by x_{1}, x_{2}, x_{3}, x_{4} the vertices of degree three in the K_{4} subdivision and we call arms the paths [x_{i}, x_{j}] joining different pairs x_{i}, x_{j}, 1 ≤ i, j ≤ 4.

Lemma 4.3 Let G be an odd-K_{4} of girth 3k. If all arms have length k then G is not homomorphic to C_{2k+1}.

Proof. Let V (C_{2k+1}) = {0, 1, …, 2k}. Suppose there exists a homomorphism ϕ from G onto C_{2k+1}. We may assume without loss of generality that x_{1} receives colour 0, namely ϕ(x_{1}) = 0. Now, we distinguish two cases: either both the vertices x_{2} and x_{3} receive an even colour or they both receive an odd colour. In the first case, since the lengths of the paths between x_{1} and x_{2}, and, x_{1} and x_{3} respectively, are odd and equal to k, it follows that the ϕ(x_{2}) and ϕ(x_{3}) must be at least k + 1. This implies that the circuit [x_{1}, x_{2}] ∪ [x_{2}, x_{3}] ∪ [x_{3}, x_{1}] cannot be mapped onto C_{2k+1}.

Similarly, if the labels of x_{2} and x_{3} are both odd, they must have value smaller than or equal to k which again implies that the circuit [x_{1}, x_{2}]∪[x_{2}, x_{3}]∪[x_{3}, x_{1}] cannot be mapped onto C_{2k+1}. □

Now we show that any odd-K_{4}, regardless from the length of its arms, of girth at least 3k can be mapped onto C_{2k−1}. To prove this, we introduce the operation of folding, i.e., identification of two nonadjacent vertices having a common neighbour.

Lemma 4.4 Let G be an odd-K_{4} of girth ≥ 3k. Then G is homomorphic to C_{2k−1}.

Proof. It is enough to prove the thesis when G has girth 3k. First of all observe that at least one of the arms of K_{4} has length smaller than or equal to k, since otherwise the girth of G would be greater than 3k.

We may assume without loss of generality that the arm [x_{1}, x_{2}] has length l ≤ k. If l is even then we fold the arm [x_{1}, x_{2}] l/2 times. If l is odd then we fold the arm (l − 1)/2 times, thus obtaining an arm of length 1. Then, we fold this remaining edge with the first edge of the arm [x_{1}, x_{4}].

In each case, the resulting graph has girth at least 2k − 1 and contains neither an odd-K_{4} nor an odd-K_{3}^{2}. Hence, by Theorem 4.1, it is homomorphic to its shortest odd circuit, which has length at least 2k − 1, and hence also to C_{2k−1}. □

It follows easily from Theorems 4.2, 4.1 and Lemma 4.4 that:

Theorem 4.5 Let ℓ > 1 be an odd integer. Then,

g_{K^{2}_{3}} (ℓ) ≤ \frac{3(ℓ + 1)}{2}.

Note that if F is a minor of H then the bound for F -minor free graphs is at most the bound obtained for H-minor free graphs. It follows that if H is a minor of K_{4} or a minor of K_{3}^{2} and G is an H-minor free graph, then G is homomorphic to C_{2k+1} provided that the girth of G is at least 3(k + 1).

Observe also that if H is a minor of both K_{4} and K_{3}^{2} and G is H-minor free then G is homomorphic to C_{2k+1} provided that the girth of G is at least 2k + 1, by Gerards’ theorem.

References

[1] M. Albertson and E. Moore. Personal Communication.

[2] B. Bollobás. Extremal graph theory. In Handbook of combinatorics, volume 2. Elsevier, Amsterdam, 1995.

[3] B. Bollobás and A. Thomason. Proof of a conjecture of Mader, Erdös and Hajnal on topological complete subgraphs. Europ. J. Combinatorics, 19:883–887, 1998.

[4] R. J. Cook. Analogues of Heawood’s theorem. In Combinatorics (Proc. British Combinatorial Conf.), London Math. Soc. Lecture Note Ser., No. 13, pages 27–33. Cambridge Univ. Press, London, 1974.

[5] R. J. Cook. Chromatic number and girth. Period. Math. Hungar., 6:103–107, 1975.

[6] M. DeVos, L. Goddyn, and B. Mohar. Circular chromatic numbers of highly representative graphs on a surface. In preparation.

[7] A. M. H. Gerards. Homomorphisms of graphs into odd cycles. Jour. Graph Th., 12:73–83, 1988.

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

[9] H. Grötzsch. Ein dreifarbensatz für dreikreisfreie netze auf der kugel. Math. Nat. Reihe, 8:109–120, 1959.

[10] P. Hell and X. Zhu. The circular chromatic number of series-parallel graphs. 1998.

[11] F. Jaeger. Nowhere-zero flow problems. In Selected Topics in Graph Theory, volume 3, pages 71–96. Academic Press, 1988.

[12] A. V. Kostochka. Lower bound of the Hadwiger number of graphs by their average degree. Combinatorica, 4:307–316, 1984.

[13] H. V. Kronk and A. T. White. A 4-color theorem for toroidal graphs. Proc. Amer. Math. Soc., 34:83–86, 1972.

[14] W. Mader. Homomorphieeigenschaften und mittlere kantendichte von graphen. Math. Ann., 174:265–268, 1967.

[15] J. Nešetřil and X. Zhu. On bounded treewidth duality of graphs. J. Graph Theory, 23:151– 162, 1996.

[16] N. Robertson and P.D. Seymour. Graph minors. II. Algorithmic aspects of treewidth. J. Algorithms, 7:309–322, 1986.

[17] P. D. Seymour. Matroid theory. In R. Graham, M. Grötschel, and L. Lovász, editors, Handbook of Combinatorics, volume 1, chapter 10. Elsevier, Amsterdam, 1995.

[18] P. D. Seymour. Nowhere-zero flows. In R. Graham, M. Grötschel, and L. Lovász, editors, Handbook of Combinatorics, volume 1. Elsevier, Amsterdam, 1995. Appendix to chapter 4.

[19] A. Thomason. An extremal function for contracting of graphs. Math. Proc. Cambridge Philos. Soc., 95:261–265, 1984.

[20] C. Thomassen. Paths, circuits and subdivisions. In Selected Topics in Graph Theory, volume 3, pages 97–131. Academic Press, 1988.

[21] C. Thomassen. Grötzsch’s theorem and its counterparts for the torus and the projective plane. J. Combin. Theory Ser. B, 62:268–279, 1994.

[22] C. Thomassen. Embeddings and minors. In R. Graham, M. Grötschel, and L. Lovász, editors, Handbook of Combinatorics, volume 1, chapter 5. Elsevier, Amsterdam, 1995.

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

[24] C. Q. Zhang. Circular flows of nearly eulerian graphs and vertex-splitting. 1999. Preprint.

[25] X. Zhu. Circular chromatic numbers: A survey. 1997.