Éric Sopena
email: eric.sopena@labri.fr

Upper oriented chromatic number of undirected graphs and oriented colorings of product graphs

The oriented chromatic number of an oriented graph -→ G is the minimum order of an oriented graph -→ H such that -→ G admits a homomorphism to -→ H . The oriented chromatic number of an undirected graph G is then the greatest oriented chromatic number of its orientations.

In this paper, we introduce the new notion of the upper oriented chromatic number of an undirected graph G, defined as the minimum order of an oriented graph -→ U such that every orientation -→ G of G admits a homomorphism to -→ U . We give some properties of this parameter, derive some general upper bounds on the ordinary and upper oriented chromatic numbers of Cartesian, strong, direct and lexicographic products of graphs, and consider the particular case of products of paths.

Introduction

All the graphs we consider in this paper are simple, with no loops or multiple edges. An oriented graph

-→ G = (V ( -→ G ), E( -→ G )
) is an antisymmetric digraph obtained from an undirected graph G = (V (G), E(G)) having the same set of vertices, V (G) = V ( -→ G ), by giving to each edge {u, v} in E(G) one of its two possible orientations, (u, v) or (v, u).

Such an oriented graph

-→ G is said to be an orientation of G. Let G and H be two undirected graphs. A homomorphim from G to H is a mapping h : V (G) -→ V (H) such that for every edge {u, v} in E(G), {h(u), h(v)} is an edge in H. We write G → H whenever such a homomorphism exists. Homomorphisms of oriented graphs are defined similarly, by using arcs instead of edges.

A proper k-coloring of an undirected graph G is a mapping c : V (G) -→ {1, 2, . . . , k} such that c(u) = c(v) for every edge {u, v} in E(G). Such a coloring can also be viewed as a partition of V (G) into k disjoint independent sets V 1 , . . . , V k . The chromatic number χ(G) of G is then the smallest k for which G admits a proper k-coloring. It is easy to see that χ(G) also corresponds to the smallest k for which G → K k , where K k stands for the complete graph of order k.

An oriented k-coloring of an oriented graph -→ G is a partition of V ( -→ G ) into k disjoint independent sets, such that all arcs linking any two of these sets have the same direction.

Such an oriented coloring is thus a mapping γ : V ( -→ G ) -→ {1, 2, . . . , k} such that γ(u) = γ(v) for every arc (u, v) in E( -→ G ) and γ(u) = γ(x) whenever there exist two arcs (u, v) and (w, x) in E( -→ G ) with γ(v) = γ(w) (v and w are not necessarily distinct). The oriented chromatic number χ o ( -→ G ) of an oriented graph -→ G is then defined as the smallest k for which -→ G admits an oriented k-coloring. As before, χ o ( -→ G ) also corresponds to the smallest order of an oriented graph -→ T for which -→ G → -→ T . If G is an undirected graph, the oriented chromatic number χ o (G) of G is defined as the highest oriented chromatic number of its orientations:

χ o (G) = max χ o ( -→ G ), -→ G is an orientation of G .
Most of the papers devoted to oriented colorings were concerned with upper bounds on the oriented chromatic number of special classes of graphs [START_REF] Aravind | Forbidden subgraph colorings and the oriented chromatic number[END_REF][START_REF] Esperet | Oriented colorings of 2-outerplanar graphs[END_REF][START_REF] Fertin | On the oriented chromatic number of grids[END_REF][START_REF] Kostochka | Acyclic and oriented chromatic numbers of graphs[END_REF][START_REF] Natarajan | Oriented colouring of some graphs[END_REF][START_REF] Ochem | Negative results on acyclic improper colorings[END_REF][START_REF] Raspaud | Good and semi-strong colorings of oriented planar graphs[END_REF][START_REF] Sopena | Oriented graph coloring[END_REF][START_REF] Wood | On the oriented chromatic number of dense graphs[END_REF]. In many cases, such bounds were obtained by proving that every orientation of any graph in a given class admits a homomorphism to some specific oriented graph (sometimes a tournament). This observation motivates the introduction of a new parameter, that we call the upper oriented chromatic number of an undirected graph G, defined as the smallest order of an oriented graph -→ T such that -→ G → -→ T for every orientation -→ G of G. The aim of this paper is to initiate the study of this new parameter. We shall give general bounds on the upper and ordinary oriented chromatic numbers of lexicographic, strong, Cartesian and direct products of undirected and oriented graphs, with a particular focus on products of paths.

This paper is organised as follows. In Section 2, we give the main definitions we shall use later and provide some elementary properties of the upper oriented chromatic number. The four following sections are respectively concerned with lexicographic, strong, Cartesian and direct products of graphs, and contain our main results. Some open problems and directions for future work are discussed in Section 7.

Definitions and notation

We denote by P k the path on k vertices, by C k the cycle on k vertices and by K k the complete graph on k vertices. If G is an undirected graph, we denote by {u, v} an edge linking vertices u and v in G. If -→ G is an oriented graph, we denote by (u, v) an arc directed from vertex

u to vertex v in -→ G . A directed path of length k in an oriented graph -→ G is a sequence of vertices x 1 . . . x k such that (x i , x i+1 ) ∈ E( -→ G ) for every i, 1 ≤ i < k.

We shall denote by

--→ DP k the particular orientation of the path P k corresponding to the directed path of length k, while -→ P k will denote any orientation of P k . For any two sets A and B, the Cartesian product

A × B denotes the set [a, b], a ∈ A, b ∈ B .
An oriented clique -→ H is an oriented graph in which every pair of vertices is joined by a directed path of length 1 or 2. From the definition of oriented colorings, it follows that

χ o ( -→ H ) = |V ( -→ H )|, whenever -→
H is an oriented clique. We define the upper oriented chromatic number of an undirected graph G, denoted χ + o (G), as the smallest order of an oriented graph

-→ T such that -→ G → -→ T for every orien- tation -→ G of G.
Proposition 1 For every undirected graph G, χ o (G) ≤ χ + o (G).
Consider for instance the cycle C 3 on three vertices. We have χ o (C 3 ) = 3 since χ o (G) ≤ |V (G)| for every undirected graph G and any two vertices in any orientation -→ C 3 of C 3 are linked by a directed path of length 1 or 2. However, χ + o (C 3 ) = 4 since the smallest oriented graph contained both a directed 3-cycle and a transitive 3-cycle as subgraphs has four vertices.

More generally, for every n ≥ 3,

χ o (K n ) = n and χ + o (K n ) = ε(n),
where ε(n) stands for the minimum size of an n-universal tournament, that is a tournament containing every tournament of order n as a subgraph. The following result is proved in [START_REF] Moon | Topics on Tournaments[END_REF]Chapter 17]:

Theorem 2 For every n ≥ 1, 2 n-1 2 ≤ ε(n) ≤ n 2 n-1 2 if n is odd, 3 2 √ 2 n 2 n-1 2 if n even.
Hence, the difference between χ o (G) and χ + o (G) can be arbitrarily large. For every graph G, let ω(G) denote the clique number of G, that is the maximum order of a complete subgraph of G. From Theorem 2, we get the following general lower and upper bounds on the upper oriented chromatic number of any graph: Corollary 3 For every graph G of order n and clique number ω(G),

χ + o (G) ≥ χ + o (K ω(G) ) ≥ 2 ω(G)-1 2 and χ + o (G) ≤ χ + o (K n ) ≤ n 2 n-1 2 if n is odd, 3 2 √ 2 n 2 n-1 2
if n even.

For complete bipartite graphs, we have the following:

Theorem 4 For every m, n with m ≤ n, χ o (K m,n ) = m + min{n, 2 m } and χ + o (K m,n ) ≤ m + 2 m . Proof. Let
≤ j ≤ n, let N -(y j ) = {x i , (x i , y j ) ∈ E( -→ K m,n )}. Clearly, the mapping ϕ : V ( -→ K m,n ) -→ V ( -→
T ) defined by ϕ(x i ) = a i for every i, 1 ≤ i ≤ m, and ϕ(y j ) = b N -(y j ) for every j, 1 ≤ j ≤ n, is a homomorphism and, therefore,

χ + o (K m,n ) ≤ m + 2 m .
We

(K m,n ) ≥ χ o ( -→ X ) = m + 2 m . On the other hand, χ o (K m,n ) ≤ χ + o (K m,n ) ≤ m + 2 m . If n < 2 m , we get χ o (K m,n ) ≥ |V (K m,n )| = m + n
by considering the orientation of K m,n corresponding to the subgraph of the above defined oriented graph -→ X induced by the set of vertices {x 1 , . . . , x m } ∪ {y 1 , . . . , y n }. Since χ o (K m,n ) ≤ |V (K m,n )|, the result follows.

As said before, many upper bounds on the oriented chromatic number of classes of undirected graphs have been obtained by providing some oriented graph -→ T such that every orientation of every undirected graph in the class admits a homomorphism to -→ T . Therefore, every such upper bound also holds for the upper oriented chromatic number of the same graphs. The following theorem summarizes some of these results. Let us recall that a graph is outerplanar if it has a planar drawing with all vertices lying on the outer face. A graph is 2-outerplanar whenever it admits a planar drawing such that deleting all the vertices of the outer face produces an outerplanar graph. The acyclic chromatic number of an undirected graph G is the smallest number of colors needed in an acyclic coloring of G, that is a proper coloring of G in which every cycle uses at least three colors.

Theorem 5 Let G be an undirected graph. We then have: [START_REF] Raspaud | Good and semi-strong colorings of oriented planar graphs[END_REF], and this bound is tight for a

1. If G is a forest with at least three vertices, then χ + o (G) = 3 [12], 2. If G = C k is a cycle on k ≥ 3 vertices, then χ + o (G) = 4 when k = 5, and χ + o (G) = 5 when k = 5 [12], 3. If χ a (G) ≤ a, then χ + o (G) ≤ a2 a-1
≥ 3 [9], 4. If G is an outerplanar graph, then χ + o (G) ≤ 7 and this bound is tight [12], 5. If G is a 2-outerplanar graph, then χ + o (G) ≤ 67 [2], 6. If G is a planar graph, then χ + o (G) ≤ 80 [11], 7. If G is a triangle-free planar graph, then χ + o (G) ≤ 59 [8], 8. If G has maximum degree ∆(G) = k, then χ + o (G) ≤ 2k 2 2 k [5].
Let G be an undirected graph. The square of G is the graph

G 2 defined by V (G 2 ) = V (G) and E(G 2 ) = {{u, v}, 1 ≤ d G (u, v) ≤ 2}
, where d G (u, v) denotes the distance between vertices u and v in G. The following theorem provides an upper bound on the upper oriented chromatic number of an undirected graph depending on the chromatic number of its square:

Proposition 6 For every undirected graph G with k = χ(G 2 ), χ + o (G) ≤ 2 k -1.
Proof. Let σ be a proper k-coloring of G 2 and S be the set of 2 k -1 elements defined as

S = {[a, b 1 , . . . , b a-1 ], 1 ≤ a ≤ k, b i ∈ {0, 1}, 1 ≤ i ≤ a -1} .
Let now -→ G be any orientation of G. We define a mapping ϕ from V (G) to S as follows. For every vertex u ∈ V (G), we set ϕ(u) = [a(u), b 1 (u), . . . , b a(u)-1 (u)] where:

1. a(u) = σ(u), 2. for every i, 1 ≤ i ≤ a(u) -1, if u has a neighbor v with σ(v) = i such that (v, u) is an arc in E( -→ G ) then a i (u) = 1, otherwise a i (u) = 0. (Since σ is a proper coloring of G 2 , if such a vertex v exists it must be unique.) We claim that ϕ is an oriented coloring of -→ G . Observe first that if u and v are adjacent vertices in -→ G , then ϕ(u) = ϕ(v) since σ(u) = σ(v)
. Suppose now that there exist two arcs (u, v) and (w,

x) in E( -→ G ) such that ϕ(u) = ϕ(x) and ϕ(v) = ϕ(w). If u = x, then σ(v) = σ(w) since σ is a proper coloring of G 2 ,
a contradiction. Otherwise, we may assume without loss of generality that i

= σ(u) = σ(x) < σ(v) = σ(w). Since (u, v), (w, x) ∈ E( -→ G )
, we get b i (v) = 1 and b i (w) = 0, again a contradiction. The mapping ϕ is thus an oriented coloring of -→ G using at most 2 k -1 colors and the result follows.

Since χ(G 2 ) ≥ ∆(G) + 1 for every graph G, Proposition 6 does not give an interesting general bound for classes of graphs with unbounded degree.

Let G and H be two undirected graphs. The Cartesian product of G and H is the

undirected graph G 2 H defined by V (G 2 H) = V (G) × V (H) and {[u, v], [u ′ , v ′ ]} is an edge in E(G 2 H) if and only if either u = u ′ and {v, v ′ } ∈ E(H) or v = v ′ and {u, u ′ } ∈ E(G).
The strong product of G and

H is the undirected graph G ⊠ H defined by V (G ⊠ H) = V (G) × V (H) and {[u, v], [u ′ , v ′ ]} is an edge in E(G ⊠ H) if and only if either u = u ′ and {v, v ′ } ∈ E(H) or v = v ′ and {u, u ′ } ∈ E(G) or {u, u ′ } ∈ E(G) and {v, v ′ } ∈ E(H). The direct product of G and H is the undirected graph G × H defined by V (G × H) = V (G) × V (H) and {[u, v], [u ′ , v ′ ]} is an edge in E(G × H) if and only if {u, u ′ } ∈ E(G) and {v, v ′ } ∈ E(H).
The lexicographic product of G and H is the undirected graph G[H] defined by

V (G[H]) = V (G) × V (H) and {[u, v], [u ′ , v ′ ]} is an edge in E(G[H]) if and only if ei- ther {u, u ′ } ∈ E(G) or u = u ′ and {v, v ′ } ∈ E(H).
Cartesian, strong, direct and lexicographic products of oriented graphs are defined similarly, by replacing edges by arcs in the above definitions.

It is not difficult to see that the Cartesian, strong and direct products are symmetric operations while G[H] and H[G] are generally not isomorphic graphs (this justifies our notation for the lexicographic product). However, these four products are associative.

Moreover, G 2 H ⊆ G ⊠ H, G × H ⊆ G ⊠ H and G ⊠ H ⊆ G[H]
for every undirected or oriented graphs G and H. Therefore, every upper bound on the upper (or ordinary)

oriented chromatic number of G[H] (resp. G ⊠ H) holds for G ⊠ H (resp. G 2 H and G × H).
Following the reference book of Imrich and Klavzar [START_REF] Imrich | Product Graphs: Structure and Recognition[END_REF], we shall denote by G v (resp.

H u ) the v-layer (resp. the u-layer) of G ⊠ H, G 2 H or G × H, that is the subgraph induced by V (G) × {v} (resp. {u} × V (H)), for every v ∈ V (H) (resp. u ∈ V (G)).
The study of the oriented chromatic number of Cartesian and strong products of graphs has been recently initiated by Natarajan, Narayanan and Subramanian [START_REF] Natarajan | Oriented colouring of some graphs[END_REF]. In particular, they proved that for every undirected graph

G, χ o (G 2 P k ) ≤ (2k -1)χ o (G) and χ o (G 2 C k ) ≤ 2kχ o (G)
for every k ≥ 3. We shall improve these two bounds in Section 5.

Lexicographic products

Concerning the oriented chromatic number of the lexicographic product of oriented graphs, we have the following:

Theorem 7 If -→ G , -→ H , -→ T and -→ U are oriented graphs such that -→ G → -→ T and -→ H → -→ U , then -→ G [ -→ H ] → -→ T [ -→ U ]. Therefore, for every oriented graphs -→ G and -→ H , χ o ( -→ G [ -→ H ]) ≤ χ o ( -→ G )χ o ( -→ H ). Proof. Let α : -→ G → -→ T and β : -→ H → -→ U be two homomorphisms. Let now ϕ : V ( -→ G [ -→ H ]) -→ V ( -→ T [ -→ U ]) be the mapping defined by ϕ([u, v]) = [α(u), β(v)] for every vertex [u, v] in V ( -→ G [ -→ H ]). We claim that ϕ is a homomorphism. To see this, let ([u, v], [u ′ , v ′ ]) be an arc in -→ G [ -→ H ]. We then have ϕ([u, v]) = [α(u), β(v)] and ϕ([u ′ , v ′ ]) = [α(u ′ ), β(v ′ )]. If (u, u ′ ) ∈ E( -→ G ), then (α(u), α(u ′ )) ∈ E( -→ T ). If u = u ′ and (v, v ′ ) ∈ E( -→ H ), then α(u) = α(u ′ ) and (β(v), β(v ′ )) ∈ E( -→ U ). Therefore, every arc in -→ G [ -→ H ] is mapped to an arc in -→ T [ -→ U ] and ϕ is a homomorphism. The inequality χ o ( -→ G [ -→ H ]) ≤ χ o ( -→ G )χ o ( -→
H ) directly follows from the definition of the oriented chromatic number.

For the lexicographic product of directed paths, we have the following:

Theorem 8 For every k, ℓ ≥ 3, χ o ( --→ DP k [ --→ DP ℓ ]) = 9.
Therefore, the bound given in Theorem [START_REF] Natarajan | Oriented colouring of some graphs[END_REF]

( --→ DP k [ --→ DP ℓ ]) ≥ χ o ( --→ DP 3 [ --→ DP 3 ]) = 9 for every k, ℓ ≥ 3.
The following result provides a general upper bound on the upper oriented chromatic number of lexicographic products of undirected graphs.

Theorem 9 Let G and H be two undirected graphs with k = χ(G 2 ) and n = |V (H)|. We then have

χ + o (G[H]) ≤ k(n + 2 n ) k-1 χ + o (H).
Proof. Let α be a proper k-coloring of G 2 and ℓ = χ + o (H). Let -→ U be an oriented graph of order ℓ such that -→ H → -→ U for every orientation -→ H of H and -→ T be the oriented graph of order n + 2 n such that -→ K n,n → -→ T for every orientation -→ K n,n of K n,n , as defined in the proof of Theorem 4 (we consider here the case m = n). We define the digraph -→ W by

V ( -→ W ) = [a, b, c 1 , . . . , c k ], 1 ≤ a ≤ k, 1 ≤ b ≤ ℓ, c a = 0, 1 ≤ c i ≤ n + 2 n , 1 ≤ i ≤ k, i = a and ([a, b, c 1 , . . . , c k ], [a ′ , b ′ , c ′ 1 , . . . , c ′ k ]) is an arc in E( -→ W ) if and only if either a = a ′ and (b, b ′ ) ∈ E( -→ U ), or a = a ′ and (c a ′ , c ′ a ) ∈ E( -→ T ). The digraph -→ W is clearly an oriented graph of order kℓ(n + 2 n ) k-1 . Let now ---→ G[H] be any orientation of G[H],
-→ H u be the oriented copy of H induced by the set of vertices {u} × V (H) and λ u :

-→

H u → -→ U be a homomorphism. If {u, u ′ } is an edge in G, let µ u,u ′ be a homomorphism of the oriented subgraph of ---→ G[H] induced by the set of vertices {u, u ′ } × V (H) to -→ T . We shall now construct a mapping ϕ from V ( ---→ G[H]) to V ( -→ W )
, and prove that this mapping is a homomorphism, which will give the desired result.

Let [u, v] be any vertex in

V ( ---→ G[H]) and ϕ([u, v]) = [a, b, c 1 , . . . , c k ] be defined as follows: (i) a = α(u), (ii) b = λ u (v), (iii) if there is a neighbor u ′ of u in G with α(u ′ ) = a ′ , then c a ′ = µ u,u ′ ([u, v]), otherwise c a ′ = 0.
Note that if such a neighbor u ′ of u exists in item (iii), then it must be unique since α is a proper coloring of

G 2 . Let now ([u, v], [u ′ , v ′ ]) be any arc in E( ---→ G[H]), ϕ([u, v]) = [a, b, c 1 , . . . , c k ] and ϕ([u ′ , v ′ ]) = [a ′ , b ′ , c ′ 1 , . . . , c ′ k ]. If u = u ′ , then a = α(u) = α(u ′ ) = a ′ and (b, b ′ ) = (λ u (v), λ u (v ′ )) ∈ E( -→ U ). If u = u ′ , then {u, u ′ } ∈ E(G), c a ′ = µ u,u ′ ([u, v]), c ′ a = µ u,u ′ ([u ′ , v ′ ]) and, therefore, (c a ′ , c ′ a ) ∈ E( -→ T ). Every arc of ---→ G[H]
is thus mapped to an arc of -→ W and ϕ is a homomorphism.

Since χ(P 2 ) ≤ 3 and χ + o (P ) ≤ 3 for every path P , Theorem 9 implies that for every k, ℓ ≥ 3,

χ + o (P k [P ℓ ]) ≤ 9(ℓ + 2 ℓ ) 2 .

Strong products

Since

-→ G ⊠ -→ H ⊆ -→ G [ -→
H ] for every two oriented graphs -→ G and -→ H , Theorem 7 implies the following:

Corollary 10 For every oriented graphs -→ G and -→ H , χ o ( -→ G ⊠ -→ H ) ≤ χ o ( -→ G )χ o ( -→ H ).
This result can be strengthtened as follows:

Theorem 11 If -→ G , -→ H , -→ T and -→ U are oriented graphs such that -→ G → -→ T and -→ H → -→ U , then -→ G ⊠ -→ H → -→ T ⊠ -→ U . Proof. Let α : -→ G → -→ T and β : -→ H → -→ U be two homomorphisms. Let now ϕ : V ( -→ G ⊠ -→ H ) -→ V ( -→ T ⊠ -→ U ) be the mapping defined by ϕ([u, v]) = [α(u), β(v)] for every vertex [u, v] in V ( -→ G ⊠ -→ H ).
We claim that ϕ is a homomorphism. To see this, let (

[u, v], [u ′ , v ′ ]) be an arc in -→ G ⊠ -→ H . We then have ϕ([u, v]) = [α(u), β(v)] and ϕ([u ′ , v ′ ]) = [α(u ′ ), β(v ′ )]. If u = u ′ and (v, v ′ ) ∈ E( -→ H ), then α(u) = α(u ′ ) and (β(v), β(v ′ )) ∈ E( -→ U ). Similarly, if v = v ′ and (u, u ′ ) ∈ E( -→ G ), then β(v) = β(v ′ ) and (α(u), α(u ′ )) ∈ E( -→ T ). Finally, if (u, u ′ ) ∈ E( -→ G ) and (v, v ′ ) ∈ E( -→ H ), then (α(u), α(u ′ )) ∈ E( -→ T ) and (β(v), β(v ′ )) ∈ E( -→ U ). Therefore, every arc in -→ G ⊠ -→ H is mapped to an arc in -→ T ⊠ -→
U and ϕ is a homomorphism.

Since χ o ( -→ P ) = 3 for every oriented path -→ P , Corollary 10 gives that the oriented chromatic number of the strong product of any two oriented paths is at most 9. We can decrease this bound to 7 for directed paths and show that this new bound is tight:

Theorem 12 For every k, ℓ ≥ 3, χ o ( --→ DP k ⊠ --→ DP ℓ ) = 7. Proof. Let --→ DP k = x 1 . . . x k and --→ DP ℓ = y 1 . . . y ℓ . All arcs in E( --→ DP k ⊠ --→ DP ℓ ) are either of the form ([x i , y j ], [x i+1 y j ]), or ([x i , y j ], [x i y j+1 ]), or ([x i , y j ], [x i+1 y j+1 ]). Let -→ T 7 =
-→ T (7; 1, 2, 3) be the circulant tournament defined by V ( -→ T 7 ) = {0, 1, . . . , 6} and (i, j) ∈ E( -→ T 7 ) if and only if (ji) mod 7 ∈ {1, 2, 3}. We will show that

--→ DP k ⊠ --→ DP ℓ admits a homomorphism to -→ T 7 , which proves χ o ( --→ DP k ⊠ --→ DP ℓ ) ≤ 7. Let ϕ : V ( --→ DP k ⊠ --→ DP ℓ ) -→ V ( -→ T 7
) be the mapping defined by ϕ([x i , y j ]) = 2j + i (mod 7), for every i, j,

1 ≤ i ≤ k, 1 ≤ j ≤ ℓ. For every arc (u, v) in --→ DP k ⊠ --→ DP ℓ , we claim that ϕ(v) -ϕ(u) ∈ {1, 2, 3}. If (u, v) is of the form ([x i , y j ], [x i+1 y j ]), then ϕ(v) -ϕ(u) = 2j + i + 1 -2j -i = 1. If (u, v) is of the form ([x i , y j ], [x i y j+1 ]), then ϕ(v) -ϕ(u) = 2(j + 1) + i -2j -i = 2. Finally, if (u, v) is of the form ([x i , y j ], [x i+1 y j+1 ]), then ϕ(v) -ϕ(u)) = 2(j + 1) + i + 1 -2j -i = 3. Every arc of --→ DP k ⊠ --→ DP ℓ is
( --→ DP k ⊠ --→ DP ℓ ) ≥ χ o ( -→ X ) = 7
and the result follows.

The following result provides a general upper bound on the upper oriented chromatic number of strong products of undirected graphs.

Theorem 13 For every undirected graphs G and H,

χ + o (G ⊠ H) ≤ (2 χ(H 2 ) -1)χ(G)χ + o (G)χ + o (H). Proof. Let k = χ(H 2 ), ℓ = χ(G), m = χ + o (G) and n = χ + o (H). Moreover, let -→ T be an oriented graph of order m such that -→ G → -→ T for every orientation -→ G of G and -→ U be an oriented graph of order n such that -→ H → -→ U for every orientation -→ H of H. Let now -→ W be the digraph defined by V ( -→ W ) = {[α, β, µ, λ, c 1 , . . . , c β-1 ], α ∈ {1, 2, . . . , ℓ}, β ∈ {1, 2, . . . , k}, µ ∈ {1, 2, . . . , m}, λ ∈ {1, 2, . . . , n}, c i ∈ {0, 1}, 1 ≤ i ≤ β -1} and ([α, β, µ, λ, c 1 , . . . , c k ], [α ′ , β ′ , µ ′ , λ ′ , c ′ 1 , . . . , c ′ k ]) is an arc in E( -→ W )
if and only if one of the following holds:

(i) α = α ′ and (λ, λ ′ ) ∈ E( -→ U ), (ii) α = α ′ , β = β ′ and (µ, µ ′ ) ∈ E( -→ T ), (iii) α = α ′ , β < β ′ , and c ′ β = 1, (iv) α = α ′ , β > β ′ , and c β ′ = 0.
The graph -→ W is clearly an oriented graph (with no opposite arcs) of order (2 k -1)ℓmn.

Let now

----→ G ⊠ H be any orientation of G ⊠ H, γ be a proper ℓ-coloring of G, and h be a proper k-coloring of H 2 . For every vertex u ∈ V (G), let µ u :

-→ H u → -→ U be a homomorphism. Similarly, for every vertex v ∈ V (H), let λ v :

-→ G v → -→ T be a homomorphism. We shall now construct a mapping ϕ from V ( ----→ G ⊠ H) to V ( -→ W ), and prove that this mapping is a homomorphism, which will give the desired result.

Let [u, v] be any vertex in

V ( ----→ G ⊠ H) and ϕ([u, v]) = [α, β, µ, λ, c 1 , .
. . , c k ] be defined as follows:

(i) α = γ(u), (ii) β = h(v), (iii) µ = µ v (u), (iv) λ = λ u (v), (v) if there is an arc ([w, x], [u, v]) in E( ----→ G ⊠ H) such that u = w and h(x) < h(v), then c h(x) = 1, (vi) if there is an arc ([u, v], [w, x]) in E( ----→ G ⊠ H) such that u = w and h(x) < h(v), then c h(x) = 0, (vii) every c i that has not been set in (v) or (vi) is set to 0.
Note that in items (v) and (vi) above, if such an arc exists, then it must be unique since h is a proper coloring of H 2 .

Let now

([u, v], [u ′ , v ′ ]) be any arc in E( ----→ G ⊠ H), ϕ([u, v]) = [α, β, µ, λ, c 1 , . . . , c k ], and ϕ([u ′ , v ′ ]) = [α ′ , β ′ , µ ′ , λ ′ , c ′ 1 , . . . , c ′ k ]. If u = u ′ then α = α ′ and (λ, λ ′ ) = (λ u (v), λ u (v ′ )) ∈ E( -→ U ). Similarly, if v = v ′ then β = β ′ and (µ, µ ′ ) = (µ v (u), µ v (u ′ )) ∈ E( -→ T ). Now, if u = u ′ and v = v ′ , then α = α ′ , β = β ′ , and either β < β ′ , in which case c ′ β = 1, or β > β ′ , in which case c β ′ = 0. Every arc of ----→ G ⊠ H is thus mapped to an arc of -→
W and ϕ is a homomorphism. Since χ(P ) = 2 and χ(P 2 ) = χ + o (P ) = 3 for every path P , we get the following: Corollary 14 For every k, ℓ ≥ 3, χ + o (P k ⊠ P ℓ ) ≤ (2 3 -1).2.3.3 = 126. For k = 2 and k = 3, Natarajan, Narayanan and Subramanian [START_REF] Natarajan | Oriented colouring of some graphs[END_REF] obtained better bounds by (implicitely) proving that χ + o (P 2 ⊠ P ℓ ) ≤ 11 and χ + o (P 3 ⊠ P ℓ ) ≤ 67, for every ℓ ≥ 3.

Cartesian products

Since

-→ G 2 -→ H ⊆ -→ G [ -→
H ] for every two oriented graphs -→ G and -→ H , Theorem 7 also implies the following:

Corollary 15 For every oriented graphs -→ G and -→ H , χ o ( -→ G 2 -→ H ) ≤ χ o ( -→ G )χ o ( -→ H ).
As before, this result can be strengthtened as follows:

Theorem 16 If -→ G , -→ H , -→ T and -→ U are oriented graphs such that -→ G → -→ T and -→ H → -→ U , then -→ G 2 -→ H → -→ T 2 -→ U .
Proof. The proof is similar to the proof of Theorem 11. Let α :

-→ G → -→ T and β : -→ H → -→ U be two homomorphisms. Let now ϕ : V ( -→ G 2 -→ H ) -→ V ( -→ T 2 -→ U ) be the mapping defined by ϕ([u, v]) = [α(u), β(v)] for every vertex [u, v] in V ( -→ G 2 -→ H ). We claim that ϕ is a homomorphism. To see this, let ([u, v], [u ′ , v ′ ]) be an arc in -→ G 2 -→ H . We then have ϕ([u, v]) = [α(u), β(v)] and ϕ([u ′ , v ′ ]) = [α(u ′ ), β(v ′ )]. If u = u ′ and (v, v ′ ) ∈ E( -→ H ), then α(u) = α(u ′ ) and (β(v), β(v ′ )) ∈ E( -→ U ). Similarly, if v = v ′ and (u, u ′ ) ∈ E( -→ G ), then β(v) = β(v ′ ) and (α(u), α(u ′ )) ∈ E( -→ T ). Therefore, every arc in -→ G 2 -→ H is mapped to an arc in -→ T 2 -→ U and ϕ is a homomorphism.
Corollary 15 implies that the oriented chromatic number of the Cartesian product of two oriented paths is at most 9. From Theorem 12, we get that the oriented chromatic number of the Cartesian product of any two directed paths is at most 7. These two bounds can be improved as follows (this result also follows from a result of Natarajan et al. [START_REF] Natarajan | Oriented colouring of some graphs[END_REF]):

Theorem 17 For every oriented paths

-→ P k and -→ P ℓ , k, ℓ ≥ 1, χ o ( -→ P k 2 -→ P ℓ ) ≤ 3. Proof. Let -→ P k = x 1 . . . x k and -→ P ℓ = y 1 . . . y ℓ . Let -→ C 3 be the directed cycle on three vertices given by V ( -→ C 3 ) = {0, 1, 2} and E( -→ C 3 ) = {(0, 1), (1, 2), (2, 0)
}. We inductively define a mapping ϕ : V (

-→ P k 2 -→ P ℓ ) -→ V ( -→ C 3 ) as follows:
(i) ϕ[x 1 , y 1 ] = 0, (ii) for every j, 2 ≤ j ≤ ℓ, ϕ([x 1 , y j ]) = ϕ([x 1 , y j-1 ]) + 1 (mod 3) if (y j-1 , y j ) ∈ E( -→ P ℓ ), and ϕ([x 1 , y j ]) = ϕ([x 1 , y j-1 ]) -1 (mod 3) otherwise. (iii) for every i, 2 ≤ i ≤ k, and for every j,

1 ≤ j ≤ ℓ, ϕ([x i , y j ]) = ϕ([x i-1 , y j ]) + 1 (mod 3) if (x i-1 , x i ) ∈ E( -→ P k ), and ϕ([x i , y j ]) = ϕ([x i-1 , y j ]) -1 (mod 3) otherwise.
It is then routine to check that the mapping ϕ is a homomorphism and thus χ o (

-→ P k 2 -→ P ℓ ) ≤ 3.
We now consider the upper oriented chromatic number of Cartesian products of undirected graphs.

Theorem 18 If G and H are two undirected graphs with k = min{χ(G), χ(H)}, then

χ + o (G 2 H) ≤ kχ + o (G)χ + o (H).
Proof. Assume without loss of generality that k = χ(H) and let λ be a proper k-coloring of H. Let -→ T and -→ U be two oriented graphs of order χ + o (G) and

χ + o (H), respectively, such that -→ G → -→ T for every orientation -→ G of G and -→ H → -→ U for every orientation -→ H of H.

Let now

-→ W be the oriented graph defined by

V ( -→ W ) = {[ℓ, a, b], 1 ≤ ℓ ≤ χ(H), a ∈ V ( -→ T ), b ∈ V ( -→ U )} and ([ℓ, a, b], [ℓ ′ , a ′ , b ′ ]) ∈ E( -→ W ) if and only if either ℓ = ℓ ′ and (a, a ′ ) ∈ E( -→ T ) or ℓ = ℓ ′ and (b, b ′ ) ∈ E( -→ U ).
We shall prove that any orientation of G 2 H admits a homomorphism to -→ W , which gives the desired result.

Fix any orientation

----→ G 2 H of G 2 H. For every v ∈ V (H), let α v : -→ G v → -→
T be a homomorphism. Similarly, for every u ∈ V (G), let β u :

-→

H u → -→ U be a homomorphism. Let ϕ : V ( ----→ G 2 H) -→ V ( -→ W ) be the mapping defined by ϕ([u, v]) = [λ(u), α v (u), β u (v)] for every [u, v] ∈ V ( ----→ G 2 H).
We claim that ϕ is a homomorphism. To see this, let

([u, v], [u ′ , v ′ ]) be an arc in ----→ G 2 H. We then have ϕ([u, v]) = [λ(u), α v (u), β u (v)] and ϕ([u ′ , v ′ ]) = [λ(u ′ ), α v ′ (u), β u ′ (v)]. If u = u ′ and (v, v ′ ) ∈ E( -→ H ), then λ(u) = λ(u ′ ), β u = β u ′ and, therefore, ([λ(u), α v (u), β u (v)], [λ(u ′ ), α v ′ (u), β u ′ (v)]) ∈ E( -→ W ). Simi- larly, if v = v ′ and (u, u ′ ) ∈ E( -→ G ), then λ(u) = λ(u ′ ), α v = α v ′ and, therefore, ([λ(u), α v (u), β u (v)], [λ(u ′ ), α v ′ (u), β u ′ (v)]) ∈ E( -→ W ). Every arc in ----→ G 2

Direct products

Since

-→ G × -→ H ⊆ -→ G [ -→ H ] for every two oriented graphs -→ G and -→ H , we get from Theorem 7 that χ o ( -→ G × -→ H ) ≤ χ o ( -→ G )χ o ( -→ H
). This bound can be improved as follows:

Theorem 21 For every oriented graphs -→ G and -→ H ,

χ o ( -→ G × -→ H ) ≤ min{χ o ( -→ G ), χ o ( -→ H )}.
Proof. This result directly follows from the fact that

-→ G × -→ H → -→ G and -→ G × -→ H → -→ H since the mapping γ : V ( -→ G × -→ H ) -→ V ( -→ G ) (resp. γ : V ( -→ G × -→ H ) -→ V ( -→ H )) defined by γ([u, v]) = u (resp. γ([u, v]) = v) is clearly a homomorphism from -→ G × -→ H to -→ G (resp. to -→ H ).
We now consider the upper oriented chromatic number of direct products of undirected graphs.

Theorem 22 For every undirected graphs G and H with k = χ(G 2 ) and ℓ = χ(H 2 ),

χ + o (G × H) ≤ 2 k(ℓ-1) -1 2 ℓ-1 -1 . Proof. Let -→ W be the digraph defined by V ( -→ W ) = [α, β, c 1,1 , . . . , c 1,ℓ , . . . , c α-1,1 , . . . , c α-1,ℓ ], 1 ≤ α ≤ k, 1 ≤ β ≤ ℓ, c i,j ∈ {0, 1}, c i,β = 0, 1 ≤ i ≤ α -1, 1 ≤ j ≤ ℓ and ([α, β, c 1,1 , . . . , c 1,ℓ , . . . , c α-1,1 , . . . , c α-1,ℓ ], [α ′ , β ′ , c ′ 1,1 , . . . , c ′ 1,ℓ , . . . , c ′ α ′ -1,1 , . . . , c ′ α ′ -1,ℓ ])
is an arc in E( -→ W ) if and only if one of the following holds:

(i) α < α ′ , β < β ′ and c ′ α,β = 1, (ii) α < α ′ , β > β ′ and c ′ α,β = 0, (iii) α > α ′ , β < β ′ and c α ′ ,β = 1, (iv) α > α ′ , β > β ′ and c α ′ ,β = 0. The digraph -→ W is clearly an oriented graph of order 1+2 ℓ-1 +• • •+2 (k-1)(ℓ-1) = 2 k(ℓ-1) -1 2 ℓ-1 -1 . Let now ----→
G × H be any orientation of G × H, a be any proper k-coloring of G 2 and b be any proper ℓ-coloring of H 2 . We shall now construct a mapping ϕ from V ( ----→ G × H) to V ( -→ W ) and prove that this mapping is a homomorphism, which will give the desired result.

Let be defined as follows:

(i) α = a(u), (ii) β = b(v), (iii) if there is an arc ([u, v], [w, x]) in E( ----→ G × H) such that a(u) > a(w) and b(v) < b(x), then c a(w),b(x) = 1, (iv) if there is an arc ([u, v], [w, x]) in E( ----→ G × H) such that a(u) > a(w) and b(v) > b(x), then c a(w),b(x) = 0, (v) if there is an arc ([w, x], [u, v]) in E( ----→ G × H) such that a(u) > a(w) and b(v) < b(x), then c a(w),b(x) = 0, (vi) if there is an arc ([w, x], [u, v]) in E( ----→ G × H) such that a(u) > a(w) and b(v) > b(x), then c a(w),b(x) = 1, (
vii) every c i that has not been set in (iii), (iv), (v) or (vi) is set to 0.

Note that in items (iii) to (vi) above, if such an arc exists, then it must be unique since a and b are proper colorings of G 2 and H 2 , respectively.

Let now (

[u, v], [u ′ , v ′ ]) be any arc in E( ----→ G × H), with ϕ([u, v]) = [α, β, c 1,1 , . . . , c 1,ℓ , . . . , c α-1,1 , . . . , c α-1,ℓ ] and ϕ([u ′ , v ′ ]) = [α ′ , β ′ , c ′ 1,1 , . . . , c ′ 1,ℓ , . . . , c ′ α ′ -1,1 , . . . , c ′ α ′ -1,ℓ ]. We thus have {u, u ′ } ∈ E(G) and {v, v ′ } ∈ E(H). Suppose first that α = a(u) < a ′ (u) = α ′ . In that case, if β = b(v) < β ′ = b(v ′ ) then c ′ α,b(v) = 1, otherwise c ′ α,b(v ′ ) = 0. Suppose now that α ′ = a(u ′ ) < a(u) = α. In that case, if β = b(v) < β ′ = b(v ′ ) then c α ′ ,b(v) = 1, otherwise c α ′ ,b(v ′ ) = 0. Therefore, in all cases, ϕ maps the arc ([u, v], [u ′ , v ′ ]) to some arc in E( -→ W )
and is thus a homomorphism.

Since χ(P 2 ) = 3 for every path P , we get that the direct product of any two paths has upper oriented chromatic number at most 2 3.2 -1 2 2 -1 = 63 3 = 21. However, every such product is the disjoint union of two components that are almost grid graphs and it has been (implicitely) shown in [START_REF] Fertin | On the oriented chromatic number of grids[END_REF] that the upper oriented chromatic number of any such component is at most 11.

Discussion

In this paper, we introduced and initiated the study of a new parameter called the upper oriented chromatic number of undirected graphs which, from our point of view, arises "naturally" in the framework of oriented colorings. We gave some general upper bounds on the upper oriented chromatic number of several types of product graphs and derived some upper bounds on the ordinary oriented chromatic number of such graphs.

We hope that this new parameter will motivate further research. In particular, most of our upper bounds for product graphs can be significantly improved when considering specific graph classes (a first step in this direction was our results on products of paths). For instance, it would be interesting to determine the upper and ordinary oriented chromatic numbers of products of trees, outerplanar graphs or, more generally, of partial k-trees.

In [START_REF] Sopena | Oriented graph coloring[END_REF], we conjectured that the oriented chromatic number of every connected cubic graph is at most 7 and, to our knowledge, this conjecture is still open. A related question is thus the following: Question 1 Determine the upper oriented chromatic number of cubic graphs.

It has been proved in [START_REF] Sopena | A note on the oriented chromatic number of graphs with maximum degree three[END_REF] that every orientation of any cubic graph admits a homomorphism to the Paley tournament of order 11 and, therefore, χ + o (G) ≤ 11 for every cubic graph G. This upper bound can probably be improved. On the other hand, we know that there exists cubic graphs with oriented chromatic number 7 [START_REF] Sopena | Oriented graph coloring[END_REF].

Every tree has upper oriented chromatic number at most 3 and we know that there are trees with oriented chromatic number 3. Every such tree T thus satisfies the equality χ + o (T ) = χ o (T ). This property also holds for every outerplanar graph (or, more generally, for every partial 2-tree) with oriented chromatic number 7. These observations lead to the following question: The notion of the oriented chromatic index of an oriented graph -→ G has been introduced in [START_REF] Pinlou | Oriented vertex and arc colorings of outerplanar graphs[END_REF], and is defined as the smallest order of an oriented graph -→ T such that the line digraph LD( -→ G ) of -→ G admits a homomorphism to -→ T . (Recall that LD( -→ G ) is given by V (LD( -→ G )) = E( -→ G ) and for every two arcs (u, v) and (u ′ , v ′ ) in E( -→ G ), ((u, v), (u ′ , v ′ )) is an arc in E(LD( -→ G )) if and only if v = u ′ .) In the same vein, we can thus define the upper oriented chromatic index of an undirected graph G as the smallest order of an oriented graph -→ U such that the line digraph of every orientation of G admits a homomorphism to -→ U . Here again, many upper bounds obtained for the oriented chromatic index of specific graph classes implicitely deal with the upper oriented chromatic index of these classes. We thus propose to study this other parameter as well.

  H is thus mapped to an arc in -→ W and ϕ is a homomorphism.Since χ(P ) ≤ 2 and χ + o (P ) ≤ 3 for every path P , Theorem 18 implies that χ + o (P k 2 P ℓ ) ≤ 2.3.3 = 18 for every k, ℓ ≥ 3. In[START_REF] Fertin | On the oriented chromatic number of grids[END_REF], Fertin, Raspaud and Roychowdhury (implicitely) proved that the upper oriented chromatic number of the Cartesian product of any two paths is at most 11.Moreover, since χ(T ) ≤ 2 and χ + o (T ) ≤ 3 for every tree T , we get the following: Corollary 19 Let T be a tree. For every undirected graphG, χ + o (G 2 T ) ≤ 6χ + o (G).In the same vein, since the cycle C 5 has upper oriented chromatic number 5 and every cycle except C 5 has upper oriented chromatic number 4, we obtain: Corollary 20 Let C k be the cycle on k vertices. For every undirected graph G, χ + o (G 2 C 5 ) ≤ 15χ + o (G), and χ + o (G 2 C k ) ≤ 12χ + o (G) for every k ≥ 3, k = 5. These two corollaries improve the results of Natarajan, Narayanan and Subramanian [7], who proved that χ o (G 2 P k ) ≤ (2k -1)χ o (G) and χ o (G 2 C k ) ≤ 2kχ o (G) for every graph G.

  [u, v] be any vertex in V ( ----→ G × H) and ϕ([u, v]) = [α, β, c 1,1 , . . . , c 1,ℓ , . . . , c α-1,1 , . . . , c α-1,ℓ ]

Question 2

 2 Give necessary or sufficient conditions for a graph G to satisfy the equality χ+ o (G) = χ o (G).

  {x 1 , . . . , x m } and {y 1 , . . . , y n } denote the two maximal independent sets of

	K m,n . We first consider χ + o (K m,n ). Let	-→ T be the oriented graph defined by
		V (	-→ T ) = {a 1 , . . . , a m } ∪ {b S , S ⊆ {1, 2, . . . , m}}
	and (a i , b S ) ∈ E(	-→ T ) if and only if i ∈ S. Let now	-→ K m,n be any orientation of K m,n .
	For every j, 1

  now consider χ + o (K m,n ). Suppose first that n ≥ 2 m and let S 1 , . . . , S 2 m denote the 2 m subsets of {1, 2, . . . , m}. induced by the set of vertices {x 1 , . . . , x m } ∪ {y 1 , . . . , y 2 m }.

	Let now K m,n ) if and only if j ≤ 2 m and i ∈ S j , and let -→ K m,n be the orientation of K m,n defined by -→ -→ X denote the subgraph K m,n The subgraph (x i , y j ) ∈ E( of -→ -→ X is
	clearly an oriented clique and, therefore, χ o

  is tight.

	Proof. Since χ o ( Theorem 7. Since any two vertices in -→ P ) ≤ 3 for every oriented path --→ DP 3 [ --→ DP 3 ] are linked by a directed path of length -→ P , we have χ o ( --→ DP k [ --→ DP ℓ ]) ≤ 9 by
	1 or 2, we have χ o


Alessandra Toninelli
email: alessandra.toninelli@inria.fr

Animesh Pathak
email: animesh.pathak@inria.fr

Amir Seyedi
email: amir.seyedi@inria.fr

Roberto Speicys Cardoso
email: roberto.speicyscardoso@inria.fr

Valérie Issarny
email: valerie.issarny@inria.fr

Middleware Support for Mobile Social Ecosystems

With the increased prevalence of advanced mobile devices (the so-called "smart" phones), interest has grown in mobile social ecosystems, where users not only access traditional Web-based social networks using their mobile devices, but are also able to use the context information provided by these devices to further enrich their interactions. Owing to the large variety of platforms available for smart phones, as well as the different ways that data and context information is represented, it is natural to think of middleware solutions that the developers of these systems can use while creating their applications.

In this paper, we highlight the issues which should be addressed by middleware designed for mobile social ecosystems, taking into account the heterogeneity of both deployment nodes and available data, the intrinsic distributed nature of mobile social applications, as well as users' security concerns. As part of our ongoing effort to develop this middleware, we present a comprehensive model to represent mobile social ecosystems and the interactions possible in them, and show how to exploit it in a representative scenario.

I. INTRODUCTION

Social ties such as friendship, common interests, and shared professional activities are central to humans as they bind individuals together. This web of social bindings is referred to as a social network. Recent technological advances in wireless networks and the increasing availability of portable devices offer a unique chance to improve social applications, i.e., applications that support human social interactions and are characterized by their swarming, transitory, and informal qualities [START_REF] Churchill | Guest editors' introduction: Social networks and social networking[END_REF], [START_REF] Foth | Facilitating social networking in inner-city neighborhoods[END_REF]. The formation of ad hoc networks enables social encounters between proximate users with common interests, anywhere and anytime [START_REF] Churchill | Guest editors' introduction: Social networks and social networking[END_REF], [START_REF] Jones | P3 systems: Putting the place back into social networks[END_REF]. A salient feature of these situations is that physical places can also act as social filters: e.g., a conference venue groups together people who are likely to share common interests. Several recent prototypes exploit individuals' co-location and reciprocal proximity for guiding social network formation and management strategies and for restricting the scope of user interactions [START_REF] Ben Mokhtar | From pervasive to social computing: algorithms and deployments[END_REF], [START_REF] Jones | P3 systems: Putting the place back into social networks[END_REF], but there is still a need for models to adequately represent the complexities arising from interactions with content (commenting, tagging, etc.), as well as formation of groups and organization of events. We propose the term mobile social ecosystem (MSE) to describe this richer set of interactions occuring between the participants in these situations. Supporting MSE applications raises several challenges, which are the focus of this paper.

In order to better illustrate the potential of mobile social ecosystems, and the challenges associated with designing middleware for managing them, we present a detailed discussion This work was funded in part by an ERCIM Alain Bensoussan Fellowship Programme and the EU FP7 ICT FET CONNECT project. of a representative scenario. Our example revolves around a fictitious professional event, the European Conference for Young Researchers (ECYR), being organized in Amsterdam, the Netherlands. The conference consists of keynote talks, technical sessions, and breakout sessions for birds-of-a-feather to discuss topics of common interest. We assume that a certain amount of information, both about the event as well as the participants, is known at the beginning of the conference. As the meeting progresses, the users can gather more data, and use it to augment their view of the social ecosystem. Specifically, the following information is known a priori by everyone:

• Topics of Interest. In order to better match attendees to sessions, the conference provides a list of topics of interest. These are 1) Functional Programming, 2) Sensor Networks, 3) Android Mobile Phone OS, 4) Ceramics, 5) Formal Methods, and 6) Biotechnology.

• Participant List. The organizers of the conference compile a participant list which includes a speaker list that contains public information about the conference speakers and authors, and a pointer to an online professional profile (we have chosen LinkedIn public IDs in this example); and the information provided by each (non-speaker) attendee. Each attendee, in addition to the speaker list, had access to a subset of the participant list, compiled by combining his existing social relations, new acquaintances made at the conference, or possibly an official list provided by the conference organizers. In the sample list shown in Table I, rows 1 -4 represent the speaker list while attendee #6 may also be aware of the information of attendee #5, due to their being colleagues.

• Conference Schedule. This contains the list of events planned during the day, and their details include the presenters, location, timing, and theme, as relevant. A sample schedule can be seen in Table II.

• Locations. The list of locations available for activities during the conference. This is used to annotate both publicly available information such as the schedule, as well as for people to annotate their personal data such as location of stay, which they can then share with other participants whom they trust.

During the course of the conference, we envisage that the users will use the above information to perform the following activities, among others:

• Look up information on the research profiles of speakers and fellow attendees, subject to their privacy settings;

• Use the system's recommendation (based on shared topics • Make notes on the talks during the conference, and discuss with fellow attendees based on their comments;

• Plan shared taxi rides based on (newly shared) accommodation information;

• Plan spontaneous meetings based on common interests, and room availabilities; and

• Plan social events in Amsterdam in the evenings based on discovering interests of new acquaintences.

Complex mobile social ecosystems of the future, such as the one discussed in the scenario above, provide a rich platform for collaboration among individuals for achieving both professional and personal goals. In mobile social ecosystems, the heterogeneity of software platforms on constituent nodes, combined with their intrinsic distributed nature and heterogeneity of representation of data and context raises the need for middleware platforms to support the development of mobile social applications (MSAs).

Developing middleware for mobile social ecosystems is an extremely interesting and challenging research domain. Towards that end, in this paper, we make two contributions. Firstly, in Section II, we discuss in detail the various challenges in designing a middleware framework for MSE management. Following this, in Section III, we provide an expressive and extensible model of these social ecosystems, which can be used by middleware designers. We discuss related work on middleware for MSEs in Section IV, and conclude in Section V with a sketch of our planned research in the near future.

II. CHALLENGES FOR MIDDLEWARE FOR MOBILE SOCIAL ECOSYSTEMS

The development of mobile social applications can be greatly simplified by the presence of middleware support. Middleware would be responsible for collecting, maintaining and processing social data, as well as allowing access to those data via flexible interfaces, thus enabling different applications to exploit information provided by the mobile social ecosystem. The design and development of a middleware support platform for mobile social applications (or a MSE management middleware), however, is challenging and must address a number of issues. In the following, we discuss the features which must be provided by middleware for these applications:

Expressive and flexible models to represent mobile social ecosystems: Existing social network models [START_REF] Eagle | Inferring friendship network structure by using mobile phone data[END_REF], [START_REF] Pentland | Automatic mapping and modeling of human networks[END_REF] and social platforms [5] mostly define social interactions in terms of generic friendship relations between users, while not taking into account contextual information that might be very relevant on mobile platforms, such as proximity or location. An MSE management middleware should represent multiple aspects of users' social interactions by providing a comprehensive model that includes additional relations, such as content sharing and tagging, co-location, proximity, group membership, event participation and common interests.

Additionally, most existing Web-based social platforms, such as Facebook [5] or LinkedIn [START_REF]Linked In[END_REF] are designed for a specific purpose and do not allow data sharing across different applications. When the need to enhance existing Web applications with social features arises, application developers often choose to define an ad-hoc representation for social information (e.g., YouTube [START_REF]You Tube[END_REF]). This not only causes data redundancy, but also makes it very difficult to keep social data consistent across applications, while forcing developers to manage multiple representations of application-specific social information. The role of middleware is therefore to provide a shared model for social data representation, which allows different applications to produce, exchange and exploit social data with different purposes. This brings to the fore security and privacy issues, and the need to enforce access control policies, both between users and applications, as discussed next.

Privacy-awareness and access control: Mobile social applications manage contextual data, such as mobility traces, user preferences and activities, as well as human relationships, which are sensitive per se and can be further used to infer sensitive information. This raises critical security issues, particularly in terms of privacy and access control of users' data. Enforcing security in dynamic and open environments is always difficult as traditional models for distributed systems are not designed to face mobility issues. The task becomes even more difficult given the networked nature of MSAs, where information comes from multiple sources, moves to multiple destinations (possibly unforeseen at information production time) and is linked to other information following unpredictable patterns. We claim that security issues should be taken into account from the design phase of a MSE management middleware, affecting both the data model and the platform architecture. For instance, users should be enabled to store social information in their own devices and have full control over data disclosure. In addition, appropriate access control policies should be defined and enforced over social data exchange [START_REF] Toninelli | What's on users' minds? toward a usable smart phone security model[END_REF].

MSE management functionalities: MSE management includes functionalities for (a) MSE creation, and (b) MSE updates. Information describing each user's MSE may be gathered from existing social applications (e.g., a Facebook friendship link), but also by analyzing available contextual information, such as users' proximity patterns [START_REF] Li | Multi-layered friendship modeling for locationbased mobile social networks[END_REF], [START_REF] Noulas | Inferring interests from mobility and social interactions[END_REF] or mobile phone usage traces [START_REF] Eagle | Inferring friendship network structure by using mobile phone data[END_REF]. As human relations evolve, data describing MSE must change to represent this dynamics. In particular, the topology of social connections in mobile environments might vary not only because of changes in users' relations (e.g., users strengthening their ties or meeting new people), but also because of their mobility. In addition, since mobile devices are resource-constrained, algorithms for adding, removing or modifying data in a user's MSE must be efficient. For example, existing work on network topology (e.g., scale-free networks [START_REF] Albert | The diameter of the world wide web[END_REF]) may provide useful background and inspiration to design novel algorithms for the dynamic removal of nodes from mobile social ecosystems.

Fully distributed architecture: Mobile environments are naturally distributed, and users must be able to access their MSE data anywhere and anytime. Centralized architectures used by current Web social applications and platforms, thus, are not appropriate for the mobile setting. Therefore, MSE management middleware should be designed in a fully distributed fashion to exploit mobile ad-hoc connectivity, whenever and wherever available, and without assuming centralized servers. The middleware should also provide protocols and algorithms that enable user applications to benefit from MSE information even if only provided with its partial view. A global view of users' MSE may not (always) be available, while privacy and portability issues might discourage approaches based on MSE data replication on each user's device. Therefore, novel algorithms and techniques are needed to allow users to add, remove and exchange relevant parts of their MSE data with other users.

In this section we motivated the need for novel research on MSE management middleware. In the following we show our initial effort in this direction by providing a representational model of social data for MSE management middleware.

III. MODELING MOBILE SOCIAL ECOSYSTEMS

Despite their intuitive meaning in everyday life, social ecosystems might be very challenging to represent by means of a formal model. Graph theory, which offers a natural solution to model social networks, is in fact the most common approach to represent social relationships in the state of the art. The initial quantitative approaches to social networks, such as [START_REF] Kleinberg | The small-world phenomenon: An algorithmic perspective[END_REF], were inspired by "small world" models, where the social network is essentially modeled as a random graph with adjusted degree distribution [START_REF] Newman | Random graph models of social networks[END_REF]. Relevant work has also been dedicated to analyzing the properties of social networks based on graph topology and dynamic evolution [START_REF] Mislove | Measurement and analysis of online social networks[END_REF].

To the best of our knowledge, all existing work in this social models relies on some variation of a basic "social relation" model, where nodes are people (or more generally agents) and edges represent a generic link between them [START_REF] Leskovec | Statistical properties of community structure in large social and information networks[END_REF], [START_REF] Newman | Random graph models of social networks[END_REF]. More complex models take time into account by defining edges between nodes as state functions [START_REF] Van De Bunt | Friendship networks through time: An actor-oriented dynamic statistical network model[END_REF], or assign different weights to the edges of a social graph, in order to express a variable degree of tie strength [START_REF] Kumpula | Emergence of communities in weighted networks[END_REF]. However, they do not explicitly distinguish different types of social ties, from real friendship to acquaintance, from specific relationships (e.g., colleagues) to preference/interest sharing. Real social ecosystems, however, are more complex than represented in current models. This is because several activities and interactions of users actually have a social meaning, although they are not generally considered as being part of social networks. For example, user profiles adopted in several mobile context-aware applications often contain socially relevant information, such as interests and preferences, but also affiliation to organizations or groups. This seems to suggest that some of these categories should find their place in a proper MSE model.

Another interesting contribution is provided by research in the field of spontaneous ontology development by online users, i.e., folksonomy [START_REF] Mika | Ontologies are us: A unified model of social networks and semantics[END_REF]. Folksonomies are taxonomies describing a specific domain of knowledge, which are built by connecting relevant concepts created by users and assigned to online content via tagging (e.g., on Flickr). By integrating the social dimension with the existing models for folksonomies, it is possible to link online users with the content they tagged, thus creating a tripartite graph of actors, concepts and instances [START_REF] Mika | Ontologies are us: A unified model of social networks and semantics[END_REF]. However, since these models are conceived for online content and user modeling, they do not generally take into account users' dynamic characteristics, such as proximity and location, as well as the specific issues/potentials of MSAs (e.g., building location-based social ecosystems).

A. A Comprehensive Model for Mobile Social Ecosystems

In order to provide a suitable trade-off between formal MSE modeling and application-specific concepts, we define a set of basic entities acting as building blocks for the creation of mobile social ecosystems. We call these entities first-class entities, meaning that they are necessary and sufficient to describe any mobile social ecosystem, albeit in a general way. We derived these entities from the analysis of (i) real world use case scenarios, like the one described in Section I, and other scenarios presented by existing work on mobile social networks [START_REF] Ben Mokhtar | From pervasive to social computing: algorithms and deployments[END_REF]; (ii) existing models for representing not only social networks, but also networks of contents, such as folksonomies [START_REF] Mika | Ontologies are us: A unified model of social networks and semantics[END_REF]; and (iii) previous experience on knowledge representation, particularly with respect to semantic languages to represent social information [START_REF] Toninelli | What's on users' minds? toward a usable smart phone security model[END_REF]. The model defines five first-class entities, namely: Agent. An entity having beliefs, desires, intentions, according to the BDI design model for intelligent agents [START_REF] Rao | Modeling rational agents within a BDIarchitecture[END_REF]. Subclasses of Agent are Person and Group. A Group is a set of Persons.

Person and Group are used in practice more frequently than the generic Agent class. However, their superclass is needed to collect relevant properties and relationships that are common to both classes.

Event. In general, a 4D occurrence, i.e., an entity whose existence in characterized in tridimensional space and time [START_REF] Guarino | An overview of ontoclean[END_REF]. Among others, social events, such as meetings, represent an interesting type of event. Events are not, however, bound to any specific social setting: for example, a person entering a room may be modeled as an event if this had a social meaning to the application. As events have a temporal dimension, they can be either atomic, or the temporal composition of two or more events (either in sequence or in parallel).

Place. A physical entity located in a space. This concept is especially needed to model mobile social ecosystems, where physical location plays an explicit role in social activities.

Content. An entity that conveys some kind of information. It could also be defined as an information object, such as a picture, a blog post or a speech.

Topic. A subject of interest for users in mobile social ecosystems. This concept definition was mainly driven by common application scenarios, where users "tag" contents online with keywords and categories (e.g., folksonomies). Among the above defined classes several binary relations might hold, including self-referential properties. We define a subset of fundamental relations that we call first-class relationships. First-class relationships reflect an essential and invariant relation between the two considered entities (or the same entity in case of self-referential). For example, an agent's relation with an event is always some kind of involvement: depending on the particular situation, the agent might be the presenter of a talk or the organizer of a party. Other relations may be added to first-class ones, some of which being fundamental to describe specific applications. For instance, by defining Picture as a subclass of Content and defining the depicts relationship, one might state that a picture depicts a place. However, given the application-dependent nature of those relations, we do not include them in the first-class set.

Figure 1 shows the graph of first-class entities and relationships. The graph should be interpreted as the set of base relations that may hold between a set of first-class entities and it reads as follows. An agent may be involved in an event; may be located in a place; may know another agent; may be the creator of a content; and may belong to a group. A place may be located in another place. An event may also be located in a place. An agent may be interested in any event, place, topic and content. Agents, places, events and contents may be tagged with a topic. The model also includes a set of attributes that provide information about an agent, such as name, email and homepage. These attributes were inspired by the Friendof-a-Friend (FOAF) ontology, one of the very few existing standards for expressing socially relevant information [START_REF]Friend of a Friend[END_REF].

We represent our MSE model by adopting the Resource Description Framework (RDF) 1 , a base Semantic Web standard. The data model of RDF is very generic and is well suited to modeling real-world phenomena, including entities, events and interactions that characterize mobile social ecosystems. RDF enables simple reasoning over data, and thus supports the association of formal semantics with data models. At the same time, RDF encourages modeling using semi-structured data, alleviating the need for a strict, predefined schema. In particular, the MSE, as described above, is represented as a graph of RDF triples, i.e. subject-predicate-object triples, with each statement describing an attribute and its value. The set of RDF statements defining social information is linked as a graph of nodes and arcs, as shown in Figure 1. Agent's attributes have been modeled as RDF datatype properties and mapped onto FOAF corresponding properties, thanks to the common RDF vocabulary. This allows the direct import of existing FOAF profiles into our model2 , with no additional effort. In case richer expressivity is needed (e.g., defining constraints on the cardinality or range of a property), ontologies can be easily augmented with Web Ontology Language (OWL) constructs. Given OWL's greater complexity, we limit our initial model to RDF, while keeping the possibility to upgrade to OWL whenever needed.

As a final remark, we note that our model provides firstclass entities and relationships to the MSE application developer who wishes to exploit them with no additional effort. The model does not, however, tightly constrain the usage of available classes and properties, nor does it prevent the developer from extending the base model to accomodate specific application requirements. This is mainly due to the flexibility of semantic languages, as shown in the following section. Additionally, because our model is based on a graph representation, it is well suited to support the retrieval and representation of partial MSE knowledge since graphs can be split and merged based on users' application needs. Finally, existing quantitative models for social network analysis can be usefully applied to each (first-class) relationship, or possibly to a combination of then, to generate n-dimensional graphs.

B. Applying the Model to a Real Use Case Scenario

In this section we show how to concretely exploit our proposed model to describe mobile social ecosystems. In particular, by referring to the scenario introduced in Section I, we consider the following situation. Animesh is attending the second talk of Session I (see Table II), given by Joseph Katz. Arun Kulkarni is also attending his colleague's talk. Arun and Animesh introduce each other just before the talk and they exchange some basic information, including their LinkedIn profiles. By extracting keywords from the paper Arun is coauthor of, Animesh's application infers that they might share an interest for operating systems running on smart phones. Therefore, Animesh invites Arun to attend breakout session 2, and creates on-the-fly a discussion group for conference attendees interested in Android OS. Knowing that his colleague Alessandra is also interested in Android, Animesh invites her to join the group and proposes to group members to meet at the Reception Hall during the coffee break. Alessandra accepts both invitations, while Arun will not join the meeting because of a previous scheduled meeting.

Extending the base model: Let us consider Tables I andII. In order to translate data included in these tables into our model, a number of steps are required. The first step is extending the base model with application-specific classes and properties. Extension proceeds by subclassing RDF classes/properties and possibly importing other (portions of) ontologies, provided that they are compliant with the base model. In our example, we create subclasses of Event (Talk, Coffee Break and Meeting); subclasses of Group (Affiliation); and subclasses of Content (Paper and Keynote). We also create the corresponding property linking this new type of content to a person (subclass of agent), i.e., a person may be the speaker of a talk, and a person may attend a talk or meeting. A talk may present a paper or a keynote. We also create a subproperty of creator called admin, to express that a person may be the administrator of a group. We create a subproperty of homepage datatype property, called LinkedIn, referring to the personal homepage identifier on LinkedIn. Finally, we subclass the generic Place with more specific Room.

Creating entity instances: Now we can create instances of available classes. Based on Table I, we create instances of Person, e.g., "Arun Kulkarni" and "Animesh Pathak" each with its associated attributes (name and LinkedIn homepage identifier). We also created instances of Paper (e.g., "Cats on Pots: Android"), as well as the corresponding instances of Talk; of Places (e.g., "Room 5.A"); of Groups/Group subclasses (e.g, "INRIA" and "Android OS"); and a set of topics of interests for the conference attendees (e.g.,"Android"). Connecting entities via social relationships: Finally, we link instances via appropriate properties according to the underlying ontological model. The resulting social graph is depicted in Figure 2. We adopt an N3-like notation 3 , where each individual's name is followed by the class it is an instance of, and define namespaces for the mobile social ecosystem model (mse:) and the example extension (ex:). Note that the graph represents all social information known by Animesh: in particular, plain arrows/ovals are data known at the beginning, dashed arrows/ovals are portions of social graph acquired from Arun, and long dashed-dotted arrows/ovals are graph portions created by him during the interaction with Arun. Name and LinkedIn identifiers for Animesh and Alessandra are not shown in figure for the sake of clarity.

IV. RELATED WORK

Web-based social networking applications have been rapidly spreading during the last few years, as shown by the success of Web-based social platforms, such as Facebook [5] and Twitter [32], as well as by the development of applications exploiting social information for various purposes, for example recommender systems based on social trust [START_REF] Geyer | Recommending topics for self-descriptions in online user profiles[END_REF], [START_REF] Golbeck | FilmTrust: movie recommendations using trust in web-based social networks[END_REF]. Traditional Web applications, e.g., maps and email clients, have also been enhanced with social features [10], while recent efforts attempt to provide a uniform interface to access social information [START_REF]Open Social[END_REF].

Moving from Web-based social communities to physical spaces, social applications specifically targeted at mobile environments have been developed in recent years. Current MSAs, such as applications supporting the dissemination of content updates (e.g., news or traffic information) over a mobile social network [START_REF] Ioannidis | Distributing content updates over a mobile social network[END_REF], or exploiting mobile social networking to enhance group communication [START_REF] Grob | Cluestr: mobile social networking for enhanced group communication[END_REF], are often designed from scratch by embedding into the application logic all MSE management functionalities and providing application-specific data representation models. Some authors have recognized the need to externalize social management functionalities [START_REF] Rana | An architecture for mobile social networking applications[END_REF], [START_REF] Tran | Social context: Supporting interaction awareness in ubiquitous environments[END_REF], but to the best of our knowledge, only a few middleware frameworks to support MSAs have been proposed. The MobiSoc middleware supports the development of MSAs by allowing the sharing of social data between applications, as well as inferring new social knowledge from the observation of geo-social data [START_REF] Gupta | MobiSoC: a middleware for mobile social computing applications[END_REF]. MobiSoc centralized architecture, where a trusted server collects and manages all social information, is not suitable for modern MSEs, as discussed in Section II. In addition, MobiSoc only models profiles of people and places, while our model is able to represent more complex social interactions, including contents and events. Similarly, the MobiClique middleware, which supports social interaction between proximate users on mobile ad-hoc networks, only provides a very simple data model, focused on a specific application domain, and does not provide security features [START_REF] Pietiläinen | Experiments in mobile social networking[END_REF]. On the other hand, it represents an interesting effort to build a decentralized middleware architecture, which also provides social APIs. The semantic data model presented in [START_REF] Ben Mokhtar | From pervasive to social computing: algorithms and deployments[END_REF], where the FOAF ontology is extended to model users' interests and activities, is the most similar to our RDF model. We take, however, a more comprehensive approach since our base ontology can integrate with FOAF, but also includes additional concepts. Moreover, their middleware is mainly focused on a specific application domain, that is, supporting mobile users in the accomplishments of their tasks, while our model is generic and well suited to represent various application domains.

Finally, several techniques and algorithms have been developed to extract meaningful social information from available context/location data, such as users' proximity patterns [START_REF] Li | Multi-layered friendship modeling for locationbased mobile social networks[END_REF], [START_REF] Noulas | Inferring interests from mobility and social interactions[END_REF] or mobile phone usage traces [START_REF] Eagle | Inferring friendship network structure by using mobile phone data[END_REF]. These techniques may be usefully integrated within a MSE management middleware to provide social information extraction and inference.

V. CONCLUSIONS AND FUTURE WORK

In this paper, we discussed the challenges in designing middleware support for complex mobile social ecosystems of the not-so-distant future. We also presented the first results of our ongoing effort to develop this middleware, that is, an expressive and extensible model to represent MSEs and the interactions possible in them, and demonstrated its application in a representative scenario. Based on the proposed model, we are currently working on the design of a middleware framework to support mobile social ecosystems, and on the implementation of a prototype mobile social application that utilizes our middleware.

Fig. 1 .

 1 Fig. 1. First-class Entities and Relationships

Fig. 2 .

 2 Fig. 2. Application of our Model to the ECYR Scenario

http://www.w3.org/TR/rdf-primer/

Available at http://www-rocq.inria.fr/arles/mse/ontologies/mse.rdf

http://www.w3.org/DesignIssues/Notation3