Meirun Chen
email: mrchen@xmut.edu.cn.

Reza Naserasr

Homomorphisms of partial t-trees and edge-coloring of partial 3-trees

Keywords: Planar graphs, treewidth, homomorphism, minor, edge-coloring

A reformulation of the four-color theorem is to say that K 4 is the smallest graph to which every planar (loop-free) graph admits a homomorphism. Extending this theorem, the second author has proved (using the four-color theorem) that the Clebsch graph (a well known triangle-free graph on 16 vertices) is a smallest graph to which every triangle-free planar graph admits a homomorphism. As a further generalization he has proposed that the projective cube of dimension 2k, P C(2k), (that is the Cayley graph (Z 2k 2 , {e 1 , e 2 , . . . , e 2k , J}, where e i 's are the standard basis and

) is a smallest graph of odd-girth 2k +1 to which every planar graph of odd-girth at least 2k +1 admits a homomorphism. This conjecture is related to a conjecture of P. Seymour who claims that the fractional edge-chromatic number of a planar multigraph determines its edge-chromatic number (more precisely, Seymour conjectured that χ (G) = χ f (G) for any planar multigraph G). Note that the restriction of Seymour's conjecture on cubic (planar) graphs is Tait's reformulation of the four-color theorem.

Both these conjectures are believed to be true for the larger class of K 5 -minor-free graphs (which includes the class of planar graphs). Motivated by these conjectures and in extension of a recent work of L. Beaudou, F. Foucaud and the second author, which studies homomorphism bounds for the class of K 4 -minor-free graphs, in this work we first give a necessary and sufficient condition for a graph B of odd-girth 2k + 1 to admit a homomorphism from any partial t-tree of odd-girth at least 2k + 1. Applying our results on the class of partial 3-trees, which is a rich subclass of K 5 -minor-free graphs, we prove that P C(2k) is in fact a smallest graph of odd-girth 2k + 1 to which every partial 3-tree of odd-girth at least 2k + 1 admits a homomorphism. We then apply this result to show that every planar (2k + 1)-regular multigraph G whose dual is a partial 3-tree, and whose fractional edge-chromatic number is 2k + 1, is (2k + 1)-edge-colorable. Both these results are the best known supports for the general cases of the above mentioned conjectures in extension of the four-color theorem.

Introduction

Given graphs G and H, a homomorphism of G to H is a mapping of the vertices of G to the vertices of H which preserves adjacency, that is to say, a mapping h : V (G) → V (H) such that if x and y are adjacent in G then h(x) and h(y) are adjacent in H. When there exists a homomorphism of G to H we write G → H and we may say G maps to H. It is easily verified that mapping of G to K k corresponds to a k-coloring of G, thus homomorphism generalizes the theory of coloring of graphs. Given a class C of graphs we say H bounds C if every member of C maps to H. Thus, in this terminology, the four-color theorem is to say: K 4 bounds the class of planar graphs.

Given a graph G, the odd-girth of G is the length of a shortest odd-cycle of G. It can be easily verified that an odd-cycle of length 2l + 1 maps to an odd-cycle of length 2k + 1 if and only if l ≥ k. Thus we have the following no-homomorphism lemma: Lemma 1.1. If G → H, then odd-girth(G) ≥ odd-girth(H).

In fact a slightly stronger statement can be stated: Lemma 1.2. Let G and B be graphs of odd-girth 2k + 1 and suppose that there is a homomorphism φ of G to B. Let u and v be two vertices of G which belong to a common (2k + 1)-cycle of G. Then φ(u) and φ(v) are on a common (2k + 1)-cycle of B and d G (u, v) = d B (φ(u), φ(v)).

Observe that the odd-girth of a given graph G can be computed in time polynomial in the order of G. Given a vertex x of G compute, inductively, the set N i (x) consisting of vertices at distance i from x. The first i for which N i (x) induces an edge implies the existence of a closed-walk of length 2i + 1 starting at x. The smallest sa uch closed walk is a shortest odd-cycle of G. Thus this classic no-homomorphism lemma is among the rare no-homomorphism lemmas which is based on a parameter computable in polynomial time (in contrast to other well known no-homomorphism lemmas which are based on parameters such as the clique number, the chromatic number, the fractional or circular chromatic numbers, all of which are NP-hard to compute).

The simplest use of this lemma concerns loops, that are odd-cycles of length 1. It asserts that when H is a simple graph and G → H, then G must have no loops. Hence, in this work we consider only graphs with no loops. However multi-edges will be considered when dealing with application to edge-coloring. When multi-edges are allowed, we will use the term multigraph, thus making sure the term graph refers solely to a simple graph.

In view of this no-homomorphism lemma, the four-color theorem can be restated as follows:

Theorem 1.3 (4CT). The smallest graph with no loop which bounds the class of all planar graphs with no loop is K 4 .

The natural question then is to find a (or probably the unique) smallest graph of odd-girth 2k + 1 which bounds the class of all planar graphs of odd-girth at least 2k + 1. A conjecture of the second author which implies, in particular, the order of such a graph must be 2 2k is discussed in Section 6.

Motivated by this question and the recent work of [START_REF] Beaudou | Homomorphism bounds and edge-colourings of K 4 -minor-free graphs[END_REF] we consider the question of bounding the class of partial t-trees of odd-girth at least 2k + 1 by a graph of odd-girth 2k + 1. A necessary and sufficient condition for a graph B of odd-girth 2k + 1 to admit a homomorphism from all K 4 -minor-free graphs of odd-girth at least 2k + 1 is provided in [START_REF] Beaudou | Homomorphism bounds and edge-colourings of K 4 -minor-free graphs[END_REF]. Extending this work, we give a necessary and sufficient condition to test if a given graph B of odd-girth 2k + 1 bounds the class of partial t-trees of odd-girth at least 2k + 1. We will then apply our work to the class of partial 3-trees to obtain results which are the strongest known support for the general cases of some conjectures in generalization of the four-color theorem.

The paper is organized as follows. In the next section we present our adaptation of various terminologies for the class of partial t-trees. In Section 2, extending the notion of odd-girth to weighted graphs, we build up the required terminologies and provide some classifications. Then in Section 4 we prove a necessary and sufficient condition for a graph B of odd-girth 2k+1 to bound all partial t-trees of odd-girth at least 2k + 1. In Section 5 we discuss the algorithmic consequences of this necessary sufficient condition. In Section 6 we discuss a conjecture in generalization of the four-color theorem, then we provide support for this conjecture by finding an optimal bound of odd-girth 2k + 1 for partial 3-trees of odd-girth at least 2k + 1. In Section 7 we consider an edge-coloring conjecture of P. Seymour on the edge-chromatic number of planar graphs which also extends the four-color theorem. We provide support for this conjecture by proving it for a subclass of multigraphs which are planar and whose duals are partial 3-trees.

Partial t-trees

The class of t-trees is a class of graphs built according to the following rules:

• K t+1 is a t-tree.

• Given a t-tree T and a t-clique C of T , the graph T built from T by adding a vertex which is adjacent to all the vertices of C is also a t-tree.

After an arbitrary ordering of the vertices of the first K t+1 , this construction induces an ordering v 1 , v 2 , . . . , v n of the vertices which has the following properties: i. the subgraph induced by v 1 , v 2 , . . . , v t is a clique, ii. in the subgraph H i induced by vertices v 1 , v 2 , . . . , v i , i > t, the vertex v i is of degree t and its neighbors induce a complete graph of order t. Such an ordering of the vertices of a t-tree T is called a t-tree ordering of T . Given a t-tree T and a t-tree ordering v 1 , v 2 , . . . , v n , n > t, let X i , t + 1 ≤ i ≤ n, be the (t + 1)-clique induced by v i and all its neighbors in {v 1 , v 2 , . . . , v i-1 }. The sequence X t+1 , X t+2 , . . . , X n , which is uniquely determined by the given t-tree ordering, is called a clique-sequence of T .

Observe that isomorphic copies of a t-tree might be associated with different t-tree orderings and that the class of 1-trees is exactly the class of trees, granting the name t-tree.

A partial t-tree is any subgraph of a t-tree. A partial t-tree G might be a subgraph of two or more non-isomorphic t-trees on a same set V (G) of vertices. Given a partial t-tree G, any t-tree ordering of a t-tree T , which is built on V (G) and contains G as a subgraph, is also a t-tree ordering of G. We will denote the class of all partial t-trees by PT t and the subclass of partial t-trees of odd-girth at least 2k + 1 by PT t,2k+1 .

The class PT t is known under various equivalent definitions. It is most notably known as the class of graphs of treewidth at most t. It is easily verified that PT t is a minor-closed class of graphs. For t = 1 we have the class of all forests which is identified as the class of graphs with no K 3 -minor. The class PT 2 is the class of K 4 -minor-free graphs, for a proof see for example [START_REF] Diestel | Graph Theory[END_REF]. The next class, PT 3 , is the class of all graphs having none of the four graphs of Figure 1 as a minor, this is proved in [1]. For t ≥ 4 the full list of forbidden minors is not known, though this list is finite thanks to the Graph-Minor Theorem of Rebertson-Seymour. One thing sure though: graphs in PT t are K t+2 -minor-free and that K t+1 is a member of this class. In particular PT 3 forms a special subclass of K 5 -minor-free graphs.

Weighted graphs and (2k + 1)-wideness

While previous definitions and notation are standard, here we introduce some notions we have developed to address our work. Throughout this section and also in the rest of the work, when it is clear from the context, k is a given positive integer such 2k + 1 is a lower bound on the odd-girth of graphs and weighted graphs we are working with, notion of odd-girth for weighted graphs being defined below.

A weighted graph (G, w) is a graph together with an assignment w : E(G) → Z + which assigns a positive integer w(e) to each edge e of G.

A homomorphism of a weighted graph (G, w 1 ) to a weighted graph (H, w 2 ) is a homomorphism of G to H which preserves the weights, that is to say

f : V (G) → V (H) is a homomorphism of (G, w 1 ) to (H, w 2 ) if w 2 (f (x)f (y)) = w 1 (xy).
Definition 3.1. Given a weighted graph (G, w) satisfying w(e) ≤ 2k, we define (G, w) 2k+1 to be a graph built from G as follows: for each edge uv of G delete the edge uv and add two u -v paths, one of length w(e) and the other of length 2k + 1 -w(e), (all internal vertices of these paths being new and distinct).

We then say (G, w) is (2k + 1)-wide if the graph (G, w) 2k+1 is of odd-girth 2k + 1.

Thus whenever we claim (G, w) is (2k + 1)-wide we implicitly imply that w satisfies 1 ≤ w(e) ≤ 2k for each edge e of G.

Given a weighted graphs (G, w) and (G, w ) with w(e), w (e) ≤ 2k for each edge of G, if for each edge e we have w (e) = w(e) or w (e) = 2k + 1 -w(e), then (G, w ) 2k+1 is isomorphic to (G, w) 2k+1 . Thus we may freely assume the weight of each edge is bounded from above by k. However, when dealing with the parity of a cycle in (G, w) 2k+1 going through three or more original vertices of G, we may need to consider some values of w which are greater than k.

From Lemma 1.2 we can drive the following lemmas: Proof. Since homomorphisms must preserve the weights, an edge of weight say p in (G, w 1 ) is mapped to an edge of weight p in (H, w 2 ). Thus we just need, for each edge, to extend mapping of the end points of a path of length p to a path of length p and of a path of length 2k +1-p to a path of length 2k +1-p.

The converse of this lemma is true in the following sense:

Lemma 3.4. Given two weighted graphs (G, w 1 ) and (H, w 2 ) which are both (2k + 1)-wide, if φ is a homomorphism of (G, w 1 ) 2k+1 to (H, w 2 ) 2k+1 which maps vertices of G to vertices of H, then the restriction of φ to V (G) is a homomorphism of (G, w 1 ) to (H, w 2 ).

Proof. This is based on the fact that (G, w 1 ) and (H, w 2 ) are both (2k + 1)-wide. This implies that both (G, w 1 ) 2k+1 and (H, w 2 ) 2k+1 are of odd-girth 2k + 1. The claim then follows from the fact that every mapping of C 2k+1 to another cycle of the same length must preserve distances.

Next we would like to introduce procedures using which one can decide whether a given weighted complete graph is (2k + 1)-wide. We first give two independent procedures for weighted triangles. We then show that for weighted complete graphs of larger order it is enough to apply one of the procedures to on all induced triangles. The first test, introduced in [START_REF] Beaudou | Homomorphism bounds and edge-colourings of K 4 -minor-free graphs[END_REF], applies when we assume all weights are bounded from above by k. Proposition 3.5. [START_REF] Beaudou | Homomorphism bounds and edge-colourings of K 4 -minor-free graphs[END_REF] Let (K 3 , w) be a weighted triangle with edge weights a, b, c satisfying 1 ≤ a ≤ b ≤ c ≤ k. Then is (2k + 1)-wide if and only if one of the following holds:

(i) a + b + c is odd and a + b + c ≥ 2k + 1, (ii) a + b + c is even and a + b ≥ c.
The next procedure is when w is allowed to give also values between k and 2k. We prove this one here. Proof. Suppose (K 3 , w) is (2k + 1)-wide. By definition, the graph (K 3 , w) 2k+1 is of odd-girth 2k + 1.

Then each odd-cycle of (K 3 , w) 2k+1 has length at least 2k + 1. Let x, y, z be the three vertices of K 3 . There are eight cycles in (K 3 , w) 2k+1 containing all the three vertices x, y and z. Exactly four of these eight cycles are of odd length and they are of length a + b + c, (2k + 1 -a) + (2k + 1 -b) + c, (2k +1-a)+b+(2k +1-c) and a+(2k +1-b)+(2k +1-c). Since there is an odd-cycle of length a+b+c, and since we have assumed that all odd-cycles are of length at least 2k + 1, we get a + b + c ≥ 2k + 1, and thus f 2k+1 (a, b, c) ≥ 0. The odd-cycle corresponding to the length 2k + 1

-a + 2k + 1 -b + c implies that 2k + 1 -a + 2k + 1 -b + c ≥ 2k + 1, therefore f 2k+1 (a, b, c) ≤ c. Similarly, we have f 2k+1 (a, b, c) ≤ b and f 2k+1 (a, b, c) ≤ a. So 0 ≤ f 2k+1 (a, b, c) ≤ min{a, b, c}.
Conversely, assume 0 ≤ f 2k+1 (a, b, c) ≤ min{a, b, c}. We want to show that (K 3 , w) is (2k + 1)-wide.

By definition, we need to show that the graph (K 3 , w) 2k+1 is of odd-girth 2k + 1. The odd-cycles in (K 3 , w) 2k+1 which contain exactly two vertices of K 3 are of length 2k + 1. There are four odd-cycles which contain three vertices of K 3 . Since a + b + c is odd, these four odd-cycles are of length a

+ b + c, 2k + 1 -a + 2k + 1 -b + c, 2k + 1 -a + b + 2k + 1 -c and a + 2k + 1 -b + 2k + 1 -c.
By the assumption that f 2k+1 (a, b, c) ≥ 0, we get a+b+c ≥ 2k+1. Since f 2k+1 (a, b, c) ≤ c, we have 2k+1-a+2k+1-b+c ≥ 2k+1. Similarly, we get that the other two odd-cycles have length at least 2k + 1. This completes the proof.

Next we prove that, given a weighted complete graph (K t , w) in order to decide whether (K t , w) is (2k + 1)-wide, it is enough to apply either any of the two previous propositions on all the induced triangles.

Theorem 3.7. A complete weighted graph (K t , w) is (2k + 1)-wide if and only if each of its induced triangles is (2k + 1)-wide.

Proof. First we show that the condition is necessary. Assume that (K t , w) is (2k + 1)-wide. Then, by definition, 1 ≤ w(e) ≤ 2k for any edge e ∈ E(K t ) and the graph (K t , w) 2k+1 is of odd-girth 2k + 1. Let (K * 3 , w * ) be an induced triangle where w * is induced by w over the edges of K * 3 . Thus (K * 3 , w * ) 2k+1 is a subgraph of (K t , w) 2k+1 and, therefore, is also of odd-girth 2k + 1.

To prove that the condition is also sufficient, we assume that (K t , w) is not (2k + 1)-wide and we show that there exists a set of three vertices whose induced weighted triangle is not (2k + 1)-wide. Since (K t , w) is not (2k + 1)-wide, there exists an odd-cycle in (K t , w) 2k+1 of length less than 2k + 1. Assume C is such an odd-cycle with minimum number of vertices from K t . By construction, C must have at least three vertices of K t . If it has three such vertices, then we have found our triangle. Thus we assume that C has at least four vertices from K t . Let x, y, z, u be four of these vertices in clockwise direction of C. Denote the two paths in C connecting x and z by P and Q. We know that the lengths of P and Q have different parity. There are two threads in (K t , w) 2k+1 which connect x and z, denote them by R 1 and R 2 . The sum of the length of R 1 and R 2 is 2k + 1, so the lengths of R 1 and R 2 have also different parity. Without loss of generality, assume that P ∪ R 1 and Q ∪ R 2 are odd-cycles (if necessary, we relabel R 1 and R 2 ). Thus each of P ∪ R 1 and Q ∪ R 2 induces a cycle of (K t , w) 2k+1 which uses less vertices of K t than C. Furthermore, the total length of these two cycles is |C| + 2k + 1, hence one of them is of length smaller than 2k + 1. This contradicts the choice of C, thus proving our claim.

In the next theorem we show how to use the previous results to test whether a given weighted t-tree is (2k + 1)-wide. Theorem 3.8. Let G be a t-tree with a clique-sequence X t+1 , X t+2 , . . . , X t+l . Let w be a weighting of G such that each X i , together with weights induced by w, is (2k + 1)-wide. Then (G, w) is (2k + 1)-wide.

Proof. We prove our claim by induction on l. If l = 1, then (G, w) = (X t+1 , w) and thus (G, w) is (2k + 1)-wide. Suppose (G , w), which is obtained from the clique-sequence X t+1 , X t+2 , . . . , X t+l-1 , is (2k + 1)-wide and let (G, w) be the graph obtained by adding a vertex v joined to t vertices u 1 , u 2 , . . . , u t . Thus u 1 , u 2 , . . . , u t together with v induces the (t + 1)-clique X t+l . Furthermore, suppose vu i is of weight a i (i = 1, 2, . . . , t). Since (G , w) is (2k + 1)-wide, in order to prove that (G, w) is (2k + 1)-wide, we only need to consider cycles of (G, w) 2k+1 which contain v and connect it to two vertices, say u 1 , u 2 , among u 1 , u 2 , . . . , u t , by paths of length a i or 2k + 1 -a i , i = 1, 2. Let C be such a cycle, and assume, by contradiction, that C is an odd-cycle of length smaller than 2k + 1. Let p be the length of the u 1 vu 2 part of C and let p be the length of the complementary part. Thus p and p are of different parity. Suppose that the (2k + 1)-cycle connecting u 1 and u 2 in (G, w) 2k+1 is separated by u 1 and u 2 into two paths of length a and a , thus a + a = 2k + 1. By symmetry of a and a , assume p + a is odd, then p + a is also odd. Observe that each of p + a and p + a corresponds to the length of a cycle in (G, w) 2k+1 . Since the sum of the lengths of these two cycles, (which is |C| + 2k + 1), is less than 2(2k + 1), one of them is of length smaller than 2k + 1. But p + a being smaller than 2k + 1 will contradict the assumption of the theorem that each X i together with weights induced by w is (2k + 1)-wide, and p + a being smaller than 2k + 1 contradicts our inductive assumption that (G , w) is (2k + 1)-wide. These contradictions complete our proof.

Combining these results we have the following criteria for a t-tree to be (2k + 1)-wide. Corollary 3.9. A weighted t-tree (T, w), t ≥ 2, is (2k + 1)-wide if and only if all of its induced weighted triangles are (2k + 1)-wide.

Partial and k-partial distance graphs

In this work we will only consider wighted graph for which the weight function is a specific metric function defined below.

Let G be a connected graph on n vertices. The complete distance graph of G is the weighted graph (K n , d G ) where K n is the complete graph on V (G) and the weight d G (uv) of an edge uv is the distance in G between u and v. Thus edges of weight 1 induce G. Any spanning (weighted) subgraph of (K n , d G ) will then be referred to as a partial distance graph of G or a partial G-distance graph. Thus a partial G-distance graph (H, d G ) has V (G) as its vertex set and each edge uv of H is given the weight d G (u, v), noting that H may not necessarily contain all edges of G. If, furthermore, we have

d G (u, v) ≤ k for each edge uv of H, then we say that (H, d G ) is a k-partial distance graph of G or a k-partial G-distance graph.
A special family of k-partial G-distance graphs is built as follows:

Definition 3.10. Let G be a t-tree and w be an edge-weighting of G with weights from {1, 2, . . . , k} such that (G, w) is (2k + 1)-wide. Recall that we have associated with (G, w) a graph (G, w) 2k+1 whose vertices contain vertices of G and, furthermore, an edge of G is also an edge of (G, w) 2k+1 if and only if it is of weight 1. Let G * (w,2k+1) be the weighted graph obtained from (G, w) 2k+1 by adding all missing edges of G. Then edges of (G, w) 2k+1 are assigned weight 1 and each other edge e is assigned the weight w(e). As common edges are of weight 1 this works fine.

Observe that for t ≥ 2, given a partial t-tree and an edge e of it, adding an edge parallel to e and subdividing it the result is still a partial t-tree. Thus we may claim the following: Observation 3.11. Given a weighted t-tree (G, w) which is (2k + 1)-wide, the underlying graph of G * (w,2k+1) is a partial t-tree.

An example is given in Figure 2. The figure on the right is a weighted graph built from the weighted K 4 presented on the left. The weights of bold edges are the same as corresponding edges of (K 4 , w) in the left, and all other edges are of weight 1.

0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1
00000 00000 00000 00000 00000 00000 11111 11111 11111 11111 11111 11111 00000 00000 00000 00000 00000 00000 00000 00000 00000 00000 00000 00000 00000 00000 00000 As claimed in the following proposition, the condition that (G, w) is (2k + 1)-wide implies that the extension of (G, w) into G * (w,2k+1) transforms the general weight function w to a k-partial distance function (of (G, w) 2k+1 ). We leave the verification of this claim to the reader. Proposition 3.12. Given a t-tree G and an edge weighting w with weights from {1, 2, . . . , k} such that

(K 4 , w) (K 4 ) * (w,7) (K 4 , w) 7
(G, w) is (2k + 1)-wide, the weighted graph G * (w,2k+1) is a k-partial (G, w) 2k+1 -distance graph.

Odd-girth and wideness

Here we will prove that for a complete distance graph of G to be (2k + 1)-wide is equivalent with G being of odd-girth at least 2k + 1. One direction of this claim is followed from definitions. We prove the other direction in the following general setting. Lemma 3.13. If B is of odd-girth 2k + 1, then any partial B-distance graph B is (2k + 1)-wide.

Proof. By the definition of a weighted graph to be (2k + 1)-wide, we only need to prove that the complete B-weighted graph B is (2k + 1)-wide. To do this we need to show that every odd-cycle C of ( B, w) 2k+1 has length at least 2k + 1. If C has exactly two vertices from B, then the length of C is exactly 2k + 1 by construction. Assume C has at least three vertices from B and denote them by x 1 , x 2 , . . . , x t in the clockwise orientation of C. Denote the distance from x i to x i+1 in C by l i . If there exist l i and l j such that l i , l j ≥ k, then t s=1 l s ≥ 2k + 1. So the length of C is at least 2k + 1. Suppose that l i < k for every i = 1, 2, . . . , t. Then we know that l i = d B (x i , x i+1 ), so there is a closed-walk of odd length going through

x 1 , x 2 , ... x t in B whose length is t s=1 l s . Since B is of odd-girth 2k + 1, we have t s=1 l s ≥ 2k + 1. So
the length of C is at least 2k + 1. Finally consider the case where there is exactly one l i with l i ≥ k. By symmetry we may assume l 1 ≥ k. Hence,

l i = d B (x i , x i+1 ) for i = 2, . . . , t. We consider into two subcases. If l 1 = k, then we have l 1 = w(x 1 , x 2 ) = k ≤ d B (x 1 , x 2 )
. By the triangular inequality, we get

l 2 + • • • + l t ≥ d B (x 1 , x 2 ). So t s=1 l s ≥ k + d B (x 1 , x 2 ) ≥ 2k. Since t s=1 l s is odd we have t s=1 l s ≥ 2k + 1. If l 1 ≥ k + 1, then l 1 = 2k + 1 -w(x 1 , x 2 ). Hence, t s=1 l s = 2k + 1 -w(x 1 , x 2 ) + l 2 + • • • + l t . Since w(x 1 , x 2 ) ≤ d B (x 1 , x 2 )
, by the triangular inequality, we have t s=1 l s ≥ 2k + 1. We conclude that C has length at least 2k + 1 in each case.

The following theorem is a key tool of our work. It claims, basically, that a homomorphism of a graph G to a graph H where both G and H are of odd-girth 2k + 1 can be viewed as a mapping which preserves more than just adjacency. It is only a restatement of Lemma 1.2 using the terminology we have just developed.

Theorem 3.14. Let G and H be two graphs of odd-girth 2k + 1. Let (G , w 1 ) be the partial G-distance graph consisting of all edges xy where x and y belong to a common (2k + 1)-cycle of G. Similarly, define (H , w 2 ) to be the partial H-distance graph consisting of all edges uv where u and v belong to a common (2k +1)-cycle of H. Then each homomorphism of G to H is also a homomorphism of (G , w 1 ) to (H , w 2 ).

Proof. This is also an application of the fact that a mapping of C 2k+1 to another cycles of the same length is rather an isomorphism and distances are preserved.

List of all (2k + 1)-wide complete graphs on t + 1 vertices

Given positive integers k and t, and toward working with graphs in PT t,2k+1 , we will need the list of all weightings w of the complete graphs on t + 1 vertices for which (K t+1 , w) is (2k + 1)-wide. As k and t are fixed numbers, this list can be easily computed. The computation of this list is further simplified by Theorem 3.7. We denote the list of such weightings by L(t + 1, 2k + 1). The total number of weightings on a K t+1 whose vertices are labeled, with weight of each edge being an integer between 1 and k, is k ( t+1 2 ) . This provides an upper bound on the number of elements of L(t + 1, 2k + 1). This upper bound is not too far from the exact number of elements by the following observation:

Proposition 3.15. If w is a weighting of K t+1 satisfying 2k 3 ≤ w(e) ≤ k, then (K t+1 , w
) is (2k +1)-wide. Proof. By Theorem 3.7 it is enough to check that for each triangle the induced weighted triangle is (2k + 1)-wide. Let a, b, c be weights of a triangle in (K t+1 , w). We use Proposition 3.5 to test if this triangle is (2k + 1)-wide.

If a + b + c is odd, then it is at least 2k + 1. If it is even, then a + b ≥ 4k 3 but c ≤ k, which implies a + b ≥ c.
Thus, given k and t, there are at least 1

( t+1 2 )! ( k 3 ) ( t+1
2 ) non isomorphic elements in L(t + 1, 2k + 1). We leave finding the exact number of elements of L(t + 1, 2k + 1) as an open question. To help with a better understanding of the notion, in Figure 3, we have provided the full list of 7 non-isomorphic elements of L(4, 5).

In the next lemma we show that our list L(t + 1, 2k + 1) maintains a weak notion of monotonicity. That is to say, if in a given (2k + 1)-wide weighting all entries corresponding to a vertex u are raised to the maximum possible value (which is k), then the result will still be a member of our list. Proof. By the assumption, we have w (e) ≤ k for every e ∈ E(K t+1 ). In order to prove that (K t+1 , w ) is (2k + 1)-wide, by the definition of (K t+1 , w ) 2k+1 , we only need to prove that every odd-cycle C which contains at least three vertices of K t+1 has length at least 2k + 1. Let v 0 be the vertex for which we change the weights of its adjacent edges.

If v 0 ∈ V (C), then the length of C is at least 2k + 1. Otherwise,
C is an odd-cycle of (K t+1 , w) 2k+1 . Hence, the length of C is at least 2k + 1.

Necessary and sufficient conditions

Here we would like to give a necessary and sufficient condition for a graph B of odd-girth 2k + 1 to bound the class of partial t-trees of odd girth 2k + 1. Our condition is expressed in the form of the existence of a family of cliques in a partially B-weighted graph. We start with a description of the main property this set of cliques must satisfy. We point out that deciding if there is a weighting on B for which such a set of cliques exists, and finding one such a set of cliques, when it exists, can be done in polynomial time (in terms of the order of B, k and t). Such an algorithm will be given in Section 5.

(t, 2k + 1)-closed sets of cliques

The following definition is a key property of a set of cliques in a partial B-weighted graph which we need for B, which is of odd-girth 2k + 1, to bound the class of all partial t-trees of odd-girth at least 2k + 1. We will provide an example to explain it better. Definition 4.1. Let (G, w) be a weighted (2k + 1)-wide graph. Let W be a collection of (weighted) (t + 1)-cliques (G, w). Observe that each member of W, without labeling of its vertices, is a member of L(t + 1, 2k + 1). We say W is (t, 2k + 1)-closed if the following is satisfied for each member W of W: Let v be a vertex of W and let a 1 , a 2 , . . . , a t be the weights of the edges of W incident to v (a i = w(vv i )). Suppose that switching the weights a 1 , a 2 , . . . , a t to a 1 , a 2 , . . . , a t while keeping all other weights the same results in another element of L(t + 1, 2k + 1). Then there must exist a clique W in W which is obtained from W by removing the vertex v and adding a vertex v where w(v v i ) = a i for i = 1, 2, . . . , t.

The definition is inspired by the construction of t-trees. Given a (t + 1)-clique W of a weighted t-tree G, if a new vertex is added which is joined to t vertices of W , and weighted in such a way that the new graph G is also (2k + 1)-wide, we want to be able to extend any mapping of G to the weighted graph B to a mapping of G to B. A (t, 2k + 1)-closed set of (t + 1)-cliques will do exactly this. And as we will prove, this is also a necessary condition.

For further clarification, we would like to point out a main difference between this definition and the list L(t + 1, 2k + 1): a (t, 2k + 1)-closed set is a set of (weighted) cliques in a weighted version of a given graph, thus in particular its vertices are labeled. In contrast, for the list L(t + 1, 2k + 1) the labeling of vertices is of no importance. The key here is the edge weights of graphs in the list which helps with keeping us within the condition of odd-girth at least 2k + 1.

For a better understanding of this definition we use the list of Figure 3. Suppose (B, w) is a weighted graph which is 5-wide (in a sense it is triangle-free), and let W be a collection of its 4-cliques which is (3, 5)-closed. Let W 1 be a member of W on vertices x, y, z, t and suppose that all edges are of weight 2, i.e., W 1 is isomorphic to the first weighted graph in the list of Figure 3. Consider the triangle induced by xyz, all whose edges are of weight 2. There are three other weighted K 4 's in the list L(4, 5) which contain triangles all whose edges are of weight 2. Those are the second, fifth and sixth graphs in Figure 3. Considering the first, the condition of 4.1 is the existence of a vertex u 111 which is adjacent to x, y and z (each edge having weight 1). The fifth element implies the existence of three other vertices: a vertex u 122 which is adjacent to x with an edge of weight 1 and to y and z both with edges of weight 2. Vertices u 212 and u 221 are defined similarly. Note that, by our definition, each of the three cliques induced by {x, y, z, u 122 }, {x, y, z, u 212 } and {x, y, z, u 221 } must be in W. Similarly, there must be three other vertices u 112 , u 121 and u 211 giving cliques isomorphic to the sixth element of the list. We note that each of these vertices might be used again to satisfy the condition for other triangles of W 1 or for elements of W. Altogether, as we will see later, the smallest 5-wide weighted graph with a nontrivial (3, 5)-closed set of 4-cliques has 16 vertices.

A (t, 2k + 1)-closed set of cliques of a weighted graph must then have a large number of (t + 1)-cliques. To find a smallest such set would probably address challenging questions. An easy lower bound on the number of elements of such a set is the number of elements of L(t + 1, 2k + 1). More precisely, given a (t, 2k + 1)-closed set of cliques, if it is nonempty, then it must have one (t + 1)-clique for each element of L(t + 1, 2k + 1) as we prove in the following theorem. Theorem 4.2. Given a (2k + 1)-wide weighted graph (G, w), if a nonempty collection W of its (t + 1)cliques is (t, 2k + 1)-closed, then for any weighting w of K t+1 such that (K t+1 , w) ∈ L(t + 1, 2k + 1) there is an isomorphic copy of (K t+1 , w) in W.

Proof. Since W is nonempty, there exists an element (K t+1 , w 0 ) in W. Let V (K t+1 ) = {v 0 , v 1 , . . . , v t }. If we change the weights of the edges adjacent to v 0 to k, then by Lemma 3.16 the resulting (t + 1)-clique is (2k + 1)-wide. As W is (t, 2k + 1)-closed, there exists a vertex u 0 which is adjacent to each of v 1 , v 2 , . . . , v t with an edge of weight k and such that the (t+1)-clique induced by u 0 , v 1 , v 2 , . . . , v t is in W. By repeating this process we may replace each v i with a vertex u i which is adjacent to the vertices of the current clique we are working on with edges of weight k. Thus at final step we have a clique in W all whose edges are of weight k.

In summary, starting with any (2k + 1)-wide (t + 1)-clique in W we get that there is a clique in W all whose edges are of weight k. However, this is a reversible construction, and starting with one such clique (where all edges are of weight k) and using the property of being (t, 2k + 1)-closed, we can get an isomorphic copy of any other member of L(t + 1, 2k + 1) in W.

A necessary and sufficient condition

Recall that PT t is the class of partial t-trees, and PT t,2k+1 is the subclass of partial t-trees of oddgirth at least 2k + 1. We are now ready to state and prove the following theorem, which provides a necessary and sufficient condition for a graph B of odd-girth 2k + 1 to bound PT t,2k+1 . We will give an algorithm to check this in Section 5.

Theorem 4.3. A graph B of odd-girth 2k + 1 admits a homomorphism from every partial t-tree of oddgirth at least 2k + 1 if and only if there exists a partial B-distance graph ( B, w) with a nonempty set W of (t + 1)-cliques of ( B, w) which is (t, 2k + 1)-closed.

Proof. First, we prove the sufficient part. Assume such a weighted graph B and a nonempty set W of (t + 1)-cliques exist. Suppose G is a partial t-tree of odd-girth at least 2k + 1. Let G be a t-tree containing G as a subgraph. We form a weighted graph on G by defining the weight function ϕ : E( G) → {1, 2, . . . , k} by ϕ(xy) = min{d G (x, y), k} for every xy ∈ E( G). By Lemma 3.13, we know that ( G, ϕ) is a (2k +1)-wide weighted graph. Let X 1 , X 2 , . . . , X s be a (t + 1)-clique-sequence from which G is built. Since X 1 is a subgraph of G, we know that (X 1 , ϕ) is (2k + 1)-wide. By Theorem 4.2, there is an isomorphic copy of X 1 in W, let C 1 be this copy. Let h be an isomorphism of X 1 to C 1 . Observe that, in particular, h is a homomorphism of X 1 to C 1 . Our goal is to extend h to a homomorphism of G to B. Let V (X 2 ) = {x 1 , x 2 , . . . , x t , x t+1 }. By the definition of partial t-trees, and without loss of generality, assume x 1 , x 2 , . . . , x t ∈ V (X 1 ). Since W is (t, 2k + 1)-closed and X 2 is (2k + 1)-wide, there exists y ∈ V (B) such that {y, h(x 1 ), h(x 2 ), . . . , h(x t )} induces a member of W and the weight of yh(x i ) is the same as the weight of ϕ(x t+1 x i ) for each i ∈ {1, 2, . . . , t}. Let h(x t+1 ) = y, hence, this extended mapping h is a homomorphism of (X 1 ∪ X 2 , ϕ) to B. By continuing this process, we eventually extend h to a homomorphism of ( G, ϕ) to ( B, w). Thus for each edge xy of G of weight 1, h(x)h(y) is an edge of B of weight 1. That is to say, h(x)h(y) is an edge of B. Therefore, h is also a homomorphism of G to B.

Next, we want to prove that the condition is necessary. We first define B as follows: vertices of B are the same as vertices of B. A pair x, y of vertices is an edge of B if x and y belong to a common (2k + 1)-cycle of B. Thus B does not necessarily contain all edges of B, but it does contain each pair that belongs to a common (2k + 1)-cycle and thus we may apply Theorem 3.14. We then define the weight ϕ of an edge xy of B to be the distance between x and y in B. That is the same as their distance in any (2k + 1)-cycle containing them since B is of odd-girth 2k + 1. Our aim is to show that ( B, ϕ) admits a nonempty set W of (t + 1)-cliques which is (t, 2k + 1)-closed.

Recall that given a t-tree G and a weighting w (1 ≤ w(e) ≤ k) of its edges we have associated with (G, w) a weighted graph G * (w,2k+1) which, by Proposition 3.12, is a partial distance graph of (G, w) 2k+1 . By Observation 3.11, for t ≥ 2, the underlying graph of G * (w,2k+1) is a partial t-tree. Since (G, w) 2k+1 is a partial t-tree of odd-girth 2k + 1, by our assumption, it admits a homomorphism to B. Thus, by Theorem 3.14, G * (w,2k+1) maps to ( B, ϕ). Intuitively speaking, the set W of (t + 1)-cliques we are looking for is a minimal set of (2k + 1)-cliques in a weighted version of B which are the images of cliques when mapping (2k + 1)-wide weighted graphs to the weighted version of B. More details are as follows.

Let PT * t,2k+1 be the set of weighted graphs G * (w,2k+1) , where G is a t-tree such that, together with edge-weighting w, (G, w) is (2k + 1)-wide. As mentioned above, each member of PT * t,2k+1 admits a homomorphism to ( B, ϕ). Observe that, in a mapping of any such member G * (w,2k+1) to ( B, ϕ), the image of any (t + 1)-clique of G * (w,2k+1) is a weighted (t + 1)-clique in ( B, ϕ). Let W be a minimal possible set of (t + 1)-cliques in ( B, ϕ) as the homomorphic images of such a mapping. More precisely, W is a set of (t + 1)-cliques in ( B, ϕ) such that (i) for every G * (w,2k+1) in PT * t,2k+1 there exists a homomorphism of G * (w,2k+1) to ( B, ϕ) such each (t + 1)-clique of G * (w,2k+1) is mapped to an element of W, and (ii) for each clique W ∈ W, W -W is not such a set. We will denote the existence of a homomorphism mentioned in i. by G * (w,2k+1) → ( B, ϕ, W). A restatement of (ii) is that for each clique W ∈ W, there exists a weighted graph G * (w,2k+1) in PT * t,2k+1 such that, in any mapping of G * (w,2k+1) , to ( B, ϕ, W) at least one of its (t + 1)-cliques is mapped to W .

We claim that W satisfies the condition of our theorem, i.e., W is not empty and (t, 2k + 1)-closed.

To see that W is not empty it is enough to take any (2k + 1)-wide K t+1 as (G, w) and consider the corresponding G * (w,2k+1) . To prove that W is (t, 2k+1)-closed, we take a (t+1)-clique, say C 1 , we take t vertices v 1 , v 2 , . . . , v t from C 1 and assume that adding a vertex x with ϕ(xv i ) = a i produces a (t + 1)-clique which is (2k + 1)-wide. Then we need to show that there exists a vertex v ∈ V (B) such that v 1 , . . . , v t , v induce a (t + 1)-clique in W and such that ϕ(vv i ) = a i for i = 1, . . . , t. Recall that, by the minimality of W, there exists an element ĜC1 which admits a ( B, ϕ, W)-mapping, but in any such a mapping at least one (t + 1)-clique is mapped to C 1 .

Consider all isomorphic copies of C 1 in ĜC1 (these are the (t + 1)-cliques that could potentially map to C 1 ). For each such t-clique W do as follows: let v 1 , v 2 , . . . , v t be vertices of W . Suppose that adding a vertex v to W and joining v to each v i with an edge of weight a i results in a (t + 1)-clique which is (2k + 1)-wide, i.e., the weighted clique is in L(t + 1, 2k + 1). Then, for each isomorphic copy of C 1 in ĜC1 , add a new vertex which is joined to vertices in the isomorphic copy with edges of corresponding weight from a 1 , a 2 , . . . , a t . Furthermore, for each newly added edge of weight a i , add two paths of respective length a i and 2k + 1 -a i connecting the two ends of this edge. Each edge of these two paths is of weight 1. Let G * be the new weighted graph. By construction and by Proposition 3.12, the weighted graph G * is a member of PT * t,2k+1 , and, therefore, there exists a homomorphism ρ of G * to ( B, ϕ, W). Recall that to complete our proof, given a clique C 1 in W, we need to show that, if for a vertex v of C 1 , the weights of the edges incident to v are changed from a 1 , a 2 , . . . , a t to a 1 , a 2 , . . . , a t , then there is a clique C 1 ∈ W realizing this new set of weights.

Observe that ĜC1 ⊆ G * , thus ρ induces a homomorphism of ĜC1 to ( B, ϕ, W). By the choice of ĜC1 , some (t + 1)-clique of ĜC1 , say K, is mapped to C 1 . However, in G * we have built a clique K such that t of its vertices are from K and a new vertex x is added which is adjacent to common vertices of K and K with weights a 1 , a 2 , . . . , a t . The image of x is then the vertex we are looking for and this completes our proof.

Algorithmic implications

Here we discuss how to apply the necessary and sufficient condition of Theorem 4.3 to decide whether a given graph B of odd-girth 2k + 1 bounds PT t,2k+1 . Since t and k are fixed integers, we can assume that the set L(t + 1, 2k + 1) is already computed. This is a list of order at most k ( t+1

2 ) and, therefore, of a constant size when t and k are fixed integers. We first form a weighted graph B whose vertices are vertices of B and edges are pairs uv such that u and v belong to a common (2k + 1)-cycle of B, the weight of each such edge being the distance u and v in the graph B. By the condition on the odd-girth of B, this distance is determined by the distance between u and v in one of the odd-cycles they both belong to.

Observe that determining if vertices u and v are in a common (2k + 1)-cycle of B is simple: starting at u, and iteratively, we compute the set N i (u) which consists of all vertices at distance i from u and, at each step, we check if v is in N i (u). If v / ∈ N i (u) for i ≤ k, then we conclude that the pair is in no common (2k + 1)-cycle. Otherwise, we may assume l is the first i such that v ∈ N i (u) (thus l = d B (u, v)). We then compute the set N 2k+1-2l (v). If this set has no intersection with N l (u), then u and v do not belong to a (2k + 1)-cycle. Otherwise we have found such a cycle.

Once we have our weighted graph B, we may list, in time at most |V (B)| t+1 , the set of all weighted (t + 1)-cliques of B. As t is a fixed number, with respect to the order of B, this list is provided in polynomial time. Let W be this ordered set of cliques whose elements are labeled W 1 , W 2 , . . . , W r . Next we would like to figure out if any subset of this list is (t, 2k + 1)-closed, and if so to output such a subset. To this end, given an element W i of W, we first check whether W passes the test of being (t, 2k +1)-closed with respect to W i . This is done in the following loop:

Let v 1 , v 2 , . . . , v t+1 be the vertices of W i , and let W i be a t-clique induced by W i after deleting a vertex v j . For simplicity we assume j = t + 1, but we must do this next inner loop for all v j , j = 1, 2, . . . , t + 1. In this inner loop we look for all elements of L(t + 1, 2k + 1) which can be regarded as an extension of the weights of W i by adding one more vertex and, for each such element of L(t + 1, 2k + 1), we consider all possible extensions. The number of such possibilities is a function of t and k, so it is constant with respect to our parameter which is the order of B. Consider one such extension ϕ. Thus ϕ is regarded as an edge weighting of a (t + 1)-clique, t of whose vertices are labeled v 1 , v 2 , . . . , v t and the last vertex is labeled v (which is not a vertex of B). Moreover, for each edge

v i v j , i, j ≤ t, we have ϕ(v i v j ) = d B (v i , v j ). Assume ϕ(v i v ) = a i , i = 1, 2, . . . , t. What we need to find now is a vertex v of B such that d B (v i , v) = a i for all i = 1, 2, . . . , t.
The existence of such a vertex v then can be checked easily by trying each vertex of B that is not also a vertex of

W i . If for some vertex v ∈ V (B) \ V (W i ) we have d B (v i , v) = a i ,
and the (t + 1)-clique obtained for W i by adding the vertex v is in W, then we consider this step of the inner loop verified and check the next embedding of W i among the members of L(t + 1, 2k + 1). If we cannot find any such vertex, then we conclude that W i cannot be in a set of (t, 2k + 1)-closed cliques. In that case, we remove W i from our list W and we start over. If at some point, for any choice of an element W of W, any choice of an induced t-clique W of W , and any embedding of W in elements of L(t + 1, 2k + 1), we find our required vertex v, then this list W of (t + 1)-cliques is (t, 2k + 1)-closed by definition and, therefore, it provides a certificate that B (or rather a subgraph of B induced by the edges of weights 1 of cliques in W ) bounds the class PT t,2k+1 . If, by repeating our loops and inner loops, we eventually delete all considered (t + 1)-cliques, i.e., when we arrive at the case W = ∅, we claim that our weighted graph B has no nonempty (t, 2k + 1)-closed set of (t + 1)-cliques. That is because if there were such a set W 1 , since at the start we considered all (t + 1)-cliques, we would have W 1 ⊆ W. But then each element of W 1 passes all our loops and thus no element of W 1 will ever be deleted.

Overall, in the discussion above, we have proved the following facts:

Theorem 5.1. Let t and k be given (fixed) positive integers and let B be a graph of odd-girth 2k + 1. Then

• we can decide in a finite number of steps if B bounds PT t,2k+1 ,

• this number of steps is bounded by a polynomial function of |V (B)| whose degree and coefficients are dependent on t and k,

• if the above steps certifies B as a bound for PT t,2k+1 , then it also outputs a (t, 2k + 1)-closed list of (t + 1)-cliques that we can use to find a mapping of any member of PT t,2k+1 to B.

There are a few important remarks to make here. First, in order not to underestimate the power of Theorem 4.3 and its algorithmic application, we would like to mention that, for the same general graph B of odd-girth 2k + 1, we do not know of any finite algorithm to decide whether B bounds the class of all planar graphs of odd-girth 2k + 1. While for certain cases, such as when B contains a K 4 , we have the trivial YES answer, for a general choice of B, finding such an algorithm may help to deal with some of the difficult conjectures which we have mentioned in this work. Another note is that, in the discussion before Theorem 5.1, we only cared to show that the algorithm we provide runs in a time polynomial in the order of B when t and k are fixed. To actually implement the algorithm, one may also apply further optimization. For example, having in hand a lower bound for the order of a (t, 2k + 1)-closed set of (t + 1)-cliques, if the order of W goes below such a threshold, we may stop with a negative answer. An example of such a lower bound is the number of elements of L(t + 1, 2k + 1). Recall that we must already have a list of them for our algorithm. The last note worthy comment here is about a weakness of our algorithm: when B is a bound, our algorithm provides a (t, 2k + 1)-closed set W of (t + 1)-cliques that we can use to map each member of PT t,2k+1 to B. However, the set created here is the largest of all such sets while, in practice, and toward optimization, we are interested in a smallest of such sets.

Projective cubes and bounding partial 3-trees

Theorem 4.3 is an extension of a necessary and sufficient condition provided in [START_REF] Beaudou | Homomorphism bounds and edge-colourings of K 4 -minor-free graphs[END_REF] to test whether a given graph of odd-girth 2k + 1 bounds the class of K 4 -minor-free graphs of odd-girth at least 2k + 1. The question of finding a smallest such graph is discussed in that paper, where it is shown that the order of a smallest such graph must be Θ(k 2 ). One naturally expects that the analogous question would become more difficult for PT t,2k+1 with t ≥ 3. While generally this might be the case, in this section we show that the case t = 3 is rather special by providing the optimal answer. Here we give a graph of odd-girth 2k + 1 on 2 2k vertices which bounds the class PT 3,2k+1 , and we point out that there can be no such graph with smaller order. Our results here can be viewed as the strongest support provided so far for the general case of a conjecture in extension of the four-color theorem. This conjecture will be restated after we introduce the necessary definitions.

We first recall the definition of a Cayley graph: let Γ be an additive group and let S be a symmetric subset of Γ (i.e., for each x ∈ S we have -x ∈ S), furthermore, suppose that 0 is not a member of S. Then the Cayley graph (Γ, S) is the graph whose vertices are elements of Γ, and where two vertices x and y are adjacent if and only if x -y ∈ S. The fact that S is symmetric implies that G is a graph and not a digraph. As we will consider only binary groups here, we have -x = x for each x, and thus all sets are symmetric here. The important advantage of considering Cayley graphs on binary groups is the naturally associated edge-coloring. Given a Cayley graph on a binary group, to each edge uv we assign

u + v = u -v = v -u ∈ S.
The main targets of this section are the following Cayley graphs on the binary group Z k 2 .

Definition 6.1. The projective cube of dimension k is the Cayley graph (Z k 2 , {e 1 , e 2 , . . . , e k , J}) where the e i 's are the vectors of the standard basis and J is the all-1 vector.

Recall that the Cayley graph (Z k 2 , {e 1 , e 2 , . . . , e k }) is the well known hypercube H(k), where graph distances are the same as Hamming distances. Therefore P C(k) is built from H(k) by adding an edge between antipodal pairs. It is not hard to see that this graph is also built from H(k + 1) by identifying antipodal pairs. This projection has given the choice of name "projective cube" for these graphs. However, they are more often referred to as "folded cube". It can be easily checked that P C(2k -1) is bipartite. On the other hand, P C(2k) is a 4-chromatic graph of odd-girth 2k + 1. It is easily verified that P C(2) is isomorphic to K 4 , thus the following conjecture of the second author from [START_REF] Naserasr | Homomorphisms and edge-coloring of planar graphs[END_REF] is an extension of the four-color theorem: Conjecture 6.2. Every planar graph of odd-girth at least 2k + 1 admits a homomorphism to P C(2k).

The conjecture is believed to be true for the larger class of K 5 -minor-free graphs (see [START_REF] Naserasr | Homomorphisms of planar signed graphs to signed projective cubes[END_REF]). Even a further extension using the notion of signed graphs is considered, we refer to [START_REF] Naserasr | Homomorphisms of planar signed graphs to signed projective cubes[END_REF] for more details. The conjecture is about finding an optimal bound in the following sense: it is proved in [START_REF] Naserasr | Walk-powers and homomorphism bounds of planar signed graphs[END_REF] that if the conjecture is true, then P C(2k) is a smallest graph (both in terms of the number of edges and of the number of vertices) of odd-girth 2k + 1 which bounds the class of all planar graphs of odd-girth at least 2k + 1. That is to say, if B is a graph of odd-girth 2k + 1 to which every planar graph of odd-girth at least 2k + 1 admits a homomorphism, then B has at least as many vertices and as many edges as P C(2k).

The case k = 1 of the conjecture is just the four-color theorem, and its extension to the K 5 -minor-free graphs is obtained by Wagner's theorem on decomposition of K 5 -minor-free graphs. The case k = 2 is proved in [START_REF] Naserasr | Homomorphisms and edge-coloring of planar graphs[END_REF] (using the four-color theorem) and its extension to K 5 -minor-free graphs is given in [START_REF] Naserasr | Homomorphisms of triangle-free graphs without a K 5minor[END_REF]. The case k = 3 follows from recent results on edge-coloring of planar multigraphs which are also based on the four-color theorem (see [START_REF] Naserasr | Homomorphisms of planar signed graphs to signed projective cubes[END_REF]).

For larger values of k the conjecture remains open, and the best known support was a verification for the class of K 4 -minor-free graphs proved in [START_REF] Beaudou | Homomorphism bounds and edge-colourings of K 4 -minor-free graphs[END_REF]. Here, as an application of our work, we show that the conjecture holds for the larger class of partial 3-trees of odd-girth at least 2k + 1. We note that this is a subclass of K 5 -minor-free graphs, but it does contain some non-planar graphs. Thus our result here provides the strongest evidence so far in support of the conjecture. To proceed we need to establish some notation and prove some properties of P C(2k). To this end we will have to provide proofs for some already known facts about projective cubes and then strengthen such results.

We start by recalling a general fact about Cayley graphs on binary groups. Let G be a Cayley graph on a binary group and let φ be the associated edge-coloring. Suppose v 1 , v 2 , . . . , v l , v 1 is a closed-walk of G (with this order of vertices). Then φ(v

1 v 2 ) + φ(v 2 v 3 ) + • • • + φ(v l v 1 ) = 2(v 1 + v 2 + • • • + v l ) = 0.
In particular this is the case for all cycles.

Consider the set S 2k = {e 1 , e 2 , . . . , e 2k , J}. The only linear relations among elements of S 2k are 2x = 0 for every x and x∈S 2k x = 0. This fact, together with the previous observation, partitions the set of cycles of P C(2k) into two types: (i) cycles C where φ(v 1 v 2 ) + φ(v 2 v 3 ) + • • • + φ(v l v 1 ) = 0 because every element of S 2k appears an even number of times as a color on the edges of C (0 as an even number is also allowed), and (ii) cycles C where φ(v

1 v 2 ) + φ(v 2 v 3 ) + • • • + φ(v l v 1 ) = x∈S 2k
x = 0, that is to say every element of S 2k appears as color on edges of C an odd number of times. As S 2k has an odd number of elements, this second type of cycles then correspond to the class of odd-cycles of P C(2k) while the first type correspond exactly the class of even-cycles. As a consequence, we get that P C(2k) has odd-girth 2k + 1. But in fact a stronger statement follows, based on the following notation:

Let u and v be two vertices of P C(2k), P be a shortest u -v path and S uv be the set of the colors of edges of P (thus S uv ⊂ S 2k ). Theorem 6.3. Given P C(2k) and any two vertices u and v, the set S uv corresponding to the colors of the edges of a shortest u -v path P is independent of the choice of P and thus well defined. Furthermore, given a u -v path P of length 2k + 1 -d(u, v), the set of colors of the edges of P is Suv = S 2k \ S uv and is thus independent of the choice of P .

Proof. Let P be a u -v path of length d(u, v) and let S uv be the set of colors of the edges of P . Our first claim is that |S uv | = d(u, v). Let s 1 , s 2 , . . . , s l be the elements of S uv that appear an odd number of times on the edges of P . If l = d(u, v), then each s i must appear exactly once and we are done. Otherwise, consider the path ux 1 x 2 . . . x l , with x 1 = u + s 1 and x i = x i-1 + s i for i = 2, . . . l. It follows that x l = v and that this is a shorter u -v path.

Next we claim that for S uv = S 2k \ S uv there is a u -v path P of length 2k + 1 -d(u, v) whose set of colors is S uv . Labeling elements of S uv as s 1 , s 2 , . . . , s r , one such a path P is uy 1 y 2 . . . y r , with y 1 = u + s 1 and y i = y i-1 + s i for i = 2, . . . , r, noting that y r must be v.

Observe that the color sets corresponding to the two paths P and P form a partition of S 2k into S uv (of size d(u, v)) and its complement S uv (of size 2k + 1 -d(u, v)). Now, as every u -v path Q of length d together with P forms a closed walk of length 2k + 1, and since P C(2k) has odd-girth 2k + 1, the set of colors corresponding to the edges of Q must be the complement of S uv , that is S uv . Similarly, every u -v path Q of length 2k + 1 -d must have the complement of S uv as its color set. This leads to the following labeling of the edges of the complete graph on 2 2k vertices using P C(2k). Definition 6.4. The P C(2k)-edge-labeled complete graph is the complete graph on vertices of P C(2k) where each edge uv is labeled by the partition {S uv , Suv }.

Observe that by replacing each such label with the order of S uv (that is the smallest of the two orders), we obtain the complete P C(2k)-distance graph which is (2k + 1)-wide since P C(2k) is of oddgirth 2k + 1. Before we use this labeling to apply Theorem 4.3 on the complete P C(2k)-distance graph, we use it to prove a high level of symmetry in P C(2k). To this end, we will need the following property of the complete P C(2k)-distance graph. • Each element of S 2k appears in an even number of the sets A, B or C, that is to say, either it appears in none of them, or in exactly two of them (this is the case when |A| + |B| + |C| is even).

• Each element of S 2k appears in an odd number of the sets A, B or C, that is to say, it appears either in exactly one of them, or in all three of them (this is the case when |A| + |B| + |C| is odd).

Proof. Observe that the choice of A corresponds to the colors of the edges of an x -y path P A . Similarly, the choice of B and C corresponds to x -z path P B and y -z path P C , respectively. Thus |A| + |B| + |C| corresponds to the length of the closed-walk starting at x and traversing P A , then P C and then returning to x through P B . Thus the sum of the elements of A and B and C is 0. This means that if a color comes an odd-number of times in the closed-walk, then so do all other colors, and thus |A| + |B| + |C| is an odd number. Otherwise all colors appear an even number of times, which means |A| + |B| + |C| is also even number.

Corollary 6.6. Given subsets A, B and C of the previous proposition such that |A| + |B| + |C| is odd, the number of elements that appears in all three of them is 1 2 (|A| + |B| + |C| -(2k + 1)). This corollary is of importance for two main reasons: The first reason is that |A|, |B| and |C| are the edge weights of a weighted triangle in the complete P C(2k)-distance graph induced by x, y and z. Thus this triangle is (2k + 1)-wide and the value 1 2 (|A| + |B| + |C| -(2k + 1)) of this corollary corresponds to the value f 2k+1 (|A|, |B|, |C|) of Proposition 3.6. The second reason is that the number of elements appearing in all three sets A, B and C is a function of the order of A, B and C and does not depend on the choice of A, B, C. This implies a very high level of symmetry as we will discuss below.

A graph G is said to be distance transitive if for every two pairs (u, v) and (x, y) of vertices, if d G (u, v) = d G (x, y), then there is an automorphism of G which maps u to x and v to y. Furthermore, G is said to be triple transitive if for every two triples (u, v, w) and (x,

y, z), if d G (u, v) = d G (x, y), d G (u, w) = d G (x, z), d G (v, w) = d G (y, z), then there is an automorphism ζ of G such that ζ(u) = x, ζ(v) = y and ζ(w) = z.
In the next theorem we give a proof of a result of [START_REF] Meredith | Triple transitive graphs[END_REF] (see also [START_REF] Brouwer | Distance-regular graphs[END_REF]) using the terminology we have developed here which claims that P C(2k) is triple transitive. The ideas developed in this proof are essential for the proof of Theorem 6.8. Theorem 6.7. The graph P C(2k) is triple-transitive.

Proof. In order to prove this we need to introduce automorphisms of this graph. To this end, similar to the labeling of the edges of the complete P C(2k)-labeled graph on 2 2k vertices, and using this labeling of edges, we label the vertices of P C(2k) also by partitions of S 2k . To start with, we label the vertex 0 by the trivial partition {∅, S 2k }. Then the vertex u receives the label of the edge 0u, that is {S 0u , S0u }. Using this labeling, one easily observes that every permutation of S 2k is an automorphism of the complete Lemma 6.11. Let G and H be two graphs of odd-girth at least 2k + 1 and let φ : V (G) → V (H) be a homomorphism of G to H. Then φ is also a homomorphism of G (2k-1) to H (2k-1) . Thus, if a graph B of odd-girth 2k + 1 bounds a class C of graphs, then |V (B)| is an upper bound on the order of clique number of graphs in {G (2k-1) |G ∈ C}. To prove that P C(2k) has the smallest order among graphs of odd-girth 2k + 1 bounding PT 3,2k+1 , we prove that this class of graphs has some weak sense of perfectness. That is to say, there is a graph G ∈ PT 3,2k+1 for which the clique number of G (2k-1) is 2 2k . This approach was introduced in [START_REF] Naserasr | Walk-powers and homomorphism bounds of planar signed graphs[END_REF], where a planar graph G of odd-girth 2k + 1 satisfying w(G (2k-1) ) = 2 2k was built. Our observation here is that the construction given there is also a partial 3-tree. Thus we only describe the construction to verify that the result is a partial 3-tree, and refer the reader to [START_REF] Naserasr | Walk-powers and homomorphism bounds of planar signed graphs[END_REF] for the verification of w(G (2k-1) ) = 2 2k . Theorem 6.12. There exists a partial 3-tree G of odd-girth 2k + 1 for which the graph G (2k-1) has clique number 2 2k . Sketch of proof: We consider the following construction of a planar graph G of odd-girth 2k + 1 whose walk power 2k -1 has a clique of order 2 2k . The graph G is built iteratively, starting with a particular subdivision G 0 of K 4 such, in a planar embedding, all four faces are odd-cycles of order 2k + 1. It is shown that for any such subdivision, the walk power 2k -1 is a complete graph on 4k + 2 vertices. Given an already constructed graph G i , if there is a u -v path P all of whose internal vertices are of degree 2, then first add a new u -v path P of the same length as P , and parallel to P so P and P make a new face of the plane graph, and then an internal vertex of P is connected to a particular internal vertex of P in such a way that the P P face is split into two faces, each being a (2k + 1)-cycle, the result is the graph G i+1 . If G (2k-1) i has a clique that uses l internal vertices of P , then we will find an extension of it in G (2k-1) i+1 which uses l more vertices. With a specific choice of a subdivision of K 4 and a specific rule on connecting P and P , at the end of this process we will have a graph G for which G (2k-1) has a 2 2k -clique.

What we observe furthermore are a few easy facts whose proofs we leave to the reader: * K 4 is the first 3-tree.

* If G is a partial 3-tree and e is an edge of G, the any subdivision of e results in a partial 3-tree.

* If G is a partial 3-tree and P is a path whose internal vertices are of degree 2, then adding a vertex which is joined to (only) three internal vertices of P is also a partial 3-tree.

One can view the construction of [START_REF] Naserasr | Walk-powers and homomorphism bounds of planar signed graphs[END_REF], sketched above, as repeated applications of these three steps. Thus the resulting graph at each step, and in particular at the final step, beside being a planar graph is also a partial 3-tree. We have thus constructed a partial 3-tree G of odd-girth 2k + 1 for which G (2k-1) has clique number at least 2 2k . That the clique number of G (2k-1) is indeed 2 2k and not bigger follows from the fact that G maps to P C(2k) by Theorem 6.9 (this fact was not verified in [START_REF] Naserasr | Walk-powers and homomorphism bounds of planar signed graphs[END_REF]).

In summary we have proved:

Theorem 6.13. The projective cube of dimension 2k, P C(2k), is a smallest graph, in terms of the number of vertices, of odd-girth 2k + 1 which bounds the class PT 3,2k+1 .

Application to edge-coloring

The edge-chromatic number of a multigraph G, denoted χ (G), is the smallest number of matchings into which E(G) can be partitioned. The fractional edge-chromatic number of G, denoted χ f (G), is the smallest total sum of nonnegative weights assigned to the matchings of G such that total weight of the matchings containing each given edge is at least one. Given a subset S of an odd number of vertices, it Using this theorem, it can be easily verified that a cubic multigraph has fractional edge-chromatic number exactly 3 if and only if it is bridgeless. Thus Tait's classic reformulation of the four-color theorem ( [START_REF] Tait | Remarks on the colouring of maps[END_REF], then a conjecture) is to say that the edge-chromatic number of a cubic bridgeless planar multigraph is equal to its fractional edge-chromatic number. With such a view, P. Seymour proposed the following strong generalization: Conjecture 7.2. [START_REF] Seymour | Unsolved problem in "Graph Theory and Related Topics[END_REF] For every planar multigraph we have χ (G) = χ f (G) .

The conjecture is proved for K 4 -minor-free graphs in [START_REF] Seymour | Colouring series-parallel graphs[END_REF] (a different proof is provided in [START_REF] Fernandes | Edge-coloring series-parallel multigraphs[END_REF]), and using this result it is proved in [START_REF] Marcotte | Optimal edge-colourings for a class of planar multigraphs[END_REF] for the larger class of K - 5 -minor-free graphs, where K - 5 is the graph obtained from K 5 by removing one edge. As a direct generalization of Tait's statement, the case of k-regular planar multigraphs satisfying χ f (G) = k has got more attention. After verifying a condition under which a k-regular multigraph satisfies χ f (G) = k, this special case of the conjecture can be restated as:

Conjecture 7.3. If G is a planar k-regular multigraph in which any set X of an odd number of vertices is connected to V (G) \ X by at least k edges, then G is k-edge-colorable.

The cases k = 4, 5 of this conjecture are proved in [START_REF] Guenin | Packing T-joins and edge-colouring in planar graphs[END_REF], the case k = 6 in [START_REF] Dvořák | Packing six T-joins in plane graphs[END_REF], the case k = 7 in [START_REF] Edwards | Optimization and packings of T-joins and T-cuts[END_REF] (see also [START_REF] Chudnovsky | Edge-coloring seven-regular planar graphs[END_REF]) and the case k = 8 in [START_REF] Chudnovsky | Edge-colouring eight-regular planar graphs[END_REF]. Proofs are based on induction on k, thus dependent on the case of k = 3 which is equivalent to the four-color theorem. The case k = 4 is known to imply the four-color theorem and one cannot expect an independent proof, however, it is not known whether the cases k ≥ 5 are stronger than the four-color theorem, though we expect them to be.

In this section, providing support for the general case of Conjecture 7.3, and as an application of our work, we prove that Conjecture 7.3 holds on the subclass of (2k + 1)-regular planar multigraphs whose duals are partial 3-trees. This subclass of planar graphs can be characterized as a minor closed family of graphs with four forbidden minors given in Figure 4. Observe that two of these forbidden minors are K 5 and K 3,3 , whose absence as a minor implies planarity, and that the other two are duals of the two planar graphs of Figure 1. Let G be a planar (2k + 1)-regular multigraph whose dual is a partial 3-tree. Furthermore, assume that for each subset X of an odd number of vertices, the number of edges connecting X to V (G)\X is at least 2k + 1. Then χ (G) = 2k + 1.

Proof. Let G be a planar (2k + 1)-regular multigraph, together with a planar embedding, and G D be its duals together with the corresponding planar drawing. Let X be a set of vertices of G and let δ(X) be the set of edges with one end in X and another end in V (G) \ X. Each vertex of G corresponds to a facial cycle of G D , which is a cycle of length 2k + 1. More generally, given a set X of vertices of G, δ(X) corresponds to a cycle C X of length |δ(X)| which bounds |X| faces of G D . As all of the facial cycles are of odd-length, the parity of C X is determined by the parity of |X|. In other words, C X is an odd-cycle if and only if X contains an odd number of the vertices of G. Thus the condition on G that for every set X of an odd number of vertices δ(X) has at least 2k + 1 edges is equivalent to the statement that G D has odd-girth 2k + 1.

Since G D has odd-girth 2k + 1, and since we have assumed it is a partial 3-tree, by Theorem 6.9 it admits a homomorphism to P C(2k). Under any such mapping, the image of each (2k + 1)-cycle of G D is a (2k + 1)-cycle of P C(2k). Recall that the edges of P C(2k) are colored by the elements of the

Figure 1 :

 1 Figure 1: Forbidden minors of the class of partial 3-trees

Proposition 3 . 6 .

 36 Let (K 3 , w) be a weighted triangle with edge weights a, b, c satisfying 1 ≤ a, b, c ≤ 2k such that a + b + c is odd. Let f 2k+1 (a, b, c) = 1 2 (a + b + c -(2k + 1)). Then (K 3 , w) is (2k + 1)-wide if and only if 0 ≤ f 2k+1 (a, b, c) ≤ min{a, b, c}.

Figure 2 :

 2 Figure 2: Examples of (G, w) 2k+1 and G * (w,2k+1)

Figure 3 :

 3 Figure 3: The list L(4, 5) of all 5-wide K 4 's

Proposition 6 . 5 .

 65 Let x, y and z be three vertices of the P C(2k)-edge-labeled complete graph. Let A ∈ {S xy , Sxy }, B ∈ {S xz , Sxz } and C ∈ {S yz , Syz }. Depending on the parity of |A| + |B| + |C|, one of the following holds:

  can be verified that 2|E(G[S])| |S| -1 is a lower bound for χ f (G). Let Λ(G) = max |S|odd { 2|E(G[S])| |S| -1 }.We refer to the text book[START_REF] Scheinermann | Fractional graph theory: a rational approach to the theory of graphs[END_REF] for more on fractional coloring and for a proof and references to the following theorem: Theorem 7.1. Given a multigraph G we have χ f (G) = max{∆(G), Λ(G)}.

Figure 4 :

 4 Figure 4: Forbidden minors of the class of planar graphs whose duals are partial 3-trees

  Lemma 3.2. Given two weighted graphs (G, w 1 ) and (H, w 2 ) such that w 1 and w 2 are both bounded from above by 2k, if (G, w 1 ) → (H, w 2 ) and (H, w 2 ) is (2k + 1)-wide, then so is (G, w 1 ).

Lemma 3.3. Given two weighted graphs (G, w 1 ) and (H, w 2 ) which are both (2k + 1)-wide, if (G, w 1 ) → (H, w 2 ) then (G, w 1 ) 2k+1 → (H, w 2 ) 2k+1 .

$ This work is supported by the ANR-France project HOSIGRA (ANR-17-CE40-0022), by Fujian Provincial Department of Science and Technology (2016J01041) and by Fujian Provincial Department of Education (JZ160473). Preprint submitted to Journal of Combin. Theory series B December 13, 2019

Acknowledgement

We would like to thanks Eric Sopena for carefully reading this work and helping us to improve the presentation of this work. Similarly we would like to thanks anonymous referees.

P C(2k)-labeled graph and, therefore, also an automorphism of P C(2k). In fact this is the full list of automorphisms that has 0 as its fixed point, but we do not need to prove this fact here. Given a set A ⊂ {e 1 , e 2 , . . . , e 2k }, one may get an automorphism of the complete P C(2k)-labeled graph (and thus of P C(2k)) by mapping the vertex labeled {X, X} to the vertex labeled {X ⊕ A, X ⊕ A} (if a is the vector in Z 2k 2 whose support is A, then this automorphism corresponds to the mapping u → u + a). Unless A is the empty set, this automorphism never fixes the vertex 0. By composing two of the automorphisms described above one clearly gets an automorphism of the complete P C(2k)-labeled graph and thus of P C(2k). This is indeed the full list of automorphisms of this graph, but we do not need to prove this stronger statement here either.

To prove the claim of the theorem, let {x, y, z} and {u, v, w} be two triples of vertices of P C(2k) such that d P C(2k) (x, y) = d P C(2k) (u, v), d P C(2k) (x, z) = d P C(2k) (u, w) and d P C(2k) (y, z) = d P C(2k) (v, w). Note that by taking a symmetric difference, one may easily map the vertex u to the vertex x. If v and w are mapped to v and w by this automorphism, then it is enough to prove that the triple {x, v , w } can be mapped to {x, y, z} by an automorphism of P C(2k), so we may assume u = x in the rest of this proof.

The assumption of We are now ready to prove that the projective cube of dimension 2k satisfies the conditions of Theorem 4.3 for t = 3 and odd-girth 2k + 1. Theorem 6.8. The set W of all the 4-cliques of the complete P C(2k)-distance graph is (3, 2k +1)-closed.

Proof. Our proof is based on Theorem 6.7, and on the terminology developed in this section and in the proof of Theorem 6.7. Since the projective cube P C(2k) is triple-transitive, we only need to prove that, for each (2k + 1)-wide weighted graph (K 4 , w), there is an isomorphic copy of (K 4 , w) in W.

Let (K 4 , w) be a (2k + 1)-wide graph with vertices x, y, z, t. Suppose that w(xy) = a , w(xz) = b , w(xt) = c , w(zt) = a, w(yt) = b and w(yz) = c. To show that there exists at least one isomorphic copy of this graph in the P C(2k)-distance graph, using the development in the proof of the previous theorem, it is be enough to find subsets S x , S y , S z and S t of S 2k such that the symmetric difference of any two of them, or the complement of this set, has the same order as the weight on the corresponding edge. For example, we want the symmetric difference S x ⊕ S y to be of order either a or 2k + 1 -a .

We recall that, by Proposition 6.5, with such a choice of the three subsets S x , S y and S z , the three symmetric differences corresponding to the edges of the xyz-triangle, i.e., S x ⊕ S y , S y ⊕ S z and S z ⊕ S x , have the property that each element of S 2k is in an odd number of them, that is to say, each element is either exactly in one or in all three of them. Thus to prove our theorem, in what follows, we show how to make this property hold for each triangle of the K 4 .

If necessary, we change the weight of an edge to its complementary weight 2k + 1 -w to make sure that the elements of each pair {a, a }, {b, b }, {c, c } are of the same parity and the sum a + b + c is odd. Therefore, the weight sum of the four triangles of (K 4 , w) are a + b + c, a + b + c , a + b + c and a + b + c, each being an odd number. Let

2 (a +b+c -2k -1), and f t = 1 2 (a +b +c-2k -1). Since (K 4 , w) is (2k +1)-wide, by Theorem 3.7, each of its four triangles is (2k + 1)-wide. Then by Proposition 3.6, we conclude that each of the four values f v , v ∈ {x, y, z, t}, is a nonnegative integer not larger than the minimum of the three elements defining it.

Next, we will assign a subset A vv of S 2k = {e 1 , e 2 , . . . , e 2k , J} to each edge vv of K 4 such that |A vv | (the order of A vv ) is either w(vv ) or 2k + 1 -w(vv ) and such that, for each triangle uvw of K 4 , each element of {e 1 , e 2 , . . . , e 2k , J} appears either in exactly one of A uv , A uw , A vw or in all of them, in order to satisfy Proposition 6.5 (here, u, v and w can be any triple among x, y, z, t; similarly v, v can be any pair of vertices chosen from these four vertices).

Without loss of generality, assume that f x = min{f x , f y , f z , f t }. Our idea is to choose the six subsets A vv of S 2k (v and v being two distinct vertices of (K 4 , w)) in such a way that an f x number of the elements of S 2k belong to all six of them (unlike the other conditions, this is not the only way, depending on the weight function w of (K 4 , w), there could be other types of solutions). Then, for the three edges not incident to x (i.e., the edges of the triangle yzt), we will partition the remaining elements of S 2k according to the weight of the corresponding edges. Next, for each of the three triangles, namely xyz, xyt and xzt, we need to pick, respectively, f t -f x , f z -f x and f y -f x more common elements. The details of the whole process is as follows.

Let S x be a subset of S 2k = {e 1 , e 2 , . . . , e 2k , J} of order f x . We partition the set S 2k \ S x into three disjoint subsets S yz , S yt and S zt of order

Observe that one of these sets might be empty, but we cannot have two of them empty. For example, if c -

). Adding up these two identities we conclude that a = 2k + 1, but we are restricted to the weights from 1 to 2k. Define A yz = S yz ∪ S x , A yt = S yt ∪ S x and A zt = S zt ∪ S x .

Let S y , S z and S t be subsets of S 2k such that S y ⊂ S zt and

In summary, we have built subsets A zt , A yt , A yz , A tx , A zx and A yx such that: (1) 2) for each triangle induced by three vertices among {x, y, z, t}, in the three sets corresponding to the three edges, each element of S 2k appears either once or three times.

With these choices of A vv , we may choose the following set of four vertices in P C(2k)-distance graph. The first vertex, say x, can be any vertex. The vertices y, z and t are defined as follows:

, where the addition is done in Z 2k

2 . The fact that every element of S 2k is in either all three of A xy , A xz and A yz or just in one of them, implies that z = y + si∈Ayz s i . For the same reason, similar relations hold between any two of the four vertices, that is to say, their binary difference is equal to the sum of the elements of the set associated with the corresponding edge.

Recall that the size of A uv is either d(u, v) or 2k + 1 -d(u, v). Thus the four vertices x, y, z, t we have defined above will have distances in P C(2k) equal to the corresponding weights in (K 4 , w) that we have started with. This completes the proof.

Remark

In the proof of this theorem we chose S x to be a subset of all the sets A uv . Depending on the weight function w, other solutions may exist. This shows that P C(2k) being triple transitive is the limit of the symmetries of this graph and that P C(2k) is not 4-tuple transitive.

In support of Conjecture 6.2, we have the following theorem which is an immediate corollary of Theorem 4.3 and Theorem 6.8. Theorem 6.9. The projective cube of dimension 2k, P C(2k), is a graph of odd-girth 2k + 1 which bounds the class of partial 3-trees of odd-girth at least 2k + 1.

Next we claim that P C(2k) is a smallest graph of odd-girth 2k + 1 which may satisfy the statement of the previous theorem. This claim is implicitly proved in [START_REF] Naserasr | Walk-powers and homomorphism bounds of planar signed graphs[END_REF] based on the following notation. Definition 6.10. Given a graph G of odd-girth 2k + 1 and an integer l, l < k, the walk power G (2l+1) of G is defined to be the graph on V (G) where vertices u and v are adjacent if and only if there is a (u -v)-walk of length 2l + 1.

Given an odd number 2l + 1, traversing an edge uv an odd number of times is a (u -v)-walk of length 2l + 1. Thus G is a subgraph of G (2l+1) for any choice of l. This is one of the main reasons because of which we only considered walks of odd-length in this definition. The other reason is that the choice of an odd number 2l + 1 together with the condition of G being of odd-girth at least 2l + 3 insure that G (2l+1) has no loop. The following easy lemma is the main interest of this definition for us:

We restate the theorem also using the set of four forbidden minors: Theorem 7.5. Let G be a (2k + 1)-regular multigraph which does not contain any of the four graphs of Figure 4 as a minor. Furthermore, assume that for each subset X of an odd number of vertices, the number of edges connecting X to V (G) \ X is at least 2k + 1. Then χ (G) = 2k + 1.

Remarks and discussion

At the end we have a few remarks: 1. We gave an independent proof that P C(2k) is triple-transitive. The proof was based on the fact that given triples x, y, z and subsets A, B and C of S 2k corresponding to three edges of the triangle induced by xyz in P C(2k)-distance complete graph, if |A| + |B| + |C| is odd, then each element of S 2k is either in all three of them or exactly in one of them. Furthermore, the number of elements in all three of them is only a function of the distances between x, y and z. But if a set of four vertices is selected, then the common elements among six sets corresponding to the six edges of K 4 is no longer determined uniquely by the distances between the six pairs. Thus we can easily show that P C(2k) is not 4-tuple-transitive. When viewed as signed graphs, these properties extend to P C(2k -1) as well. This will be addressed in forthcoming work.

2. We find it rather surprising that a sort of perfectness holds for the class of partial 3-trees in the following sense. The order of a smallest graph of odd-girth 2k + 1 to which every partial 3-tree of odd-girth at least 2k + 1 admits a homomorphism, the largest chromatic number of G (2k-1) when G is a partial 3-tree of odd-girth at least 2k + 1 and the largest clique number of G (2k-1) when G is a partial 3-tree of odd-girth at least 2k + 1 are all 2 2k . This is not necessarily the case for the class of partial t-trees, t = 3. For example, for the class of partial 2-trees, which is the same as the class of K 4 -minor-free graphs, the smallest triangle-free graph to which every triangle-free graph with no K 4 -minor admits a homomorphism is of order 8, but the largest clique one can find in a G (3) where G is a triangle-free graph with no K 4 -minor is 6 (ongoing work of W. He, second author and Q. Sun, [START_REF] He | Walk-powers and homomorphism bound of K 4 -minor-free graphs[END_REF]).

3. We showed that P C(2k) has the smallest number of vertices among all graphs of odd-girth 2k + 1 which bounds all partial 3-trees of odd-girth at least 2k + 1. It follows from a simple construction in [START_REF] Naserasr | Mapping planar graphs into projective cubes[END_REF] that any such minimal bound must be of minimum degree at least 2k + 1. Thus P C(2k) is also optimal in term of the number of edges.

4. Using terminology and discussions of [START_REF] Naserasr | Homomorphisms of planar signed graphs to signed projective cubes[END_REF] and [START_REF] Naserasr | Homomorphisms of signed graphs[END_REF], the question of bounding signed bipartite partial t-trees will be addressed in a forthcoming work. Using such results, we will be able to present a 2k-regular analogue of Theorem 7.4.