Pascal Ochem
email: pascal.ochem@lirmm.fr

Alexandre Pinlou
email: alexandre.pinlou@lirmm.fr

Sagnik Sen

Homomorphisms of 2-edge-colored triangle-free planar graphs 1

Keywords: 2-edge-colored graph, Graph homomorphism, Discharging method

In this paper, we introduce and study the properties of some target graphs for 2-edge-colored homomorphism. Using these properties, we obtain in particular that the 2-edge-colored chromatic number of the class of triangle-free planar graphs is at most 50. We also show that it is at least 12.

Introduction

Graph homomorphisms and proper graph colorings are closely related. Indeed, the homomorphisms ϕ : G → K k are the k-colorings of G. This explains that homomorphisms of G to H are usually called H-colorings of G (we also say G is H-colorable) and that the vertices of such graphs H are called colors. The chromatic number of G is defined as the minimum number of colors k such that G admits a k-coloring; it can be equivalently defined as the minimum order of a graph H such that G → H. In this paper, we propose to study homomorphisms of 2-edge-colored graphs and the related notion of coloring. They have been already studied as a way of extending classical results in graph coloring such as Hadwiger's conjecture. Guenin [START_REF] Guenin | Packing odd circuit covers: a conjecture[END_REF] introduced the notion of switching homomorphism for its relation with a well known conjecture of Seymour. In 2012, this notion has been further developed by Naserasr et al. [START_REF] Naserasr | Homomorphisms of signed graphs[END_REF] as this theory captures a number of well known conjectures which can be reformulated using the definitions of switching homomorphism. In this paper, we study 2-edge-colored graph homomorphisms and switching homomorphisms for themselves.

A 2-edge-colored graph (G, s) is a simple graph G with a signature s : E(G) → {-1, +1} assigning a negative or positive sign to every edge of G. In the figures, negative edges are drawn with dashed edges. Figure 1(a) gives an example of 2-edge-colored graph. Switching a vertex v of a 2-edge-colored graph (G, s) corresponds to giving the opposite sign to the edges incident to v. Given a 2edge-colored graph (G, s) and a set of vertices X ⊆ V (G), the graph obtained from (G, s) by switching every vertex in X is denoted by (G, s (X) ). Let ∂(X) denote the edge cut between X and G\X. Notice that (G, s (X) ) is equivalently obtained by changing the sign of all the edges in ∂(X).

Two 2-edge-colored graphs (G, s 1 ) and (G, s 2 ) are switching equivalent if we can obtain (G, s 1 ) from (G, s 2 ) by switching a set of vertices of (G, s 2 ), i.e., s 2 = s (X) 1 with X ⊆ V (G). If (G, s 1 ) and (G, s 2 ) are switching equivalent, we write (G, s 1 ) ∼ (G, s 2 ). Figure 1 gives an example of switching equivalent 2-edge-colored graphs where the surrounded vertices belong to X. We use the notation (G) for a 2-edge-colored graph when its signature is not relevant or is clear from the context, whereas G refers to the underlying simple graph of (G).

Given two graphs (G, s) and (H, t), ϕ is a 2-edge-colored homomorphism of (G, s) to (H, t) if ϕ : V (G) → V (H) is a mapping such that every edge of (G, s) is mapped to an edge of the same sign in (H, t). Given two graphs (G, s 1 ) and (H, t 1 ), we say that there is a switching homomorphism ϕ of (G, s 1 ) to (H, t 1 ) if there exist (G, s 2 ) ∼ (G, s 1 ) and (H, t 2 ) ∼ (H, t 1 ) such that ϕ is a 2-edge-colored homomorphism of (G, s 2 ) to (H, t 2 ).

Lemma 1 If (G, s) admits a switching homomorphism to (H, t), then there exists (G, s ) ∼ (G, s) such that (G, s ) admits a 2-edge-colored homomorphism to (H, t).

Proof. Since (G, s) admits a switching homomorphism to (H, t), this implies that there exist (G, s ) ∼ (G, s), (H, t ) ∼ (H, t), and a 2-edge-colored homomorphism ϕ of (G, s ) to (H, t ). Let X ⊆ V (H) be such that (H, t ) = (H, t (X) ). Let Y = {v ∈ V (G) | ϕ(v) ∈ X}. Let (G, s ) = (G, s (Y ) ). For every uv ∈ E(G) we have:

• s (uv) = -s (uv) ⇐⇒ uv ∈ ∂(Y ) by the switching of Y .

• t(ϕ(u)ϕ(v)) = -t (ϕ(u)ϕ(v)) ⇐⇒ ϕ(u)ϕ(v) ∈ ∂(X) by the switching of X.

• uv ∈ ∂(Y ) ⇐⇒ ϕ(u)ϕ(v) ∈ ∂(X) by the definition of Y .

• s (uv) = t (ϕ(u)ϕ(v)) by the definition of ϕ.

Then we deduce that s (uv) = t(ϕ(u)ϕ(v)), which means that ϕ is a 2-edgecolored homomorphism of (G, s ) to (H, t).

2

The above lemma implies that, in order to prove the existence of a switching homomorphism of (G, s) to (H, t), there is no need to switch (H, t).

The 2-edge-colored chromatic number χ 2 (G, s) of the graph (G, s) is the minimum order (number of vertices) of a graph (H, t) such that (G, s) admits a 2-edge-colored homomorphism to (H, t). Similarly, we define χ sw (G, s) as the minimum order of a graph (H, t) such that (G, s) admits a switching homomorphism to (H, t). Equivalently,

χ sw (G, s) = min {χ 2 (G, s ) | (G, s ) ∼ (G, s)}. The 2-edge-colored chromatic number χ 2 (G) of a simple graph G is defined as the maximum χ 2 (G) = max {χ 2 (G, s)} over all signatures. The 2-edge- colored chromatic number χ 2 (C) of a class of simple graphs C is defined as χ 2 (C) = max{χ 2 (G) | G ∈ C}. Similarly, χ sw (G) = max {χ sw (G, s)} and χ sw (C) = max{χ sw (G) | G ∈ C}.
An equivalent definition of the 2-edge-colored chromatic number can be given by defining 2-edge-colored coloring. A 2-edge-colored k-coloring of a 2-edgecolored graph (G, s) is a proper vertex-coloring ϕ : V (G) → {1, 2, . . . , k} such that if there exist two edges uv and xy with ϕ(u) = ϕ(x) and ϕ(v) = ϕ(y), then these two edges have the same sign. Notice that given such a coloring, we can construct the target graph (H, t) associated to ϕ such that V (H) = {1, 2, . . . , k} and for every uv ∈ E(G) there exists e = ϕ(u)ϕ(v) ∈ E(H) such that t(e) = s(uv). Hence, the 2-edge-colored chromatic number of (G) is the minimum number of colors needed for a 2-edge-colored coloring of (G).

We use the following notations. The set of positive (resp. negative) neighbors of a vertex v in a 2-edge-colored graph is denoted by

N + (v) (resp. N -(v)). A vertex of degree k (resp. at least k, at most k) is called a k-vertex (resp. k-vertex, k-vertex). A path (resp. a cycle) containing k edges is called a k-path (resp. a k-cycle).
In this paper, we study 2-edge-colored and switching homomorphisms of outerplanar and planar graphs of given girth. In Section 2, we introduce and study the properties of several families of target graphs, namely the antitwinned graph AT (G, s), the 2-edge-colored Zielonka graph SZ k , the 2-edgecolored Paley graph SP q , and the 2-edge-colored Tromp Paley graph T r(SP q ). We consider 2-edge-colored homomorphisms of planar graphs and outerplanar graphs in Section 3 and we provide lower and upper bounds on the 2-edgecolored chromatic number. In particular, we prove that 12 χ 2 (P 4 ) 50. This improves the previous known upper bound of 80 that holds for planar graphs. We obtain results on switching homomorphisms of planar graphs and outerplanar graphs of given girth in Section 4. We finally conclude in Section 5.

Target graphs

Given a class of simple graphs C, we say that a 2-edge-colored graph (H) is C-universal if every 2-edge-colored graph (G) such that G ∈ C admits a 2-edge-colored homomorphism to (H).

In this section, our goal is not only to find target graphs that will give the required upper bounds of our results in Sections 3 and 4. We describe several families of target graphs that may be C-universal, for some classes C, and we determine their properties. We consider below anti-twinned graphs, the 2-edge-colored Zielonka graph SZ k , the 2-edge-colored Paley graph and the 2-edge-colored Tromp Paley graph.

We say that a 2-edge-colored graph (G, s) is

• vertex-transitive if for every two vertices u and v, there exists a 2-edgecolored automorphism mapping u to v. • arc-transitive if for every vertices u 1 , u 2 , v 1 , and v 2 such that u 1 u 2 and v 1 v 2 are edges of the same sign, there exists a 2-edge-colored automorphism mapping u 1 to v 1 and u 2 to v 2 . • triangle-transitive if for every vertices u 1 , u 2 , u 3 , v 1 , v 2 , and v 3 such that u 1 u 2 u 3 and v 1 v 2 v 3 are triangles satisfying s(u

1 u 2 ) = s(v 1 v 2 ), s(u 2 u 3 ) = s(v 2 v 3 )
, and s(u 3 u 1 ) = s(v 3 v 1 ), there exists a 2-edge-colored automorphism mapping u 1 to v 1 , u 2 to v 2 , and u 3 to v 3 .

Anti-twinned graphs

In a 2-edge-colored graph, two distinct vertices u and v are twins if

N + (u) = N + (v) and N -(u) = N -(v). Also, u and v are anti-twins if N + (u) = N -(v)
and N -(u) = N + (v). Note that twins (resp. anti-twins) are necessarily nonadjacent. Moreover, if u has two anti-twins v 1 and v 2 , then v 1 and v 2 are twins. A 2-edge-colored graph is twin-free if it contains neither a pair of twins nor a pair of anti-twins.

Let (G, s) be a 2-edge-colored graph and let (G +1 ) and (G -1 ) be two copies of (G). The vertex corresponding to u ∈ V (G) in (G i ) is denoted by u i . We define the graph AT (G, s) = (H, t) on 2|V (G)| vertices as follows:

• V (H) = V (G +1 ) ∪ V (G -1 ) • E(H) = {u i v j : uv ∈ E(G), i ∈ {-1, +1} , j ∈ {-1, +1}} • t(u i v j ) = i × j × s(uv)
Figure 2 illustrates the construction of the graph AT (G, s).

v +1 u -1 v -1 (G +1 ) (G -1 ) u +1
Fig. 2. The graph AT (G, s).

We say that a The Zielonka graph Z k is an oriented graph introduced by Zielonka [START_REF] Zielonka | Time-stamp systems for a fixed set of agents[END_REF] in the theory of bounded timestamp systems. Raspaud and Sopena [START_REF] Raspaud | Good and semi-strong colorings of oriented planar graphs[END_REF] have used Z k in the context of oriented homomorphism. Alon and Marshall [START_REF] Alon | Homomorphisms of edge-colored graphs and Coxeter groups[END_REF] have adapted this construction to m-edge-colored graphs in order to get bounds on the m-edge-colored chromatic number of graphs having an acyclic k-coloring. Let us describe the construction of the 2-edge-colored Zielonka graph SZ k corresponding to the case m = 2. Every vertex is of the form (i; α 1 , α 2 , . . . , α k ) where 1 i k, α j ∈ {-1, +1} for j = i, and

α i = 0. Thus, |V (SZ k )| = k • 2 k-1
. For i = j, there is an edge between the vertices (i; α 1 , α 2 , . . . , α k ) and (j; β 1 , β 2 , . . . , β k ) and the sign of this edge is the product α j × β i .

Proposition 5

The graph SZ k is anti-twinned.

Proof. We denote by s the signature of SZ k . By definition of an anti-twinned graph, we have to show that every vertex of SZ k has a unique anti-twin. To prove that the anti-twin of the vertex u = (i; α 1 , α 2 , . . . , α k ) is the vertex u = (i; -α 1 , -α 2 , . . . , -α k ), we check that for every edge uv, the edge u v exists and that s

(u v) = -s(uv). If uv is an edge, then v = (j; β 1 , β 2 , . . . , β k ) for some j = i and thus s(u v) = (-α j ) × β i = -(α j × β i ) = -s(uv). 2

The 2-edge-colored Paley graph SP q

In the remainder of this section, q is any prime power such that q ≡ 1 (mod 4). We denote by F q the unique (up to isomorphism) finite field of order q. Let g be a generator of the multiplicative group F * q and let sq : F * q → {-1, +1} be the function square defined as sq(v) = +1 if and only if v is a square of F q . Note that g is necessarily a non-square, so that sq(g t ) = (-1) t .

(1)

The Paley graph P q is the undirected graph with vertex set V (P q ) = F q and edge set E(P q ) = {xy | sq(yx) = +1}. Since -1 is a square in F q , sq(x-y) = sq(yx) and therefore the definition of an edge is consistent. A Paley graph is vertex-transitive, arc-transitive, and self-complementary [START_REF] Sachs | Über selbstkomplementäre graphen[END_REF], that is, it is isomorphic to its complement.

A strongly regular graph with parameters (n, k, λ, µ) is a k-regular graph G with n vertices such that (1) every two adjacent vertices have λ common neighbors and (2) every two non-adjacent vertices have µ common neighbors. Paley graphs P q are known to be strongly regular graphs with parameters q, q-1 2 , q-5 4 , q-1

4 . G -1 ∞ +1 ∞ -1 G +1 v +1 u +1 v -1 u -1 Fig. 4. The 2-edge-colored graph T r(G).
We define the 2-edge-colored Paley graph SP q = (K q , s) as the complete graph on q vertices such that V (SP q ) = F q and s(uv) = sq(uv). That is, SP q is obtained from the Paley graph P q by replacing non-edges by negative edges. Figure 3 represents the 2-edge-colored Paley graph SP 5 .

An anti-automorphism of a 2-edge-colored graph (G, s) is a permutation ρ of V (G) such that for every edge uv, ρ(u)ρ(v) is an edge and s(ρ(u)ρ(v)) = -s(uv). Then (G) is anti-automorphic if it admits an anti-automorphism.

Since P q is vertex-transitive, arc-transitive, and self-complementary, SP q is vertex-transitive, arc-transitive, and anti-automorphic.

The 2-edge-colored Tromp Paley graph T r(SP q )

Given an oriented graph -→ G , Tromp [14] proposed a construction of an oriented graph T r(G) called the Tromp graph. We adapt this construction to 2-edgecolored graphs as follows.

Given a 2-edge-colored graph (G), we denote by (G • ) the graph obtained from (G) by adding a universal vertex, denoted by ∞, that is positively linked to all the vertices of (G).

The Tromp 2-edge-colored graph T r(G) of (G) is then defined as the 2-edgecolored graph AT (G • ). By construction, T r(G) is obtained from two copies (G +1 ) and (G -1 ) of (G) and the vertices ∞ +1 and ∞ -1 (see Figure 4).

Given a 2-edge-colored graph (G, s), let T r(G) be the Tromp graph of (G) with signature s . Let u i v j ∈ T r(G) such that u = ∞. If v = ∞, then s (u i v j ) = i × j × s(uv).
(

) Otherwise s (u i ∞ j ) = i × j. 2
Lemma 6 If (G) is anti-automorphic, then AT (G) and T r(G) are anti-automorphic.

Proof. Let s be the signature of G and s be the signature of T r(G). Let ρ be an anti-automorphism of (G). We define the mapping γ : V (T r(G)) → V (T r(G)) as:

γ : u i →      ∞ -i if u = ∞ (ρ(u)) i if u = ∞
Let us check that γ maps every edge u i v j ∈ E(T r(G)) to an edge of opposite sign. If u, v = ∞, then γ maps u i v j to ρ(u) i ρ(v) j and we have by [START_REF] Borodin | On acyclic colorings of planar graphs[END_REF]:

s (ρ(u) i ρ(v) j ) = i × j × s(ρ(u)ρ(v)) = i × j × (-s(uv)) = -s (u i v j ). If u = ∞ and v = ∞, then γ maps u i ∞ j to ρ(u) i ∞ -j
and we have by (3):

s (ρ(u) i ∞ -j ) = i × (-j) = -(i × j) = -s (u i ∞ j ).
Since the restriction of γ to V (AT (G)) is well-defined, the same proof applies to AT (G). 2

In the remainder of this section, we focus on the Tromp Paley graph T r(SP q ) obtained by applying the Tromp construction to the 2-edge-colored Paley graph SP q . It has 2q + 2 vertices denoted u i such that u ∈ {0, 1 = g 0 , g, g 2 , . . . , g q-2 , ∞} and i ∈ {-1, +1} (recall that g is a generator of the multiplicative group F * q ). We denote by s the signature of SP q and by s the signature of T r(SP q ). Note that if

u i v j ∈ T r(SP q ), u = ∞, and v = ∞, then s (u i v j ) = i × j × sq(u -v) by (2) since s(uv) = sq(u -v).
The graph T r(SP q ) has remarkable symmetries and some useful properties given below.

Lemma 7

The 2-edge-colored graph T r(SP q ) is vertex-transitive.

Proof. To prove that T r(SP q ) is vertex-transitive, we show that every vertex u can be mapped to ∞ +1 . Recall that SP q is vertex-transitive and arctransitive. Moreover, for every vertex w i ∈ V (T r(SP q )), either w = ∞, w = 0, or w = g t for some t.

If ϕ is an automorphism of SP q , we define the corresponding automorphism γ ϕ of T r(SP q ) as:

γ ϕ : u i →      u i if u = ∞ (ϕ(u)) i if u = ∞
We also define the mapping γ ∞ : V (T r(SP q )) → V (T r(SP q )) as:

γ ∞ : u i →              ∞ i if u = 0 0 i if u = ∞ g -t i×(-1) t if u = g t
Let us check that γ ∞ is an automorphism of T r(SP q ), i.e., that for every edge

u i v j , we have γ ∞ (u i )γ ∞ (v j ) ∈ E(T r(SP q )) and s (γ ∞ (u i )γ ∞ (v j )) = s (u i v j ).
• If u = g t and v = g r , we have

s (γ ∞ (u i )γ ∞ (v j )) = s g -t i×(-1) t g -r j×(-1) r = i × (-1) t × j × (-1) r × sq g -t -g -r by (2) = i × j × sq g t+r × sq g -t -g -r by (1) = i × j × sq g t+r g -t -g -r = i × j × sq g r -g t = i × j × sq g t -g r = s (g t i g r j ) by (2) = s (u i v j ). • If u = g t and v = 0, we have s (γ ∞ (u i )γ ∞ (v j )) = s (g -t i×(-1) t ∞ j ) = i × (-1) t × j by (3) = i × j × sq(g t ) by (1) = i × j × sq(g t -0) = s (g t i 0 j ) by (2) = s (u i v j ). • If u = g t and v = ∞, we have s (γ ∞ (u i )γ ∞ (v j )) = s (g -t i×(-1) t 0 j ) = i × (-1) t × j × sq(g -t -0) by (2) = i × (-1) t × j × (-1) -t by (1) = i × j = s (g t i ∞ j ) by (3) = s (u i v j ). • If u = 0 and v = ∞, we have s (γ ∞ (u i )γ ∞ (v j )) = s (∞ i 0 j ) = i × j by (3) = s (0 i ∞ j ) by (3) = s (u i v j ).
Given a vertex u ∈ SP q , the automorphism ϕ can be chosen so that ϕ(u) = 0. Then, we have γ ϕ (u i ) = 0 i for every u = ∞. Also, γ ∞ (0 i ) = ∞ i and atw(∞ -1 ) = ∞ +1 . Thus, we can map every vertex of T r(SP q ) to ∞ +1 by combining the automorphisms γ ϕ , γ ∞ , and atw. So T r(SP q ) is vertex-transitive. 2 Lemma 8 T r(SP q ) is triangle-transitive.

Proof. There are 4 types of triangles (a, b, c) according to the number of positive edges in their signature. Without loss of generality, the edges incident to c have the same sign β and we denote by α the sign of ab. Thus, every type of triangle is characterized by a couple (α, β) ∈ {-1, +1} 2 . We have to prove that for every two triangles of the same type, there exists an automorphism of T r(SP q ) that maps one triangle to the other.

We first prove that every triangle (a, b, c) of type (+1, β) maps to the triangle 0 +1 1 +1 ∞ β . By Lemma 7, T r(SP q ) is vertex-transitive, so there exists an automorphism ϕ that maps c to ∞ β . Every edge of sign β incident to ∞ β has its other extremity in SP +1 q . Thus, ϕ maps the edge ab to a positive edge u +1 v +1 in SP +1 q . Since SP q is arc-transitive, we can finally map u +1 v +1 to 0 +1 1 +1 . Let T r(SP q ) be obtained from T r(SP q ) by changing the sign of every edge. Since SP q is anti-automorphic, T r(SP q ) is also anti-automorphic by Lemma 6. So T r(SP q ) is isomorphic to T r(SP q ). Let us fix β ∈ {-1, +1} and let T 1 and T 2 be two triangles of type (-1, β) in T r(SP q ). So T 1 and T 2 are triangles of type (+1, -β) in T r(SP q ). By the previous case, there exists an automorphism that maps T 1 to T 2 in T r(SP q ). This automorphism also maps T 1 to T 2 in T r(SP q ). 2

Coloring properties of target graphs

A sign vector of size k is a k-tuple α = (α 1 , α 2 , . . . , α k ) ∈ {-1, +1} k . The negation of α is the sign vector -α = (-α 1 , -α 2 , . . . , -α k ). Given a sequence of k distinct vertices

X k = (v 1 , v 2 , . . . , v k ) of a 2-edge-colored graph (G, s) that induces a clique in G, an α-neighbor of X k is a vertex u ∈ V (G) such that s(v i u) = α i for 1 i k. The set of α-neighbors of X k is denoted by N α (X k ).
Thus, the notion of α-neighbor generalizes to sequences of vertices the notions of positive and negative neighbors of a vertex.

Consider the 2-edge-colored graph SP 5 depicted in Figure 3. For example, given α = (+1, -1) and X = (0, 3), the vertex 1 is an α-neighbor of X, the vertex 2 is a (-α)-neighbor of X, we have N α (X) = {1} and N -α (X) = {2}.

A 2-edge-colored graph (G) has property P k,l if |N α (X k )| l for every sequence X k of k distinct vertices inducing a clique in G and for every sign vector α of size k.

Lemma 9 If SP q has property P n-1,k , then T r(SP q ) has property P n,k .

Proof. Suppose that SP q has property P n-1,k and let α = (α 1 , . . . , α n-1 , α n ) be a given sign vector. Let X = (x 1 , . . . , x n-1 , x n ) be a sequence of n distinct vertices inducing a clique of T r(SP q ). We have to prove that X admits k αneighbors. By Lemma 7, T r(SP q ) is vertex-transitive and we assume without loss of generality that x n = ∞ +1 . By noticing that N -α (X) = atw(N α (X)), we also assume without loss of generality that α n = +1. Since X is a clique, we have

x i / ∈ {∞ +1 , ∞ -1 } for 1 i n -1. We define Y = (y 1 , . . . , y n-1 ) such that y i = x i if x i ∈ SP +1 q and y i = atw(x i ) if x i ∈ SP -1
q . Hence, the vertices in Y belong to SP +1 q . We define β = (β 1 , . . . , β n-1 ) such that, for

1 i n -1, β i = α i if and only if x i = y i . By Property P n-1,k of SP q , there exist k β-neighbors v 1 , v 2 , . . . , v k of Y in SP +1
q . The v i 's are positive neighbors of ∞ +1 , so they are (β 1 , . . . , β n-1 , +1)-neighbors of (y 1 , . . . , y n-1 , ∞ +1 ). Hence X has k α-neighbors.

2

Lemma 10 If (G) is a 2-edge-colored graph and T r(G) has property P n,k , then AT (G) has property P n,k-1 .

Proof. Recall that AT (G) is obtained from two isomorphic copies of (G) and then T r(G) is obtained from AT (G) by adding the anti-twin vertices ∞ +1 and ∞ -1 . Let X be a sequence of n distinct vertices inducing a clique in AT (G). Since T r(G) has property P n,k , we have that N α (X) contains k vertices of T r(G) for every sign vector α of length n. However, N α (X) cannot contain both ∞ +1 and ∞ -1 , since they are anti-twins. So X has at least k -1 α-neighbors in AT (G), which means that AT (G) has property P n,k-1 . 2

Lemma 11

(1) SP q has properties P 1,(q-1)/2 and P 2,(q-5)/4 .

(2) T r(SP q ) has properties P 1,q , P 2,(q-1)/2 , and P 3,(q-5)/4 .

(3) AT (SP q ) has properties P 1,q-1 , P 2,(q-3)/2 , and P 3,max(0,(q-9)/4) .

Proof.

(1) These properties follow from the fact that the 2-edge-colored Paley graph SP q is built from the Paley graph P q which is self-complementary, arctransitive, and strongly regular with parameters q, q-1 2 , q-5 4 , q-1 4 .

(2) T r(SP q ) has property P 1,q since it is vertex-transitive by Lemma 7 and the vertex ∞ +1 has q positive and q negative neighbors. The other properties follow from Lemma 11.(1) and Lemma 9. (3) These properties follow from Lemma 11.(2) and Lemma 10.

3 Results on 2-edge-colored homomorphisms

This section is devoted to 2-edge-colored homomorphisms of planar graphs and outerplanar graphs. Recall that a graph (H) is C-universal if every 2edge-colored graph (G) of the class C admits a 2-edge-colored homomorphism to (H).

An acyclic k-coloring is a proper vertex-coloring such that every cycle has at least three colors. In other words, the graph induced by every two color classes is a forest. Let A k be the class of graphs that admit a k-acyclic coloring.

In 1998, Alon and Marshall [START_REF] Alon | Homomorphisms of edge-colored graphs and Coxeter groups[END_REF] proved the following (the 2-edge-colored graph SZ k has k • 2 k-1 vertices and has been considered in Section 2.2):

Theorem 12 ([1]) SZ k is A k -universal. Thus χ 2 (A k ) k • 2 k-1 .
Huemer et al. [START_REF] Huemer | Lower bounds for the colored mixed chromatic number of some classes of graphs[END_REF] have shown that Theorem 12 is tight.

The girth of a graph is the length of a shortest cycle. We denote by P g (resp. O g ) the class of planar graphs (resp. outerplanar graphs) with girth at least g. So P 3 is simply the class of planar graphs.

Borodin [START_REF] Borodin | On acyclic colorings of planar graphs[END_REF] proved that every planar graph admits an acyclic 5-coloring. Thus, Alon and Marshall deduced the following from Theorem 12:

Corollary 13 ([1]) SZ 5 is P 3 -universal. Thus χ 2 (P 3 ) 80.
In this same context, Borodin et al. [START_REF] Borodin | Homomorphisms from sparse graphs with large girth[END_REF] and Montejano et al. [START_REF] Montejano | Homomorphisms of 2-edge-colored graphs[END_REF] obtained the following results: Theorem 14 ( [START_REF] Borodin | Homomorphisms from sparse graphs with large girth[END_REF][START_REF] Montejano | Homomorphisms of 2-edge-colored graphs[END_REF])

(1) T r(SP 9 ) is P 5 -universal. Thus χ 2 (P 5 ) 20 [START_REF] Montejano | Homomorphisms of 2-edge-colored graphs[END_REF].

(2) T r(SP 5 ) is P 6 -universal. Thus χ 2 (P 6 ) 12 [START_REF] Montejano | Homomorphisms of 2-edge-colored graphs[END_REF].

(3) SP 9 \ {0} is P 8 -universal. Thus χ 2 (P 8 ) 8 [START_REF] Montejano | Homomorphisms of 2-edge-colored graphs[END_REF]. (4) SP 5 is P 13 -universal. Thus χ 2 (P 13 ) 5 [START_REF] Borodin | Homomorphisms from sparse graphs with large girth[END_REF].

In this section, we obtain anti-twinned target graphs for triangle-free outerplanar graphs (Theorem 15) and triangle-free planar graphs (Theorem 16). The latter result gives a new upper bound on the 2-edge-colored chromatic number. Then, we give properties that must be satisfied by the target graphs for outerplanar graphs (Theorem 18) and planar graphs (Theorem 19). Finally, we obtain new lower bounds on the 2-edge-colored chromatic number of triangle-free planar graphs (Theorem 20) and planar graphs with girth at least 7 (Theorem 21).

Theorem 15 AT (SP 5 \ {0}) is O 4 -universal.
Proof. Assume by contradiction that (H) is a counterexample to the result such that H is minimal with respect to the number of vertices.

Suppose that H contains a 1-vertex u. By minimality of H, the graph (H ) = (H \ {u}) admits a 2-edge-colored homomorphism to AT (SP 5 \ {0}). Since every vertex of AT (SP 5 \ {0}) is incident to a positive and a negative edge, we can extend the 2-edge-colored homomorphism to (H), a contradiction.

Suppose that H contains two adjacent 2-vertices u and v. By minimality of H, the graph (H ) = (H \ {u, v}) admits a 2-edge-colored homomorphism to AT (SP 5 \ {0}). We have checked that for every pair of (non necessarily distinct) vertices x and y of AT (SP 5 \ {0}), the 8 possible 2-edge-colored 3paths exist. Therefore, we can extend the 2-edge-colored homomorphism to (H), a contradiction. Pinlou and Sopena [START_REF] Pinlou | Oriented vertex and arc colorings of outerplanar graphs[END_REF] have shown that every outerplanar graph with girth at least k and minimum degree at least 2 contains a face of length l k

2 ≤ k ≤ 49 v ′ 1 v ′ k v v k v 1 (a) C2 v ′ k v 1 v k v v 2 v ′ 2 2 ≤ k ≤ 24 (b) C3 3 ≤ k ≤ 12 v ′ k v 1 v v k v 3 v 2 v ′ 3 (c) C4 Fig. 5. Configurations C2-C4.
Proof of configuration C1: Trivial.

Proof of configuration C2: Suppose that H contains the configuration depicted in Figure 5(a) and f is a 2-edge-colored homomorphism of (H ) = (H) \ {v, v 1 , . . . , v k } to AT (SP 25 ). For every i, if the edges vv i and v i v i have the same sign (resp. different signs), then v must get a color distinct from atw(f (v i )) (resp. f (v i )). So, each v i forbids at most one color for v. Thus there remains an available color for v. Then we extend f to the vertices v i using property

P 2,11 if f (v i ) = f (v) of or P 1,24 if f (v i ) = f (v).
Proof of configuration C3: Suppose that H contains the configuration depicted in Figure 5(b) and f is a 2-edge-colored homomorphism of (H ) = (H) \ {v, v 2 , . . . , v k } to AT (SP 25 ). As shown in the proof of Configuration C2, each v i forbids at most one color for v. So, we have at most 23 forbidden colors for v and by property P 1,24 , there remains at least one available color for v.

Then we extend f to the vertices v i (2 i k) using property P 2,11 .

Proof of configuration C4: Suppose that H contains the configuration depicted in Figure 5(c) and f is a 2-edge-colored homomorphism of (H ) = (H) \ {v 3 , . . . , v k } to AT (SP 25 ). As shown in the proof of Configuration C2, each v i forbids at most one color for v. So, we have at most 10 forbidden colors for v and by property P 2,11 applied to f (v 1 ), f (v 2 ) this remains at least one available color in order to recolor v. Then we extend f to the vertices v i (3 i k) using property P 2,11 .

Proof of configuration C5: Suppose that H contains the configuration depicted in Figure 6(a). Let (H ) be the graph obtained from (H) by deleting the vertex v and by adding, for every 1 i < j 3, a new vertex v ij and the edges v i v ij and v ij v j . Each of the 6 edges v i v ij gets the sign α i of the edge v i v in (H). Since configuration C4 is forbidden in H, v 1 , v 2 and v 3 are 3-vertices. We have H ≺ H since n 3 (H ) < n 3 (H). Clearly, H is triangle free. Hence, there exists a 2-edge-colored homomorphism f of (H ) to AT (SP 25 ). By P 3,4 , we can find an α-neighbor u of (f

(v 1 ), f (v 2 ), f (v 3 )) in AT (SP 25 ) with α = (α 1 , α 2 , α 3 ). Now fix f (v) = u. Note that f restricted to V (H) is a homomorphism of (H) to AT (SP 25 ).
Proof of configuration C6: Suppose that H contains the configuration depicted in Figure 6(b) and f is a 2-edge-colored homomorphism of (H ) = (H) \ {v 4 , . . . , v k } to AT (SP 25 ). As shown in the proof of Configuration C2, each v i forbids at most one color for v. So, we have at most 3 forbidden colors for v and by property P 3,4 applied to f (v 1 ), f (v 2 ), f (v 3 ), there remains at least

v v 1 v 3 v 2 (a) C5 v 1 v 2 v 3 v v 4 v ′ 4 4 ≤ k ≤ 6 v k v ′ k (b) C6 v 1 w u v 2 (c) C7 w 1 u 1 u 2 u 3 b d a c c 2 w 3 w 2 c 1 v 1 v k-4 a 1 a 2 b 1 b 2 4 ≤ k ≤ 9 (d) C8
Fig. 6. Configurations C5-C8.

one available color for v. Then we extend f to the vertices v i (4 i k) using property P 2,11 .

Proof of configuration C7: Suppose that H contains the configuration depicted in Figure 6(c).

If u and w have no common neighbor other than v 1 and v 2 , then we consider the graph (H ) obtained from (H) \ {v 1 , v 2 } by adding the positive edge uw.

If u and w have at least one other common neighbor v 3 , then consider the graph (H ) obtained from (H) \ {v 1 , v 2 } by adding a vertex v adjacent to u and w such that uv is negative and the sign of vw is the product of the signs of uv 3 and v 3 w. Therefore, we have at least two 2-paths linking u and w, one whose both edges have the same sign and one whose edges have different signs.

In both cases, H is triangle-free, planar, and is a minor of H, so that (H ) admits a 2-edge-colored homomorphism f to AT (SP 25 ). Also, in both cases, f (u) and f (w) form an edge in AT (SP 25 ) since f (u) = f (w) and f (u) = f (atw(w)). Thus, the coloring of (H) \ {v 1 , v 2 } induced by f can be extended to (H) using property P 2,11 .

Proof of configuration C8: Suppose that H contains the configuration depicted in Figure 6(d). By Corollary 4, (H) admits a 2-edge-colored homomorphism to AT (SP 25 ) if and only if every 2-edge colored graph that is switching equivalent to (H) admits a 2-edge-colored homomorphism to AT (SP 25 ). So, by switching a subset of vertices in {a, b, c, c 1 , c 2 }, we can assume that the edges da, ab, bc, cc 1 , and cc 2 are positive. Consider a 2-edge-colored homomorphism f of (H ) = (H \ {d}) to AT (SP 25 ). The edge dc in (H) has to be negative, since otherwise f would be extendable to (H) by setting f (d) = f (b). Also, we must have f (c) = f (a), since otherwise we could color d using property P 2,11 . In the remainder of the proof, we show that we can modify f such that f (c) = f (a). For 1 i 3, let k i denote the color that is forbidden for c by w i , that is, k i = f (w i ) if the edges of the 2-path linking c and w i have distinct signs and k i = atw(f (w i )) otherwise.

First, we rule out the cases in which f (c 1 ), f (c 2 ), and f (b) have at least 5 common positive neighbors, since this allows to choose for c a color that is

(0 +1 , 1 +1 , 2 +1 ) 3 +1 , 4 +1 , (1 + 2 √ 2) -1 , (1 + 3 √ 2) -1 (0 +1 , 1 +1 , 3 +1 ) 2 +1 , 4 +1 , (3 + √ 2) -1 , (3 + 4 √ 2) -1 (0 +1 , 1 +1 , 4 +1 ) 2 +1 , 3 +1 , (2 √ 2) -1 , (3 √ 2) -1 (0 +1 , 1 +1 , (3 + 2 √ 2) +1 ) (3 + √ 2) -1 , (3 √ 2) -1 , (1 + 3 √ 2) -1 , (3 + 4 √ 2) -1 (0 +1 , 1 +1 , (3 + 3 √ 2) +1 ) (3 + √ 2) -1 , (2 √ 2) -1 , (1 + 2 √ 2) -1 , (3 + 4 √ 2) -1
Tab. 7. Sets of the form (0 +1 , 1 +1 , β +1 ) having exactly 4 (+1, +1, +1)-neighbors in AT (SP 25 ).

not in {k 1 , k 2 , k 3 , f (a)}. If f (c 1 ), f (c 2 )
, and f (b) are not pairwise distinct, then they have at least 11 common positive neighbors by property P 2,11 . So we assume that f (c 1 ), f (c 2 ), and f (b) are distinct. We define the sequence X = (f (c 1 ), f (c 2 ), f (b)) and the sign vector α = (+1, +1, +1). Recall that AT (SP 25 ) contains two copies SP +1 25 and SP -1 25 of SP 25 . We consider the graph T r(SP 25 ) obtained by adding the anti-twin vertices ∞ +1 and ∞ -1 to AT (SP 25 ). Using the triangle-transitivity of T r(SP 25 ), a quick computer check shows that X has 5 α-neighbors in T r(SP 25 ) if X induces a triangle with three positive edges and X has 6 α-neighbors otherwise. Notice that ∞ +1 and ∞ -1 cannot be both α-neighbors of X. Thus, if X does not induce three positive edges, then X has at least 5 α-neighbors in AT (SP 25 ). Also, if X is not contained in one copy of SP 25 of the subgraph AT (SP 25 ), then neither ∞ +1 nor ∞ -1 is an α-neighbor of X and thus X has at least 5 α-neighbors in AT (SP 25 ). So X is contained in one copy of SP 25 , say SP +1 25 . We represent the field F 25 by the numbers x+y √ 2, where x and y are integers modulo 5. Without loss of generality, we can assume that f (c 1 ) = 0 +1 and f (c 2 ) = 1 +1 since f (c 1 )f (c 2 ) is a positive edge and SP 25 is arc-transitive. Moreover, X induces three positive edges, so f (b) = β +1 where β is in the set B of positive neighbors of 0 and 1 in SP 25 . We thus have β ∈ B = 2, 3, 4, 3 + 2 √ 2, 3 + 3 √ 2 . Table 7 gives the suitable sequences and their 4 α-neighbors in AT (SP 25 ).

We are now ready to modify f . We decolor the vertices a, b, and c. By property P 2,11 , there exist at least two colors for b that are distinct from the colors forbidden by the k vertices v 1 , . . . , v k-4 , a 1 , a 2 , c 1 , c 2 . By previous discussions, these two colors are β +1 and β +1 with {β, β } ⊂ B. Let us first set f (b) = β +1 . By property P 3,4 , we can color a such that f (a) is distinct from the colors forbidden by u 1 , u 2 , and u 3 . Since f is not extendable to c and d, the 4 αneighbors of (0 +1 , 1 +1 , β +1 ) are k 1 , k 2 , k 3 , and f (a). In particular, k 1 , k 2 , and k 3 are α-neighbors of (0 +1 , 1 +1 , β +1 ). Now we set f (b) = β +1 and obtain that k 1 , k 2 , and k 3 are α-neighbors of (0 +1 , 1 +1 , β +1 ) as well. This is a contradiction, since no two distinct sequences in Table 7 have three common α-neighbors.

2

Proof of Theorem 16. Let (H) be a counterexample which is minimal with respect to . By Lemma 17, H does not contain any of the configurations C1 to C8. There remains to show that every triangle-free planar graph contains at least one of these configurations. This has been already done using a discharging procedure in the proof of Theorem 2 in [START_REF] Ochem | Oriented coloring of triangle-free planar graphs and 2-outerplanar graphs[END_REF], where slightly weaker configurations were used.

2

Montejano et al. [START_REF] Montejano | Homomorphisms of 2-edge-colored graphs[END_REF] proved that SP 9 is O 3 -universal, that gives χ 2 (G) 9 whenever G is an outerplanar graph. They also proved that this bound is tight (i.e. there does not exist O 3 -universal graph on 8 vertices). We prove here that SP 9 is the only universal target graph on 9 vertices.

Theorem 18 The only O 3 -universal graph of order 9 is SP 9 .

Proof. We say that a 2-edge-colored path or cycle is alternating if it has an even number of edges and if every two consecutive edges have different signs. Let (P ) be the alternating 6-path. Note that χ 2 (P ) = 4. Moreover, if (P ) maps to a graph T 4 with 4 vertices, then T 4 contains an alternating 4-cycle as a subgraph. Let (H) be the outerplanar graph consisting in a universal vertex u positively (resp. negatively) linked to every vertex of a copy (P p ) (resp. (P n )) of (P ). So |V (H)| = 15. Every 2-edge-colored coloring of (H) uses at least 4 colors for the vertices of (P p ), at least 4 other colors for the vertices of (P n ), and an additional color for u. Therefore χ 2 (H) = 9.

Let (G) be the outerplanar graph obtained from 16 copies (H 0 ), (H 1 ), . . . , (H 15 ) of (H) as follows: we identify each of the 15 vertices of (H 0 ) the vertex u of a copy (H i ). Consider a graph (T 9 ) with 9 vertices such that (G) maps to (T 9 ). In every 2-edge-colored homomorphism of (G) to (H 9 ), each of the nine colors appears on a vertex of (H 0 ). Since a copy of (H) is attached to every vertex of (H 0 ), every vertex c of (H 9 ) satisfies |N + (c)| = |N -(c)| = 4. Then, by previous discussions, we also have that both N + (c) and N -(c) contain an alternating 4-cycle.

Meringer [START_REF] Meringer | Fast generation of regular graphs and construction of cages[END_REF] provides an efficient algorithm to generate regular graphs with a given number of vertices and vertex degree. In particular, there exist 16 4-regular graphs on 9 vertices (see Figure 8). By replacing edges by positive edges and non-edges by negative edges, we obtain the 16 2-edge-colored graphs such that every vertex has 4 positive and 4 negative neighbors. Then we can check that SP 9 (corresponding to Figure 8(n)) is the only graph among these 16 graphs such that there is an alternating C 4 in both the positive and the negative neighborhood of every vertex.

2

Concerning planar graphs, we have that χ 2 (P 3 ) 20 [8, Corollary 9]. The following result is similar to Theorem 18 for planar graphs:

Theorem 19 If there exists an anti-twinned P 3 -universal graph (H 20 ) of order 20, then (H 20 ) is isomorphic to T r(SP 9 ).

Proof. Let (G) be the outerplanar graph considered in the proof of Theorem 18. Then the planar graph (G • ) maps to (H 20 ) and the subgraph (G) of

(a) (b) (c) (d) (e) (f) (g) (h) (i) (j) (k) ( ) (m) (n) (o) (p)
Concerning triangle-free planar graphs, we obtain a new lower bound:

Theorem 20 There does not exist a P 4 -universal graph of order 11. Thus χ 2 (P 4 ) 12. Proof. A vertex u in a 2-edge-colored graph is good if u is contained in a positive cycle of odd length, in a negative cycle of odd length, and in a 4-cycle upvn such that pu and pv are positive and nu and nv are negative (these cycle are not necessarily induced). We have checked, both by hand and by computer, that:

(i) no graph with at most 5 vertices contains a good vertex, (ii) no graph with 6 vertices contains 6 good vertices.

We consider the plane graph (G) ∈ P 4 depicted in Figure 9. If (G) admits a 2-edge-colored homomorphism h to a graph (H) such that the outerface of (G) maps to a subgraph (H ) of (H), then h(c) is good in (H ). We construct the plane graph (G ) ∈ P 4 from 10 copies (G 0 ), (G 1 ), . . . , (G 9 ) of (G) by identifying the vertex c of (G i ) with the vertex x i of (G 0 ), for 1 i 9. The embedding of (G ) is such that the x j 's of each of the 10 copies are on the outerface.

Suppose for contradiction that there exists a 2-edge-colored homomorphism of (G ) to a graph (H) such that the outerface of (G ) maps to a subgraph (H ) of (H) such that (H ) has at most 6 vertices. Since (G ) contains (G) as a subgraph, (H ) contains a good vertex. So (H ) contains exactly 6 vertices by (i). Moreover, every vertex on the outerface of (G 0 ) corresponds to the vertex c of some copy (G i ) of (G). Thus, all the 6 vertices of (H ) must be good. This contradicts (ii). Therefore, if the graph (G ) maps to some graph (H), then its outerface maps to some subgraph (H ) of (H) of order at least 7. Now, we finish the proof. In a 2-edge-colored graph, two distinct vertices u and v are friends if |N α (u, v)| 2 for every α ∈ {-1, +1} 2 . Notice that for every homomorphism h of the graph (F ) depicted in Figure 10, the vertices h(t) and h(b) must be friends in the target graph. Consider a 2-edge-colored graph (J) ∈ P 4 such that χ 2 (J) = χ 2 (P 4 ). We construct (J ) by adding to every vertex u of (J) a copy of (G ) and by connecting u to every vertex on the outerface of this copy of (G ) using a copy of (F ). So, if χ 2 (P 4 ) = k, then (J ) must map to a 2-edge-colored clique with k vertices such that every vertex has at least 7 friends. We have checked by computer that no 2-edge-colored clique with at most 11 vertices is such that every vertex has at least 7 friends. 2

Finally, concerning planar graphs with girth at least 7, the following theorem gives a new lower bound: Theorem 21 There does not exist a P 7 -universal graph of order 7. Thus χ 2 (P 7 ) 8.

Proof. Consider a 2-edge-colored graph (J) such that J ∈ P 7 and χ 2 (J) = χ 2 (P 7 ). We construct (J ) from (J) as follows. For every vertex u in (J) and for every pair (s c , s p ) ∈ {-1, +1} 2 , we add a 7-cycle whose edges have sign s c and connect u to every vertex of this 7-cycle using a path with 3 edges of sign s p .

If χ 2 (P 7 ) = k, then (J ) must map to a 2-edge-colored clique with k vertices such that for every vertex u and every s p ∈ {-1, +1}, the graph induced by the vertices reachable by a walk of three edges of sign s p starting from u contains both a positive and a negative cycle of odd length. We have checked by computer that no 2-edge-colored clique with at most 7 vertices satisfies this property. 2 Tab. 11. Bounds on the 2-edge-colored chromatic number of planar graphs.

Corollary 25 If every planar graph admits a switching homomorphism to a graph (H 10 ) of order 10, then (H 10 ) is switching equivalent to SP • 9 . By Theorem 20, there exists a bipartite planar graph (G) such that χ sw (G) 6. Finally, for higher girths, note that χ sw (C 2k ) = 4 for even cycles with exactly one negative edge.

Conclusion

One of our aims was to introduce and study some relevant target graphs for 2-edge-colored homomorphism. We have considered the graph AT (G), the 2edge-colored Zielonka graph SZ k , the 2-edge-colored Paley graph SP q , and the 2-edge-colored Tromp Paley graph T r(SP q ). Theorems 18 and 19 suggest that these target graphs are indeed interesting. Theorem 19 leads to the following question:

Open Problem 26 Is T r(SP 9 ) P 3 -universal ?

This would imply that χ 2 (P 3 ) = 20 and χ sw (P 3 ) = 10. We have checked by computer that every 4-connected planar triangulation with at most 15 vertices admits a homomorphism to T r(SP 9 ). The restriction to 4-connected triangulations (i.e. triangulations without separating triangles) is justified by Lemma 8. For the 2 25 non-equivalent signatures of each of the 6244 4-connected planar triangulations with 15 vertices, our computer check took 150 CPUdays. Checking 4-connected triangulations with more vertices would require too much computing power.

Fig. 1 .

 1 Fig. 1. Two equivalent 2-edge-colored graphs.

Fig. 3 .

 3 Fig. 3. The 2-edge-colored graph SP 5 .

Fig. 8 .

 8 Fig. 8. The 16 connected 4-regular graphs on 9 vertices.

(

  G • ) maps to the positive neighborhood of some vertex v of (H 20 ). Since (H 20 ) is anti-twinned, every vertex has at most 9 positive neighbors. Therefore, by Theorem 18, the positive neighborhood of v is isomorphic to SP 9 . Then the subgraph of (H 20 ) induced by v and its positive neighborhood is SP• 9 . Since SP •9 is a clique of order 10, it does not contain a pair of anti-twin vertices and thus (H 20 ) is isomorphic to AT (SP• 9 ). By the definition of 2-edge-colored Tromp Paley graphs, (H 20 ) is isomorphic to T r(SP 9 ).

2 Fig. 9 .

 29 Fig. 9. The graph (G) of Theorem 20.

Fig. 10 .

 10 Fig. 10. The graph (F ) of Theorem 20.

  2-edge-colored graph H is anti-twinned if and only if every vertex has a unique anti-twin.

	Observation 2 A 2-edge-colored graph H is anti-twinned if and only if H is
	isomorphic to AT (G, s) such that (G, s) is a twin-free 2-edge-colored graph.
	Given a twin-free 2-edge-colored graph (G, s), we denote by atw : V (AT (G, s)) → V (AT (G, s)) the fixed-point-free involution which maps every vertex u i to its
	unique anti-twin, that is atw(u i ) = u -i . Note that atw is an automorphism of
	AT (G, s). By extension, if W = {u, v, . . .} is a subset of V (AT (G, s)), then atw(W ) = {atw(u), atw(v), . . .}.
	Lemma 3 A graph (G, s) admits a switching homomorphism to a twin-free
	graph (H, t) if and only if (G, s) admits a 2-edge-colored homomorphism to
	the anti-twinned graph AT (H, t).
	Proof. Brewster and Graves [4, Theorem 12] obtained a general result on m-
	edge-colored graphs which gives the following in the case m = 2: a graph (G, s)
	admits a switching homomorphism to a graph (H, t) if and only if AT (G, s)
	admits a 2-edge-colored homomorphism to AT (H, t).
	Notice that AT (G, s) admits a 2-edge-colored homomorphism to AT (H, t) if
	and only if (G, s) admits a 2-edge-colored homomorphism to AT (H, t). This
	gives that (G, s) admits a switching homomorphism to a graph (H, t) if and
	only if (G, s) admits a 2-edge-colored homomorphism to AT (H, t).
	Finally, we can conclude by means of Observation 2.
	2
	Corollary 4 If (G, s) admits a 2-edge-colored homomorphism to an anti-
	twinned graph T , then (G, s ) admits a 2-edge-colored homomorphism to T
	for every (G, s ) ∼ (G, s).
	2.2 The 2-edge-colored Zielonka graph SZ k

Table 11

 11 summarizes the current knowledge of lower and upper bounds for the 2-edge-colored chromatic number of planar graphs with given girth.

	Girth	Lower bound Upper bound	Target	References
	g = 3	20	80	SZ 5	[1, 8]
	g = 4	12	50	AT (SP 25 ) Th. 16, Th. 20
	g = 5	8	20	T r(SP 9 )	Th. 21, [8]
	6 g 7	8	12	T r(SP 5 )	Th. 21, [8]
	8 g 12	5	8	SP 9 \ 0	[8]
	g 13	5	5	SP 5	[3]

This work was partially supported by the ANR grant EGOS 12-JS02-002-01 and by the PEPS grant HOGRASI.Submitted to Journal of Graph Theory

with at least (l -2) consecutive 2-vertices. Therefore, H is not a triangle-free outerplanar graph. This contradiction completes the proof.

2

Theorem 16 AT (SP 25 ) is P 4 -universal. Thus χ 2 (P 4 ) 50.

Let n 3 (G) be the number of 3-vertices in the graph G. Let us define the partial order . Given two graphs G 1 and G 2 , we have G 1 ≺ G 2 if and only if one of the following conditions holds:

Note that the partial order is well-defined and is a partial linear extension of the minor poset.

Let (H) be a 2-edge-colored graph that does not admit a homomorphism to the 2-edge-colored graph AT (SP 25 ) and such that its underlying graph H is a triangle-free planar graph which is minimal with respect to . In the following, H is given with its embedding in the plane. A weak 7-vertex u in H is a 7vertex adjacent to four 2-vertices v 1 , . . . , v 4 and three 3-vertices w 1 , w 2 , w 3 such that v 1 , w 1 , v 2 , w 2 , v 3 , w 3 , and v 4 are clockwise consecutive.

Lemma 17

The graph H does not contain the following configurations:

Results on switching homomorphism

The graph classes considered in Theorems 12, 14, 15, and 16 admit a 2-edgecolored homomorphism to an anti-twinned graph. Using Lemma 3, we obtain good upper bounds on χ sw for these classes.

Naserasr et al. [START_REF] Naserasr | Homomorphisms of signed graphs[END_REF] proved the following:

Theorem 22 ( [START_REF] Naserasr | Homomorphisms of signed graphs[END_REF]) Let G be a graph that admits an acyclic k-coloring. We have

By Theorem 12, SZ k is A k -universal. By Proposition 5 and Lemma 3, we get the following new upper bound that improves Theorem 22.

Theorem 23 Let G be a graph that admits an acyclic k-coloring. We have

Recall that Huemer et al. [START_REF] Huemer | Lower bounds for the colored mixed chromatic number of some classes of graphs[END_REF] proved that Theorem 12 is tight, i.e., for every k 0 there does not exist A k -universal graph of order k • 2 k-1 -1. In other words, there exists a graph (G k ) that admits an acyclic k-coloring and such that χ

showing that Theorem 23 is actually tight. We also obtain the following results:

Theorem 24

(1) Every outerplanar graph of girth 4 admits a switching homomorphism to SP 5 \ {0}. Thus, χ sw (O 4 ) 4.

(2) Let (H) be such that SZ 5 = AT (H). Every planar graph admits a switching homomorphism to (H). Thus, χ sw (P 3 ) 40.

(3) Every planar graph of girth 4 admits a switching homomorphism to SP 25 .

Thus, χ sw (P 4 ) 25. (4) Every planar graph of girth 5 admits a switching homomorphism to SP • 9 . Thus, χ sw (P 5 ) 10.

(5) Every planar graph of girth 6 admits a switching homomorphism to SP • 5 . Thus, χ sw (P 6 ) 6.

Proof. Every statement is of the form "every graph in C admits a switching homomorphism to (J)". By Lemma 3, it is equivalent to the statement "every graph in C admits a 2-edge-colored homomorphism to AT (J)".

• Item (1) follows from Theorem 15.

• Item (2) follows from Corollary 13 (i.e., planar graphs map to SZ 5 ) and Proposition 5 (i.e., SZ 5 is anti-twinned). • Item (3) follows from Theorem 16.

• Item (4) follows from Theorem 14(1).

• Item (5) follows from Theorem 14(2).

2

Concerning lower bounds, Naserasr et al. [START_REF] Naserasr | Homomorphisms of signed graphs[END_REF] constructed a planar graph G such that χ sw (G) = 10. This result also follows from χ 2 (P 3 ) 20 in [START_REF] Montejano | Homomorphisms of 2-edge-colored graphs[END_REF] and Lemma 3. Moreover, we obtain the following from Theorem 19 and Lemma 3:


Paulin Sourou Gnambode

Meryem Ould-Rouis
email: meryem.ould@u-pem.fr

Xavier Nicolas

Paolo Orlandi

LES OF HEAT TRANSFER IN PIPE FLOW OF POWER-LAW FLUIDS

Keywords: LES, non-newtonian, power-law fluids, turbulent, pipe flow, heat transfer

Heat transfer of turbulent forced convection of power-law fluids, flowing in a heated horizontal pipe at isoflux conditions, is numerically analyzed by Large Eddy Simulations (LES), with the extended Smagorinsky model, for various power law indices (0.75≤n≤1.2) at different Reynolds and Prandtl numbers (4000≤Re s ≤12000 and 1≤Pr s ≤100) for a nonthermally-dependent fluid, at Pearson number Pn=0. A thermally-dependent fluid is also considered for the case n=0.75, at Re s =4000 and Pr s =1, for different Pearson numbers (0.5≤Pn≤5). To validate the present computations, the LES predictions are compared to the results reported in the open literature for the Nusselt number correlations at Pn=0. The LES predictions also allow a better understanding of the physical mechanisms involved in nonnewtonian thermally-dependent fluid flows: with increasing Pn, the relative viscosity is enhanced towards the pipe center while the friction factor and the Nusselt number are significantly reduced.

Introduction

The turbulent flows of non-newtonian fluids are of importance in the mechanical and engineering fields. They are encountered in a wide range of engineering applications. While the turbulence theory, the mathematical models and the numerical methods are welladvanced for newtonian fluids, those for non-newtonian fluids are not as developed. The development of computational models for non-newtonian fluid flows and heat transfer can help to bridge the gap in the existing literature and can contribute to the development of general theories on the turbulent flows of such fluids.

The Pearson number is a dimensionless number that measures the effect of the temperature change on the effective viscosity or consistency of a non-newtonian fluid. When the Reynolds, Prandtl and Pearson numbers are significantly large, large eddy simulation (LES) provides an effective tool to predict the effect of the flow parameters on the turbulent fields. There are very few investigations employing LES for non-newtonian fluids [START_REF] Ohta | DNS and LES with an extended Smagorinsky model for wall turbulence in non-Newtonian viscous fluids[END_REF][START_REF] Gnambode | Large-Eddy simulation of turbulent pipe flow of power-law fluids[END_REF]. Ohta and Miyashita [START_REF] Ohta | DNS and LES with an extended Smagorinsky model for wall turbulence in non-Newtonian viscous fluids[END_REF] developed a turbulence model that can reproduce DNS results in nonnewtonian fluid flows. They performed LES with a Smagorinsky model, extended according to their DNS results, and showed that it can more accurately predict the velocity of turbulent flows for fluids described by Casson's and power-law models (for flow indices n=0.85 and n=1.15) than the standard Smagorinsky model. Gnambode et al. [START_REF] Gnambode | Large-Eddy simulation of turbulent pipe flow of power-law fluids[END_REF] used this extended Smagorinsky model to predict the turbulent pipe flow of power law fluids, for various flow indices (0.5<n<1.4), different Reynolds numbers (4000<Re s <12000) and Prandtl numbers (1<Pr s <100). Heat transfer in turbulent pipe flow of non-newtonian fluid has been very few studied using Large Eddy Simulations (LES). Some theoretical and experimental works focused on the turbulent heat transfer in pipe flows of non-newtonian fluids for a constant viscosity case. Quaresma and Lima [START_REF] Quaresma | Thermally developing turbulent flow of pseudoplastic fluids within circular tubes[END_REF] performed an analytical study of heat transfer in turbulent forced convection of pseudoplastic fluids in thermally developing pipe flows under isoflux conditions. They focused on the effects of the Reynolds and Prandtl numbers as well as the power law indices on the temperature profiles and the Nusselt numbers along the thermal entry zone and the fully developed regions. They found that Nusselt number increases with increasing Prandtl or Reynolds numbers, while it decreases with increasing the flow index. Gnambode et al. [START_REF] Gnambode | LES des transferts thermoconvectifs dans l'écoulement turbulent d'un fluide d'Ostwald de Waele en conduite cylindrique chauffée. 22 ème Congrès Français de Mécanique[END_REF] conducted LES for power law fluids in heated turbulent pipe flows, with the extended Samgorinsky model, using a constant turbulent Prandtl number. They confirmed the suitability of the employed LES approach for such simulations.

It is important to note that for many industrial processes, large temperature differences occur between the wall and the fluid and its viscosity decreases significantly with increasing temperature. In these situations, the flow characteristics change substantially compared with the constant viscosity case and a constant viscosity assumption leads to wrong estimations of the friction and heat transfer coefficients. Thus, it is useful and interesting to consider the effect of the temperature varying viscosity on the turbulent flow and thermal field. However, very few studies account for the dependent viscosity observed in applications. Experiments on the laminar and turbulent flows of a pseudoplastic fluid (n=0.7) in a pipe subjected to a uniform wall heat flux, with temperature dependent viscosity, have been published by Scirocco et al. [START_REF] Scirocco | Ecoulement Iaminaire et transfert de chaleur pour un fluide pseudo-plastique dans un tube[END_REF]. For the turbulent regime, the established correlations remain valid as long as the generalized definitions of the Reynolds and Prandtl numbers are used. Peixinho [START_REF] Peixinho | Contribution expérimentale à l'étude de la convection thermique en régime laminaire, transitoire et turbulent pour un fluide à seuil en écoulement dans une conduite[END_REF] conducted an experimental investigation related to the laminar, transitional and turbulent flows of various non-newtonian fluids, especially Herschell-Bulkey fluids, to investigate the thermal convection in circular and annular pipes. They analyzed the effect of the thermally dependent viscosity on different quantities and statistics. They reported that the reduction of the consistency near the heated wall induces a radial shift of the fluid particles, from the pipe center towards the wall, due to a high acceleration near the wall and a deceleration in the core region of the pipe. The evolution of the heat transfer coefficient is determined in the different regimes showing the effects of the rheological properties. LES of turbulent flows and heat transfer of thermally dependent power law fluids in a heated pipe were also carried out by Gnambode [START_REF] Gnambode | Simulation des grandes échelles des transferts thermo-convectifs dans les écoulements turbulents d'un fluide non-newtonien en conduite cylindrique[END_REF]. He focused on the effects of various parameters (flow index, Reynolds, Prandtl and Pearson numbers) on the statistics and found a significant reduction of the friction factor and Nusselt number with increasing Pearson number.

The objective of this work is to numerically investigate by LES, with an extended Smagorinsky model implemented in a laboratory code developed during Gnambode's PhD thesis [START_REF] Gnambode | Simulation des grandes échelles des transferts thermo-convectifs dans les écoulements turbulents d'un fluide non-newtonien en conduite cylindrique[END_REF], the turbulent heat transfer in the fully developed pipe flow of an incompressible power law fluid at n=0.75 and Re s =4000. The aim is to gain more insights into such complex fluid flows where the viscosity of the fluid is a function of both the temperature and the shear rate. The paper is organised as follows: section 2 introduces the governing equations and the numerical method. Section 3 presents and discusses the LES predictions. The main conclusions are drawn in section 4.

Material and methods

Governing equations

The present study deals with the fully developed turbulent flow and heat transfer of power law fluids in pipes whose wall is heated at a constant heat flux p ϕ . The filtered nonnewtonian equations are made dimensionless using the centreline axial velocity of the analytical fully developed laminar profile, ( ) ( )

1 n / U 1 n 3 U b cL + + =
, where U b is the average velocity, the pipe radius, R , and the reference temperature,

λ ϕ = / R T p ref
, where λ is the fluid thermal conductivity, as velocity, length and temperature scales respectively. These filtered equations can be expressed as follows:

0 x u i i = ∂ ∂ (1) i ij j i i j 1 n i s j i j i j x x u x u x Re 1 x P x u u t u ∂ τ ∂ +                 ∂ ∂ + ∂ ∂ γ ∂ ∂ + ∂ ∂ - = ∂ ∂ + ∂ ∂ - (2) ( ) k k 2 s s w z j z j x x Pr Re 1 T dz d u T u x t ∂ ∂ Θ ∂ >= < - - Θ ∂ ∂ + ∂ Θ ∂ Θ (3)
where the dimensionless temperature is defined by:

ref w T ) t , z , r , ( T ) z ( T θ - > < = Θ (4)
where w T is the wall temperature and < > is an average in time and periodic directions. The subgrid heat flux tensor T θj is defined and estimated by :

j t j j j x T u u T ∂ ∂ α - = Θ - Θ = Θ (5) where t t t Pr / ν = α
is the thermal diffusivity and t Pr is the turbulent Prandtl number which is constant for a given flow index n. Indeed, preliminary LES simulations carried out with the dynamical model [START_REF] Gnambode | Large-Eddy simulation of turbulent pipe flow of power-law fluids[END_REF][START_REF] Gnambode | Simulation des grandes échelles des transferts thermo-convectifs dans les écoulements turbulents d'un fluide non-newtonien en conduite cylindrique[END_REF] allowed to estimate Pr t : for n=1, Pr t =0.7 and for n=0.75, Pr t =1.5. The Reynolds and Prandtl numbers of the simulations are defined as

0 n n 2 cL s K R U Re - ρ = and 1 n cL 1 n 0 s U R K Pr - - ρα =
respectively ( α being the thermal diffusivity and ρ the density). The apparent viscosity η of the fluid is modeled by a power-law (Ostwald de Waele model) given by

1 n K - γ = η
, where

( ) [ ] b 0 Pn exp K K Θ - Θ = , 0 K is
( ) ij S 2 n s s t f f C ∆ = ν
, where ∆ is the computational filter, C s the model constant, f s the van Driest wall damping function, and f n the correction function for the change in viscosity. Note that when the spatial filter is applied to the Navier-Stokes equations, in non-newtonian viscous fluid flows (with spatially varying viscosity characteristics), additional terms are derived because the stress tensor is a non-linear function of the strain rate tensor. This means that in the current LES study with a standard dynamic model, the additional terms are ignored. Indeed, it has been shown by Ohta and Miyashita [START_REF] Ohta | DNS and LES with an extended Smagorinsky model for wall turbulence in non-Newtonian viscous fluids[END_REF] that these terms are much smaller than the sub-grid scale (sgs) stress. These authors demonstrated this result by comparing the profiles of the sgs stress and of the additional terms estimated from a filtering of the DNS results for power-law fluids. Therefore, in their study, Ohta and Miyashita [START_REF] Ohta | DNS and LES with an extended Smagorinsky model for wall turbulence in non-Newtonian viscous fluids[END_REF] concentrated on a modification of the sgs model for the viscosity characteristics of non-newtonian fluid and ignored the additional terms.

Numerical procedure

The above mathematical model was implemented in a finite difference laboratory code. The governing equations were discretized on a staggered grid in cylindrical coordinates. The numerical integration was performed by a finite difference scheme, second-order accurate in space and time. The time advancement was based on a fractional step method. A thirdorder Runge-Kutta explicit scheme and a Crank-Nicolson implicit scheme were used to evaluate the convective and diffusive terms, respectively. Uniform computational grid and periodic boundary conditions were applied to the circumferential and axial directions. Nonuniform meshes specified by a hyperbolic tangent function were employed in the radial direction. Different grids have been tested for n=0.75 and 1 and predictions were compared to those of the literature. The grid 65 3 was found to provide an accurate prediction of the turbulence statistics, in agreement with the available data of the literature, and to give a good compromise between the required CPU-time and accuracy. Detailed validations for isothermal flows can be found in [START_REF] Gnambode | Large-Eddy simulation of turbulent pipe flow of power-law fluids[END_REF][START_REF] Gnambode | Simulation des grandes échelles des transferts thermo-convectifs dans les écoulements turbulents d'un fluide non-newtonien en conduite cylindrique[END_REF]. The statistics are computed by averaging in the periodic directions and in time.

Results and discussion

It is difficult to validate the present non-isothermal LES predictions because the literature survey indicates that there are few works devoted to turbulent thermal field and heat transfer in non-newtonian fluid flows. First the present LES predictions are validated by comparison to the results of the non-thermally dependent fluid case, for both laminar and turbulent flows, before dealing with the thermally-dependent case which is more complex.

In that aim, we performed simulations of the laminar and turbulent heat transfer of nonthermally dependent pipe flows at Pr s =1, Re s =4000 and various flow indices. Then, we investigated the effects of the Reynolds and Prandtl numbers on the statistics for both shear-thinning and shear-thickening fluids. The reader can find the detailed validations in Gnambode [START_REF] Gnambode | Simulation des grandes échelles des transferts thermo-convectifs dans les écoulements turbulents d'un fluide non-newtonien en conduite cylindrique[END_REF]. We shall present here only some of them: the comparison of the velocity predictions at Pn=0 to the universal laws for n=1 and the comparison of the predicted turbulent friction factor and Nusselt number to the available correlations of literature. Then, in the following sections, main emphasis is placed on the Pearson number effects on the turbulent flow and thermal fields.

Mean velocity and temperature profiles

Our LES results for the mean axial velocity profiles scaled by the friction velocity, and its viscosity near the wall is lower than that for n=1. Consequently, the enhancement of the velocity in the buffer and log regions at Pn=1 is more pronounced for n=0.75 in comparison to the newtonian case. Because the fluid flow is more accelerated for n=0.75 at Pn=1, its temperature T is significantly reduced towards the pipe centre. This is clearly visible in figure 1b where the dimensionless temperature Θ increases towards the core region, for n=0.75 at Pn=1, due to the decrease of T, because the residence time of the fluid particles in the channel is smaller.

> - = Θ - Θ
and the consistency increases: the fluid becomes more rigid. For the shear-thinning fluid, at 0 Pn = , the viscosity near the wall, Fig. 2b, is smaller than that for 1 n = , since ( ) ( )

1 n 75 . 0 n = γ > = γ
in this region, Fig. 2a. The viscosity is enhanced towards the pipe center when increasing Pn , Fig. 2b, due to the shear-thinning property combined with the increasing consistency.

Friction factor and Nusselt number

To validate the present computations, the friction factor and the Nusselt number are compared to the results reported in the literature. They are found to agree fairly well with them. For n=0.75, the predicted friction factor,

) U /( 2 f 2 b w ρ τ =
, are in accuracy ranges of 10%, 11.4% and 20% compared with the correlations by Oswald de Waele and Gomes (Eq.18 in [START_REF] Gomes | Hydraulic, power-law models, calculation method using[END_REF]), Hanks and Ricks [START_REF] Hanks | Transitional and turbulent pipe flow of pseudo-plastic fluids[END_REF] and Dodge and Metzner (Eq.17 in [START_REF] Gomes | Hydraulic, power-law models, calculation method using[END_REF]), respectively, Table 1. These results clearly show that the friction factor decreases for a decreasing n , at a given s Re .

) r / T ( k h ∂ ∂ - =
, is close to the numerical prediction by Quaresma [START_REF] Quaresma | Thermally developing turbulent flow of pseudoplastic fluids within circular tubes[END_REF] within a 0.2% accuracy for Pr s =11 and a 2% accuracy for Pr s =100, Table 2. The agreement is also satisfactory with the correlation by Pinho and Coelho [START_REF] Pinho | Non-newtonian heat transfer. CEFT/DEMec[END_REF]. The Nusselt number deviates however from the correlation by Sandall et al. [START_REF] Sandall | Experiments on turbulent non-newtonian mass transfer in a circular tube[END_REF] within 61% for Pr s =11 and 80% for Pr s =100. We can conclude that this correlation seems not valid for high Prandtl numbers. For n=0.75 and 1, at Re s =4000, a reduction of the friction factor and Nusselt number is observed with increasing Pn, Table 3. This reduction is significant at n=0.75. However note that, at Pn=0, when n decreases, the Nusselt number increases, while it decreases at Pn=1, Table 3. As shown in Fig. 3a, the profiles of the root mean square (rms) of the fluctuating axial velocity, U z ', of the newtonian fluid (n=1) for Pn=0 and Pn=1 are nearly the same: a very small increase of the rms at Pn=1 is observed on a part of the pipe section between r/R=0.2 and r/R=0.9. On the other hand, the rms U z ' of the shear-thinning fluid (n=0.75) for Pn=1 exhibits higher values than for Pn=0, between the pipe axis and r/R=0.9, Fig. 3a. Its profile peak slightly increases and moves far away from the wall with increasing Pn. On the contrary, the rms of the radial and azimuthal velocity fluctuations are much more low for Pn=1 than for Pn=0, Fig. 3b,c. The higher intensity of the rms of U z ' + at Pn=1 is due to the higher value of the velocity U z + in the buffer and log regions, Fig. 1a. In the core region, for Y + >20 (r/R<0.7), Pn has no impact on the value of turbulent kinetic energy (not shown here). Thus, the augmentation of the rms of U z ' at Pn=1 leads to a diminution of the rms of U r ' and U θ ' in this region. The rms of the temperature Θ' + for Pn=1, just like the rms of U z ' + , is enhanced between the pipe axis and r/R=0.9, Fig. 3d. However, the rms of the fluctuating temperature is much lower than the rms of the fluctuating velocities. The peaks of the rms of Θ' + at Pn=0 (for both n=0.75 and n=1) are higher and located closer to the wall than for the case of the thermally dependent fluid (Pn=1). Thus the fluctuations of the temperature are less intense in the vicinity of the wall with increasing Pn.

Conclusions

This study is the first contribution that allows to check the applicability of LES, with an extended Smagorinsky model, to the turbulent flows and heat transfer of thermally dependent power-law fluids in pipes. The LES results allowed to gain more insight into these complex fluid flows with shear rate and temperature dependent viscosity. In the present LES of fully developed turbulent flow of power law fluids in heated pipes, under isoflux conditions, the Pearson number effects on flow and thermal fields have been revealed. For the non-thermally dependent viscosity case (Pn=0), the LES axial velocity profile for the shear-thinning and newtonian fluids, as well as the friction factor and Nusselt number, are in reasonably good agreement with the findings of the literature. With increasing Pn (thermally dependent viscosity case), the mean viscosity is enhanced towards the pipe center. This leads to a diminution of the turbulent radial heat flux and an acceleration of the flow in the log-region where the temperature is slightly reduced. As a consequence, the friction factor and the Nusselt number undergo a significant reduction when Pn increases. With increasing Pn, the rms of U z ' + and Θ' + are almost the same for the newtonian fluid (n=1) but they are noticeably enhanced between the pipe center and r/R=0.9 for the shear thinning fluid (n=0.75).

  the wall shear stress, are plotted in figure1a versus the distance to the wall η is the mean wall viscosity. With increasing the Pearson number, Pn, the fluid flow is accelerated in the log-region, Fig.1a. Indeed, the viscosity for the newtonian fluid (n=1) is equal to the consistency, wall. This means that the viscosity η is smaller near the wall at 0 Pn ≠ , leading to a faster flow in the buffer and log regions, Fig.1a. For the shear-thinning fluid (n=0.75), the viscosity is equal to

Figure 1a . 3 . 2

 1a32 Figure 1a. Axial mean velacity profile, s Pr =1 Figure 1b. Mean temperature profile, s Pr =1 3.2 Mean normalized viscosity The distribution of the shear rate versus the radial coordinate is depicted in figure 2a. It clearly exhibits a smaller shear rate in the core region of the pipe and a higher one near the wall. The shear rate near the wall is higher for 75 . 0 n = . The variation of the mean viscosity is plotted in figure 2b to give further insights into the flow field. For the newtonian fluid, the viscosity is constant when Pn=0 because 0 K = η . For a given n, figure 2b clearly displays a higher viscosity towards duct center with increasing Pn, especially for n=0.75. With increasing Pn, the viscosity increases when approaching the core region of the pipe because 0 T T b b

Figure 2a .

 2a Figure 2a. Shear rate profile, 1 Pr s = Figure 2b. Mean viscosity profile, 1 Pr s = For n=0.7, the present Nusselt number, defined by Nu=hD/k with

Figure 3 . 8 3. 5

 385 Figure 3. Root mean square of the fluctuating velocities and temperature, 1 Pr s = .

Figures 4 .

 4 Figures 4.a,b depict the profiles of turbulent radial and axial heat fluxes. The turbulent axial heat flux, presented in Fig.4b, behaves like the rms of the fluctuating axial velocity, Fig.3a, showing a strong correlation between the fluctuations Θ' and U z '. The turbulent radial heat flux undergoes a noticeable reduction with increasing Pn, because the fluid viscosity grows towards duct center when Pn increases. The Reynolds shear stress profile behaves like the turbulent radial heat flux when Pn varies (not shown here). Its distribution is shifted far from the wall with increasing Pn, and its peak value is noticeably reduced.

Figure 4a .

 4a Figure 4a. Turbulent radial heat flux, s Pr =1 Figure 4b. Turbulent axial heat flux, s Pr =1 3.6 Visualizations To explore the effects of the Pearson number on the flow, the resolved axial velocity fluctuations are presented in Fig. 5. For the newtonian fluid (n=1), with increasing Pn, the turbulent structures are less random and the streaks are larger indicating a less developed turbulence. For the shear-thinning fluid (n=0.75), the number of streaks is reduced compared with the newtonian case and much longer streaks appear, particularly at Pn=1, suggesting a reduction of turbulence and, as a consequence, of the heat transfer. The reduction of turbulence is more pronounced at n=0.75, due the augmentation of the viscosity towards the pipe center, Fig.2b.

Figure 5 .

 5 Figure 5. Resolved axial velocity fluctuations at 15 Y ≈ +

  the consistency at the bulk temperature T b , Pn=bT ref is the Pearson number and b is the parameter of the thermo-dependence.

	γ	=	S	ij S	ij	is the shear rate, with the strain rate tensor	S	ij	=	u (	i	,	j	+	u	j	i ,	)	/	2	.
	2.2. Dynamic eddy viscosity model
	The subgrid stress tensor ij τ is linked to the strain rate tensor ij S by	τ	ij	=	2ν -	t	S	ij	. In the non-
	newtonian Smagorinsky model by Ohta and Miyashita [1], the turbulent viscosity is computed
	by

Table 1 .

 1 Friction

		factor at	1 Pr s = , Pn=0 and	Re s =	4000	.
	n Present LES Dodge and Metzner [9] Oswald de Waele & Gomes [9] Hanks & Ricks [10]
	0.75	9.12×10 -3	7.60×10 -3		8.24×10 -3	8.18×10 -3
	1.0	10.47×10 -3	8.68×10 -3		9.99×10 -3	9.73×10 -3
	1.2	10.94×10 -3	9.45×10 -3		11.27×10 -3	10.81×10 -3

Table 2 .

 2 Nusselt

			number at	1 Pr s = , Pn=0 and	Re s =	4000	.
	n	s Pr	Present LES	Quaresma [3]	Sandall & al. [12]	Pinho & Coelho [11]
	0.7	100	109.69		111.94		60.77	96.43
	0.7	11	45.41		45.30		28.18	45.21
	1.0	1	18.45				24.99	18.30
	1.2	1	17.55				22.48	14.77

Table 3 .

 3 Friction

		factor and Nusselt number at	1 Pr s = and	Re s =	4000	for the present LES.
		n=0.75			n=1
		Pn=0	Pn=1			Pn=0	Pn=1
	f×10 3	9.12	6.99			9.49	9.11
	Nu	20.19	15.07			18.45	17.86


Lei Zhang

Yulin Zhang
email: yulin.zhang@u-picardie.fr

Zheng Fang
email: fangzheng@mail.neu.edu.cn

Xianbo Xiang
email: xbxiang@hust.edu.cn

Marianne Huchard
email: huchard@lirmm.fr

René Zapata
email: zapata@lirmm.fr

Towards An Architecture-Centric Approach to Manage Variability of Cloud Robotics

Cloud robotics is a field of robotics that attempts to invoke Cloud technologies such as Cloud computing, Cloud storage, and other Internet technologies centered around the benefits of converged infrastructure and shared services for robotics. In a few short years, Cloud robotics as a newly emerged field has already received much research and industrial attention. The use of the Cloud for robotics and automation brings some potential benefits largely ameliorating the performance of robotic systems. However, there are also some challenges. First of all, from the viewpoint of architecture, how to model and describe the architectures of Cloud robotic systems? How to manage the variability of Cloud robotic systems? How to maximize the reuse of their architectures? In this paper, we present an architecture approach to easily design and understand Cloud robotic systems and manage their variability.

I. INTRODUCTION

Cloud robotics is a field of robotics that attempts to invoke Cloud technologies such as Cloud computing, Cloud storage, and other Internet technologies centered around the benefits of converged infrastructure and shared services for robotics [START_REF] Kuffner | Cloud-enabled robots[END_REF]. Cloud Robotics was firstly introduced by James Kuffner [START_REF] Kuffner | Cloud-enabled robots[END_REF]. In a few short years, Cloud robotics as a newly emerged field has already received much research and industrial attention.

The use of Cloud computing for robotics and automation brings some potential benefits largely ameliorating the performance of robotic systems. Due to the limited capacities of on-board processing, storage and battery capacities, robotic devices are constrained to numerous limitations. It not only solves the problems of robotic systems, such as on-board computation and storage limitation, asynchronization communication, compatibility problem of multi-robot systems [START_REF] Mohanarajah | Rapyuta: A cloud robotics platform[END_REF], but also makes possibility of different directions or enhances their performance, such as remote brain, big data and shared knowledge-base, collective learning and intelligent behavior [START_REF] Qureshi | Five traits of performance enhancement using cloud robotics: A survey[END_REF].

However, beyond these advantages, Cloud robotics also brings us many challenges. For example, from the view of architectures, how to construct the architectures of Cloud robotic systems? How to model these architectures? How to deploy these architectures in Clouds? How to reuse these architectures? How to manage the variability of these architectures?

In this paper, we propose a domain specific language -CRALA trying to response the above questions. Our main contributions are to propose:

• an architecture-centric design process for Cloud robotic systems, • a domain specific language for architecture-centric Cloud robotic systems named CRALA. The rest of the paper is organized as follows: We begin with an introduction of related concepts, background and related work of Architecture-centric Cloud robotics. We then present an overview of the architecture-centric design process for Cloud robotic systems. Then we describe the metamodel of CRALA with examples and how CRALA manages the variability of Cloud robotic systems. Afterwards, we present the implementation of CRALA. Finally, we finish with a discussion and future work.

II. BACKGROUND AND RELATED WORK A. Related concepts

Architecture-centric Cloud robotics is a methodology of developing robotics systems on Clouds using architecturecentric development techniques.

Cloud computing Cloud computing is defined by the National Institute of Standards and Technology (NIST) as: "Cloud computing as a model for enabling ubiquitous, convenient, on-demand network access to a shared pool of configurable computing resources (e.g., networks, servers, storage, applications, and services) that can be rapidly provisioned and released with minimal management effort or service provider interaction [START_REF] Mell | The nist definition of cloud computing[END_REF]".

Clouds offer services that can be grouped into three categories: software as a service (SaaS), platform as a service (PaaS), and infrastructure as a service (IaaS) [START_REF] Zhang | Cloud computing: state-ofthe-art and research challenges[END_REF].

1) Infrastructure as a Service: IaaS refers to on-demand provisioning of infrastructural resources, usually in terms of VMs (Virtual Machines). The cloud owner who offers IaaS is called an IaaS provider. 2) Platform as a Service: PaaS refers to providing platform layer resources, including operating system support and software development frameworks. 3) Software as a Service: SaaS refers to providing ondemand applications over the Internet.

An explicit architecture of Cloud robotic system should cover these three design services in its architecture.

System/Software architectures. Traditionally, software architecture is a collection of models that capture a software systems principal design decisions in the form of components (foci of system computation and data management), connectors (foci of component interaction), and configurations (specific arrangements of components and connectors intended to solve specific problems) [START_REF] Perry | Foundations for the study of software architecture[END_REF]. Generally speaking, a software system architecture [START_REF] Taylor | Software architecture: foundations, theory, and practice[END_REF] gathers design decisions of the system. As the development of computer science, nowadays, a system is much more complex than before such as with the integration of "Internet of Things", "Cloud Computing" and "Robotics" etc.

Architectures Modeling language. Architecture models are often expressed using ADLs (Architecture Description Language) that, in most cases, provides information on the structure of the software system listing the components/services and connectors that the system is composed of. A system architecture could cover different abstraction levels, such as specification, configuration and assembly [START_REF] Zhang | Architecture-centric component-based development needs a three-level adl[END_REF] and from different viewpoints [START_REF] Clements | Documenting software architectures: views and beyond[END_REF]. For Cloud robotic system, architecture model also needs to capture Cloud and robot design decisions.

B. Related Work

The description of Cloud robotic systems should cover robot description, web services/component description and cloud robotic system global architecture description.

Robot description. Robot description languages provide models of a robot and then design and implemented software components that work on the model components rather than the particular robot instance.

The representative example of robot description language is the Unified Robot Description Format (URDF) [START_REF]Unified robot description format[END_REF], which can be used to specify the kinematics and dynamics, the visual representation and the collision model of a robot. However, URDF is not designed for specifying robot components such as sensors, actuators, and control programs.

COLLADA [START_REF] Diankov | Collada: An open standard for robot file formats[END_REF] is an XML Schema designed for describing 3D objects including their kinematics. It mainly focuses on modeling information about scenes, geometry, physics, animations, and effects. But similar to URDF, it lacks elements for describing sensors, actuators and software. SRDL [START_REF] Kunze | Towards semantic robot description languages[END_REF] focuses on modeling robot components, i.e. sensors, actuators and control programs, especially via capabilities to actions. Many work try to develop an OWL (Web Ontology Language) ontology to describe robots, such as [START_REF] Schlenoff | A robot ontology for urban search and rescue[END_REF], [START_REF] Chatterjee | Robot description ontology and disaster scene description ontology: analysis of necessity and scope in rescue infrastructure context[END_REF] in specific domains or [START_REF] Compton | A survey of the semantic specification of sensors[END_REF], [START_REF] Compton | Reasoning about sensors and compositions[END_REF] focusing on sensor ontology.

Web service description. Web service description in robotics often serves to match the capabilities with robot components, such as PHOSPHORUS [START_REF] Gil | Phosphorus: A task-based agent matchmaker[END_REF], Larks [START_REF] Sycara | Larks: Dynamic matchmaking among heterogeneous software agents in cyberspace[END_REF], OWL-S [START_REF] Martin | Bringing semantics to web services with owl-s[END_REF] and SRDL [START_REF] Kunze | Towards semantic robot description languages[END_REF]. In general, the term capability matchmaking refers to the process of matching an advertisement of a capability with a request.

Cloud Robotic description. All above work cover a part description of Cloud robotic systems, referring to robot description or web service description. However, it misses a language that fully covers all necessary aspects of Cloud robotic architecture, including the description of Clouds, robots and components/web services.

III. ARCHITECTURE DESIGN FOR CLOUD ROBOTICS

The architecture design for Cloud robotic system is different from traditional software design, as it concerns two special aspects: Cloud-based systems and robotic systems. We identify the architecture-centric development process for Cloud robotic systems into three main phases, as shown in Figure 1.

1) Specification design. Architect or robotics engineers should choose a robotic architecture pattern for the system according the models of robots (hardware) and its functional tasks (objective), for example, a pioneer robot with a task of path planning. 2) Configuration design.

• First of all, architect should consider how to distribute intelligence among robots and Cloud. That means, which components should be placed on the robot itself and which services should be placed on Cloud. How to choose the appropriate components or services from component or service repository. This design decision refers to different factors, including robot capacities, system non-functional properties such as real-time, security etc. • Secondly, architect should choose operating system for their services, as in robotics domain, there exists some operating systems that are widely used, such as ROS [START_REF]Robot operating system[END_REF]. Then, how to distribute these services in different virtual machines. 3) Assembly deployment. Lastly, how to deploy this architecture model in Clouds, automatically or not? How to reflect and supervise a runtime model to prevent VMs failure etc.? During the process, five factors affect architecture design decisions robot models, tasks, intelligence, non-functional properties, and Clouds, as shown in Figure 2.

• Robot model describes the hardware model of the robots consisting of sensors and actuators etc. • Task is the objective realized by robots.

• Intelligence distribution defines how to distribute the intelligence to robots and Clouds. • Non-functional properties are non-functional requirements required to be exposed by Cloud robotic systems, such as security, realtime, safety etc. • Clouds represent Cloud infrastructures (IaaS) used to deploy robotics services. Clouds can be mono-cloud or multi-Cloud.

IV. CRALA: A DOMAIN SPECIFIC LANGUAGE

CRALA is a domain specific language for architecturecentric Cloud robotics, and it is also an architecture description language. CRALA models architectures at three separate abstraction levels, each designed in a different development phase as shown in Fig. 1. For now, the first version of CRALA presented in this paper mainly focuses on modeling essential elements of architectures and their basic properties, as the design concept of CRALA is to auto-develop and enrich the language by experimentation and real use cases. The three levels are as follows:

1) Specification defines the abstract architecture specification. It defines which functionality should be Clouds. This architecture model exactly depicts the current state of Cloud robotic system on Cloud.

Table I presents the design decisions that should be made in each architecture level.

A. Architecture Specification

Architecture specification is composed by component roles, connections and Concept robots. The metamodel1 of specification is illustrated in Fig. 3(a).

• Component roles describe the roles that components should play in the system. In Cloud robotic systems, a roles could be a function (such as algorithm), a database, or a driver etc. A component role lists the minimum list of interfaces (both required and provided) the component/service (will be selected or implemented in configuration level) should expose. On the one had, as they define the requirements of the architect (its ideal view) to guide the search for corresponding concrete components (or service) in component (or service) repository, component roles are abstract and partial component (or service) representations. On the other hand, they can be used as the design specification for implementing new components or services from scratch. For example in Fig. 3(b), Spec1 defines three component roles to fulfill three different functionalities. • Concept robots define the robots that will be included in the system with certain sensors or actuators to realize the functionalities of the system. At this level, concept robot is totally abstract, and it only defines the types of sensor and actuators. In specification, we do not precise the model of robot used. As shown in Fig. 3(b), Robot1

B. Architecture Configuration

Architecture configurations are the second level of system architecture descriptions. They result from the search and selection of real component classes (or web services) in a component (or service) repository. The metamodel is shown in Fig. 4.

1) We precise which robots (RobotModel) will be used in configuration. Robot models should expose all sensors and actuators specified in concept robot of Specification. • Component class: A component class often can be characterized as: attributes, component interface, behaviors and properties. • Web service: A more formal and extended definition is the one offered by the W3C Web Services working group [START_REF][END_REF]:A Web service is a software system designed to support interoperable machineto-machine interaction over a network. It has an interface described in a machine-processable format (specifically WSDL). Other systems interact with the Web service in a manner prescribed by its description using SOAP-messages, typically conveyed using HTTP with an XML serialization in conjunction with other Web-related standards. 3) Then, components and services will be placed in robots or virtual machines3 . 4) Lastly, the connections should be established, for example which kind of communication protocols will be used in different situations. We could find the connection between robots and components are not permitted at this level (the same for next assembly level). According to the selection of different component classes and services and the distribution of these components in robots and VMs, it could lead to different configuration architectures, which implement the same specification architecture.

Figure 5(a) and 5(b) represent two different possible configuration architectures of specification Spec1 in Fig. 3(a). In Config1, two services LocalisationService and PathPlan-ningService locate in two separated VMs, and in Config2,

C. System assembly

System assemblies are the third level of system architecture descriptions. At the macroscopic level, They result from the deployment of VMs of configuration in Clouds. At the microscopic level, they result from the instantiation of the component classes and the deployment of the web services from a configuration. The important thing is that they should provide a description of runtime software systems including deployment description. The metamodel of Cloud is illustrated in Fig. 6. Each component or service are defined clearly which VMs or robots they are deployed and each VM is illustrated with which physical machine of which Cloud it is deployed.

System assemblies are the most related level to Cloud.

• Cloud: Different Clouds directly affect the deployment results of configurations.

D. The variability

The variability of software architecture often cites SPL (Software Product Line). In SPL, the variability is inside in configuration level. A reference architecture could be implemented by different possible configurations with certain limit choices. In CRALA, variability is horizontal, which is reflected in the relationships between three levels. We use illustrating examples to explain how CRALA manages the variability of Cloud robotic systems from microscopic and macroscopic views.

Firstly, from macroscopic view, the variability of architectures could be captured by their relationships between different architecture levels, as shown in Fig. 8 (a). Secondly from microscopic view, the variability is reflected by components. Fig. 9 presents an example of com- In our viewpoint, if we could combine these two kinds of variability: horizontal and vertical in our future work, it will greatly increase the feasibility and reusability of CRALA.

V. IMPLEMENTATION

We used the Ecore framework [START_REF] Steinberg | EMF: eclipse modeling framework[END_REF] and Sirius [START_REF] Viyovic | Sirius: A rapid development of dsm graphical editor[END_REF] for CRALA. Ecore allows create a tree editor for a DSL according to its metamodel, as show in Fig. 10. Sirius is an Eclipse project which allows you to easily create your own graphical modeling workbench including generating graph of models or editing graphical models. The models created by CRALA Ecore plugins could be automatically expressed in graphs. In future work, we aim to extend CRALA in several ways. We would like to develop some mechanisms to support the automatically developing process of architecturecentric Cloud robotic systems. First of all, how to search the correspondent and appropriate components or services in repository to construct architecture configuration automatically. Secondly, how to deploy the configuration on Cloud automatically. Then how to reorganize the system on Clouds when service failure. Our overall goal is to construct an intelligent development environment to construct Cloud robotic systems.

Fig. 1 .

 1 Fig. 1. Cloud robotic system architecture design

Fig. 2 .

 2 Fig. 2. Cloud robotic system architecture design

Fig. 3 .

 3 Fig. 3. Architecture specification Metamodel and example

Fig. 4 .

 4 Fig. 4. Architecture Configuration Metamodel

Fig. 5 .

 5 Fig. 5. Architecture Configuration Example Config1 and Config2

Fig. 6 .

 6 Fig. 6. Assembly Metamodel

Fig. 7 .Fig. 8 .

 78 Fig. 7. Assembly Metamodel and examples

  Figure 8(b) illustrates the relationships of example architectures Arch1 presented earlier in this section and it's generated automatically by CRALA toolsuite according to the relationships defined in architecture models (Fig. 3(b), 5(a,b) and 7(a,b)).

Fig. 9 .

 9 Fig. 9. The Localization component role, some possible concrete realizations and some of their instantiations

  Figures 3(b), 5(a,b), 6(a,b) and 8 are graphs generated from CRALA models.

Fig. 10 .

 10 Fig. 10. A sample of CRALA Ecore editor

TABLE I DECISION

 I DECISIONS MADE IN EACH ARCHITECTURE ABSTRACTION Cloud deployment, 2) Running state supplied by robotic systems. All the constituents of this architectural models are abstract and without any consideration of Cloud etc. 2) Configuration defines the sets of component or service implementations (classes) by searching and selecting from the component/service repository and defines how to group services and components in different virtual or physical machines by consideration of system requirements. 3) Assembly depicts how configuration is deployed on

		MODEL
	Architecture	Defined Aspects
	Architecture specification	1) Functionalities of the system, 2)
		system non-functional properties
	Architecture configuration	1) Component/service selection (for
		reuse) or implementation (for from
		scratch), 2) Component/service group,
		and 3) Operating system selection
	System assembly	1)

In this paper, we ignore interfaces aspects and all attributes in metamodel for sake of simplicity.

For sake's simplicity, the details of connection and its constraints are not discussed in this paper.

In the first version of CRALA, we ignore the possibility that besides virtual machines, for web services could also be placed in physical machines directly.

• Physical machine: Normally in one Cloud, clients (tenants) could not see which physical machines locate their VMs. Only administrators could know this kind of information for security. In order to raise the clarity of Cloud, we add this information to assembly level. This could make easier to control Cloud robotic systems.

*This work was supported by the National Natural Science Foundation of China under Grant No. 61300020, the Scientific Research Funds for Introduced Talents of Northeastern University under Grant No. 28720524.