Thème Com

Frédéric Havet -Andrew

D King

Frédéric Havet

Andrew D King

List circular backbone colouring

Keywords: backbone colouring, list colouring, planar graph, combinatorial Nullenstellensatz

A natural generalization of graph colouring involves taking colours from a metric space and insisting that the endpoints of an edge receive colours separated by a minimum distance dictated by properties of the edge. In the q-backbone colouring problem, these minimum distances are either q or 1, depending on whether or not the edge is in the backbone. In this paper we consider the list version of this problem, with particular focus on colours in Z p -this problem is closely related to the problem of circular choosability.

We first prove that the list circular q-backbone chromatic number of a graph is bounded by a function of the list chromatic number. We then consider the more general problem in which each edge is assigned an individual distance between its endpoints, and provide bounds using the Combinatorial Nullstellensatz. Through this result and through structural approaches, we achieve good bounds when both the graph and the backbone belong to restricted families of graphs.

Coloration dorsale circulaire sur listes

Résumé : Une généralisation naturelle de la coloration de graphe requiert de prendre des couleurs dans un espace métrique et que deux sommets reliés par une arête rec ¸oivent des couleurs séparées par une distance minimum imposée par les propriétés de l'arête. Dans les cas de la coloration q-dorsale, ces distances minimum valent q ou 1, suivant que l'arête est dans la dorsale ou non. Dans ce rapport, nous considérons un version sur listes de ce problème, en prenant des couleurs dans Z p -ce problème est étroitement lié au problème de la choisissabilité circulaire.

Nous prouvons d'abord que la choisissabilité q-dorsale circulaire d'un graphe est majorée par une fonction de la choisissabilité. Nous considérons ensuite un problème plus général dans lequel chaque arête est munie d'une distance propre requise entre ses extrémités et donnons des bornes supérieures à l'aide du Nullstellensatz combinatoire. A l'aide de ce résultat et d'approches structurelles, nous obtenons de bonnes bornes quand le graphe et la dorsale appartiennent à des classes particulières de graphes.

Mots-clés : coloration dorsale, coloration sur listes, graphe planaire, Nullenstellensatz combinatoire

Introduction

All graphs considered in this paper are simple. Let G = (V, E) be a graph, and let H = (V, E(H)) be a subgraph of G, called the backbone. A k-colouring of G is a mapping f : V → {1, 2, . . . , k}. Let f be a k-colouring of G.

It is a proper colouring if | f (u) -f (v)| ≥ 1.
It is a q-backbone colouring for (G, H) if f is a proper colouring of G and | f (u)f (v)| ≥ q for all edges uv ∈ E(H). The chromatic number χ(G) is the smallest integer k for which there exists a proper k-colouring of G. The q-backbone chromatic number BBC q (G, H) is the smallest integer l for which there exists a q-backbone k-colouring of (G, H).

If f is a proper k-colouring of G, then g defined by g(v) = q • f (v) -(q -1) is a q-backbone (q • kq + 1)colouring of (G, H) for any spanning subgraph H of G. Hence, BBC q (G, H) ≤ q • χ(G)q + 1.

(1)

In [START_REF] Broersma | Backbone colorings for networks[END_REF][START_REF] Broersma | Backbone colorings for graphs: tree and path backbones[END_REF], Broersma et al. showed that for any integer k there is a graph G with a spanning tree T such that BBC 2 (G, T ) = 2k -1.

One can generalize the notion of backbone colouring by allowing a more complicated structure of the colour space. A natural choice is to impose a circular metric on the colours. We can see Z k as a cycle of length k with vertex set {1, . . . , k} together with the graphical distance || k . Then |a -b| k ≥ q if and only if q ≤ |a -b| ≤ kq. A circular q-backbone k-colouring of G or q-backbone Z k -colouring of (G, H) is a mapping f : V (G) → Z k such that c(v) = c(u) for each edge uv ∈ E(G) and |c(u)c(v)| r ≥ q for each edge uv ∈ E(H). The circular q-backbone chromatic number of a graph pair (G, H), denoted CBC q (G, H), is the minimum k such that (G, H) admits a circular q-backbone k-colouring.

A backbone Z k -colouring is trivially a backbone k-colouring. On the other hand, a backbone k-colouring yields a circular backbone Z k+q-1 -colouring. Hence for every graph pair (G, H) (where

H is a subgraph of G), we have BBC q (G, H) ≤ CBC q (G, H) ≤ BBC q (G, H) + q -1. (2)
It is well-known that CBC q (G, G) = q • χ(G) and so

CBC q (G, H) ≤ q • χ(G) for every subgraph H of G. ( 3
)
This bound is tight if H contains a complete graph of size χ(G). In particular, it is the case when G is bipartite, and H is non-empty. On the other hand, Broersma et al. [START_REF] Broersma | λ-backbone colorings along pairwise disjoint stars and matchings[END_REF] gave better upper bounds when the backbone is a matching. We explore similar restrictions shortly, but first we define a list colouring analogue.

List backbone colourings

The notions of backbone and circular backbone colouring naturally generalize to list colouring. An S-list assignment of a graph G is a mapping L which assigns to each vertex v ∈ V (G) a prescribed list of colours L(v) ⊆ S, where S is a set of colours. For a list assignment L, an L-colouring is a colouring c such that c(v) ∈ L(v) for every vertex. The graph pair (G, H) is said to be circularly q-backbone k-choosable if for any Z p -list assignment L such that |L(v)| ≥ k, there is an L-colouring that is a q-backbone Z p -colouring. The list circular q-backbone number of a pair (G, H), denoted CBC ℓ q (G, H) is the least integer k such that (G, H) is circularly q-backbone k-choosable. The concept of circular choosability, introduced by Mohar [START_REF] Mohar | Choosability for the circular chromatic number[END_REF] and Zhu [START_REF] Zhu | Circular choosability of graphs[END_REF], is closely related to list circular backbone colouring. Indeed, the circular list chromatic number or circular choice number of G may be defined as cch(G) := inf{CBC ℓ q (G, G)/q}.

Zhu [START_REF] Zhu | Circular choosability of graphs[END_REF] proved that cch(G) ≥ χ ℓ (G) -1 for every graph G. This implies that CBC ℓ q (G, G) ≥ q • χ ℓ (G)q for every positive q. In view of this inequality and the fact that CBC q (G, G) = q • χ(G), it is natural to ask whether CBC ℓ q (G, G) can be bounded by a function of χ ℓ (G). We answer in the positive in Section 2. However, the function we prove is exponential in χ ℓ (G) -we believe that it is far from optimal, and pose the following problem.

Problem 1. Let q be a positive integer. What is the minimum function m q such that for every k-choosable graph G,

CBC ℓ q (G, G) ≤ m q (k)? In other words, what is m q (k) = max{CBC ℓ q (G, G) | χ ℓ (G)
= k} ? This is closely related to a conjecture of Zhu [START_REF] Zhu | Circular choosability of graphs[END_REF].

Conjecture 2 (Zhu [START_REF] Zhu | Circular choosability of graphs[END_REF]). There is a constant α such that, for every graph G, cch(G) ≤ α • χ ℓ (G).

Note that if such an α exists then it is at least two, as for any positive integer M,

χ ℓ (K k,m k ) ≤ k + 1 and cch(K k,m k ) ≥ 2 -2k
m k. Conjecture 2 would be implied by the following.

Conjecture 3. Let q be a positive integer. There is a constant α q such that, for every graph G,

CBC ℓ q (G, G) ≤ α q • q • χ ℓ (G).
As an evidence in support of the latter conjecture, we prove (Theorem 17) that for a graph G and a matching

M, CBC ℓ 2 (G, M) ≤ 2 • χ ℓ (G) + 1 and CBC ℓ q (G, M) ≤ 2q(1 + o(1)χ ℓ (G)
, where o( 1) is a function tending to 0 when χ ℓ (G) tends to infinity. These bounds generalize to any backbone H in an upper bound in terms of χ ℓ (G) and χ ′ (H), the chromatic index of H:

CBC ℓ 2 (G, H) ≤ 2 χ ′ (H) χ ℓ (G) + 1 and for any q ≥ 3, CBC ℓ q (G, H) ≤ 2 χ ′ (H) q(1 + o(1))χ ℓ (G).
In Section 3, we consider list circular backbone colouring of 2-choosable graphs. In [START_REF] Erdős | Choosability in graphs[END_REF], Erdős, Rubin, and Taylor characterized such graphs as follows. The heart of a graph G is the maximal subgraph in which there is no vertex of degree one. The graph consisting of two vertices connected with three internally vertex-disjoint paths of length i, j and k is θ i, j,k .

Theorem 4 (Erdős et al. [START_REF] Erdős | Choosability in graphs[END_REF]). A connected graph is 2-choosable if and only if its heart is either a single vertex, an even cycle or θ 2m,2,2 for some integer m ≥ 1.

Using this characterization, Havet et al. [START_REF] Havet | Circular choosability[END_REF] proved that if G is 2-choosable, then CBC ℓ q (G, G) ≤ 5q/2. This upper bound was later improved by Norine, Wong, and Zhu [START_REF] Norine | Circular choosability via combinatorial nullstellensatz[END_REF] to 16q/7. In other words, m q (2) ≤ 16q/7. They conjectured that m q (2) = 2q.

Conjecture 5 (Norine, Wong, and Zhu [START_REF] Norine | Circular choosability via combinatorial nullstellensatz[END_REF]). If G is 2-choosable, then CBC ℓ q (G, G) = 2q. This conjecture is trivial for trees and was proved by Norine [START_REF] Norine | On two questions about circular choosability[END_REF] for even cycles (and so for all graphs whose heart is an even cycle).

Theorem 6 (Norine [START_REF] Norine | On two questions about circular choosability[END_REF]). If C is an even cycle, then CBC ℓ q (C,C) = 2q for all q. Norine, Wong, and Zhu [START_REF] Norine | Circular choosability via combinatorial nullstellensatz[END_REF] also verified Conjecture 5 for K 2,3 = θ 2,2,2 . Note that Conjecture 5 implies that if G is 2-choosable, then CBC ℓ q (G, H) = 2q for any non-empty subgraph H of G. We prove that this is the case if H is a matching (Theorem 28). We also show that if H does not contain the heart of G, then CBC ℓ q (G, H) ≤ 2q + 1.

Edge-weighted backbones

In Section 4 we generalize the idea of a backbone colouring by giving every edge e a positive integer weight w(e) dictating the minimum distance between the colours of its endpoints.

Formally, a colouring c of G of G is w-coherent if |c(u) -c(v)| ≥ w(uv) for every edge uv of G. A graph G is w-coherent k-choosable if, given any list assignment L such that |L(v)| ≥ k for each vertex v of G, there is a w-coherent L-colouring. INRIA Similarly, a Z p -colouring c of G is w-circular if |c(u) -c(v)| p ≥ w(uv) for every edge uv of G. A graph G is w-circular k-choosable if, given any Z p -list assignment L such that |L(v)| ≥ k for each vertex v of G,
there is a w-circular L-colouring. Clearly, every w-circular colouring is a w-coherent colouring, and every w-coherent k-colouring induces a w-circular (k + max v∈V w(v) -1)-circular colouring.

The w-degree of a vertex v is d w (v) = ∑ e∋v (2w(e) -1). The maximum w-degree of G, denoted ∆ w (G), is max{w(v) | v ∈ V (G)}. Clearly, using the (one-pass) greedy algorithm, every graph is w-circular (∆ w (G) + 1)choosable.

The w-semi-degree of a vertex v is dw (v) = ∑ e∋v w(e), and the maximum semi-degree of a graph G is ∆w

(G) = max{ dw (v) | v ∈ V (G)}.
Using the many-passes greedy algorithm, McDiarmid [START_REF] Mcdiarmid | On the span in channel assignment problems: bounds, computing and counting[END_REF] proved that every graph

G is w-coherent ( ∆w (G) + 1)-choosable. Therefore every graph G is w-circular ( ∆w (G) + max v∈V w(v))-choosable.
For a digraph D, we denote by E + D (v) the set of arcs with v as their tails, and by

E - D (v) the set of arcs with v as their heads. Similarly, if D is a digraph, its w-outdegree is d + w (v) = ∑ e∈E + D (v) (2w(e) -1
). Extending a result of Norine, Wong and Zhu [START_REF] Norine | Circular choosability via combinatorial nullstellensatz[END_REF] (Theorem 33), which itself extended a famous result of Alon and Tarsi [START_REF] Alon | Colorings and orientations of graphs[END_REF] (Theorem 32), we use the Combinatorial Nullstellensatz to prove that if a graph G admits an orientation D with certain property, then for any Z p -list assignment L such that |L(v)| ≥ d + w (v) + 1 for each vertex v, there is a w-circular L-colouring (Lemma 34). In particular, if D is an orientation of G that contains no odd directed cycles, then it has the required property (Theorem 34). From this we deduce that if

G is bipartite, then it is w-circular (M + 1)-choosable for M = ∑ i (2i -1)⌈Mad(G i )/2⌉
, where G i is the graph induced by the edges of weight i.

Restricted graph classes

Let G and H be two graph classes. For any parameter A in among BBC q , CBC q and CBC ℓ q , we define A(G, H ) as the maximum value of A(G, H) over all pairs (G, H) such that G ∈ G, H ∈ H and H is a subgraph of G. Let P , F and M be the classes of planar graphs, forests, and matchings respectively.

In Section 5, we consider the case when G is in P and H is in one of the three classes P , F and M . Inequality (1) and the Four-Colour Theorem imply BBC q (P , P ) ≤ 3q + 1 and CBC q (P , P ) ≤ 4q. Moreover, BBC q (G, G) = 3q + 1 and CBC q (G, G) = 4q, for any 4-chromatic planar graph G. Thus BBC q (P , P ) = 3q + 1 and CBC q (P , P ) = 4q.

Extending the celebrated planar 5-choosability proof due to Thomassen [START_REF] Thomassen | Every planar graph is 5-choosable[END_REF], Havet et al. [START_REF] Havet | Circular choosability[END_REF] proved the that if G is planar, then CBC ℓ q (G, G) ≤ 8q -3. On the other hand, they constructed planar graphs G for which

CBC ℓ q (G, G) ≥ 6q -2. Therefore, 6q -2 ≤ CBC ℓ q (P , P ) ≤ 8q -3.
But the exact value of CBC ℓ q (P , P ) is still unknown.

Problem 7. What is the exact value of CBC ℓ q (P , P ) ?

This problem is very closely related to the one posed by Mohar [START_REF] Mohar | Choosability for the circular chromatic number[END_REF].

Problem 8 (Mohar [START_REF] Mohar | Choosability for the circular chromatic number[END_REF]). What is the best upper bound on circular choosability for planar graphs?

Clearly, BBC q (P , M ) ≤ BBC q (P , F ) ≤ BBC q (P , P ) ≤ 3q + 1. However, better upper bounds have been obtained for BBC q (P , M ) and BBC q (P , F ). Havet et al. [START_REF] Havet | Circular) backbone coloring: tree backbones in planar graphs[END_REF] proved that for q ≥ 4, BBC q (P , F ) = q + 6. They also proved that BBC 3 (P , F ) ≤ 9, and conjectured the following.

Conjecture 9 (Havet et al. [START_REF] Havet | Circular) backbone coloring: tree backbones in planar graphs[END_REF] ). BBC 3 (P , F ) = 8.

Inequality 1 and the Four-Colour Theorem imply that BBC 2 (P , F ) ≤ 7. Broersma et al. [START_REF] Broersma | Backbone colorings for graphs: tree and path backbones[END_REF] showed BBC 2 (P , F ) ≥ 6 and conjectured the following.

Conjecture 10 (Broersma et al. [START_REF] Broersma | Backbone colorings for graphs: tree and path backbones[END_REF]). BBC 2 (P , F ) = 6.

Havet et al. [START_REF] Havet | Circular) backbone coloring: tree backbones in planar graphs[END_REF] showed that Conjecture 10 implies Conjecture 9.

They also proved that CBC q (P , F ) ≤ 2q + 4 and conjectured that this upper bound can be reduced by at least one.

Conjecture 11. CBC q (P , F ) ≤ 2q + 3.

It might even be possible that the bound 2q + 3 is not optimal.

Regarding matching backbones, Broersma et al. [START_REF] Broersma | λ-backbone colorings along pairwise disjoint stars and matchings[END_REF] proved that for BBC q (P , M ) = q + 3 for all q ≥ 3 and conjecture that the same holds for q = 2.

Conjecture 12. BBC 2 (P , M ) = 5.
By Equation ( 2), the fact that BBC q (P , M ) ≤ q + 3 implies that CBC q (P , M ) ≤ 2q + 2. The missing case q = 2 of this inequality was proved by Broersma et al. [START_REF] Broersma | λ-backbone colorings along pairwise disjoint stars and matchings[END_REF].

Proposition 13 (Broersma et al. [START_REF] Broersma | λ-backbone colorings along pairwise disjoint stars and matchings[END_REF]). CBC q (P , M ) ≤ 2q + 2. They also show an example for which the bound is attained for q = 2, so CBC 2 (P , M ) = 6. For larger value of q, it is sitll open if the bound 2q + 2 is best possible. Problem 14. Is is true that CBC q (P , M ) ≤ 2q + 1, for all q ≥ 3 ?

We also believe that Conjecture 11 and Proposition 13 extend to list circular backbone colouring.

Conjecture 15.

(i) CBC ℓ q (P , F ) ≤ 2q + 3;

(ii) CBC ℓ q (P , M ) ≤ 2q + 2.
In support of both parts of this conjecture, we derive from our result of Section 4, that if G is a bipartite planar graph G and F a forest in G, CBC ℓ q (G, F) ≤ 2q + 2. Observe that by (3), we have CBC q (G, F) ≤ 2q. We also show that CBC ℓ q (P , M ) ≤ 2q + 3 (Theorem 42). Our proof also uses the approach of Thomassen's 5-choosability proof [START_REF] Thomassen | Every planar graph is 5-choosable[END_REF].

2 Bounding CBC q (G, H) and CBC ℓ q (G, H)in terms of χ(G) and χ ℓ (G)

Theorem 16. Let M q (k) = 4(k 2 +1) 2 (2q-1) log 2 e 2 • 2 2k + 1. Then CBC ℓ q (G, H) ≤ M q (χ ℓ (G)) for any subgraph H of G. Proof. Because CBC ℓ q (G, H) ≤ CBC ℓ q (G, G) for any graph G, it is sufficient to prove it for CBC ℓ q (G, G). Let G be a graph such that CBC ℓ q (G, G) > M q (k). Let H be the smallest subgraph of G such that CBC ℓ q (H, H) > M q (k). Then δ(H) > M q (k)-1 2q-1 = 4(k 2 +1) 2 log 2 e 2 • 2 2k . But Alon [1] proved that if δ(G) > 4(k 2 +1) 2 log 2 e 2 • 2 2k , then χ ℓ (G) > k. Therefore χ ℓ (H) ≥ k and so χ ℓ (G) ≥ k.
We believe the bound M q (k) of Theorem 16 is far from being be tight. In particular, when H is a matching, we can get an upper bound that is a lot smaller.

Theorem 17. Let G be a graph and M a matching in G. Then

(i) CBC ℓ 2 (G, M) ≤ 2 • χ ℓ (G) + 1,
(ii) for any q ≥ 3 and any α > 1, there is

β q = β q (α) such that CBC ℓ q (G, M) ≤ 2q • α • χ ℓ (G) + β q .
INRIA In order to prove this theorem, we need some definitions. Let A and B be two sets of N or Z p . We say that A and B q-interfere if there exists a ∈ A and b ∈ B such that a = b and |a -b| < q.

For any pair of non-negative integers, we define f q (a, b) to be the smallest integer m such that for any two subsets of N of cardinality at least m, there exist two non-interfering sets

A ′ ⊂ A and B ′ ⊂ B such that |A ′ | = a, |B ′ | = b.
Similarly, let g q (a, b) be the smallest integer m such that for any p and any two subsets of Z p of cardinality at least m, there exist two non-interfering sets A ′ ⊂ A and B ′ ⊂ B such that |A ′ | = a, |B ′ | = b. These two functions are closely related.

Proposition 18. f q (a, b) ≤ g q (a, b) ≤ f q (a, b) + q -1.
Proof. If two sets q-interfere in N, then they also 2-interfere in Z r (for r sufficiently large). So f q (a, b) ≤ g q (a, b). Now let C and D be two sets in Z p of cardinality f q (a, b) + q -1, and consider A = C \ {1, . . . , q -1} and B = D \ {1, . . . , q -1}. Then |A| = |B| = f q (a, b), so there exist two sets A ′ ⊂ A and B ′ ⊂ B of cardinality a and b respectively which do not q-interfere in N. But by definition of A and B, A ′ ⊂ C, B ′ ⊂ D and they cannot q-interfere in Z p .

Let us define h q by h q (k) = g q (k, k). The function h q is useful for our purpose as shown by the following lemma.

Lemma 19. Let G be a graph, H a subgraph of G and M a matching in H. Then

CBC ℓ q (G, H) ≤ h q (CBC ℓ q (G, H -M)).
In particular, CBC ℓ q (G, M) ≤ h q (χ ℓ (G)).

Proof. Let k = χ ℓ (G). Let L be a h q (k)-list assigment in Z p . By definition of h q , for every edge uv ∈ M, we can find two k-sets L ′ (u) ⊂ L(u) and L ′ (v) ⊂ L(v) that do not 2-interfere. Since G is k-choosable, there is an L ′ -colouring c of G.

We now show that c is a q-backbone colouring of (G, M). First, for any edge xy ∈ E(G), c(x) = c(y). For any edge uv ∈ M, c(u) = c(v). In addition, since L ′ (u) and L ′ (v) do not q-interfere, |c(u)c(v)| ≥ q.

Notation For two integers a and b, we denote by [a, b] p , the set {a, a + 1, . . . , b}, where the numbers are modulo p. For every integer a, we denote by [a] p q the set [aq + 1, a + q -1] p . Very often p is either clear from the context or implicit and we omit the supercript p.

Lemma 20. (i) f 2 (a, b) ≤ a + b.
(iii) For q ≥ 3 let i * = i * (q) be the smallest integer such that (q -1)i * < 2 i * +1 -2, and set R(q) = (2q - Without loss of generality,we may assume a ≤ b. Assume a < 2 i * -1. Then one can choose any a-subset A ′ of A. It forbids at most a × 2q -2 elements to be chosen in B. So if |B| is of cardinality at least b + a + R(q) ≥ b + (2q -2)a, we can find a b-subset B ′ that does not q-interfere with A ′ .

3)2 i * -2. Then f q (a, b) ≤ 2(a + b) + R(q).
Assume now that a and b are both greater or equal to 2 i * -1.

Let x be the smallest element of A ∪ B. Without loss of generality, we may assume that x ∈ A. Consider

C 1 = A \ {x} and D 1 = B \ [x, x + q -1]. If |B ∩ [x, x + q -1]| ≤ 2,
then C 1 and D 1 are both of cardinality at least 2(a + b) + R(q) -2. Hence by the induction hypothesis, we can find an (a -1)-set C ′ in C 1 and a b-set B ′ in D 1 which do not q-interfere. Then, A ′ = C ′ ∪ {x} and B ′ are the desired sets. Hence we may assume that at least three elements of B are in [x, x + q -1].

For any k, let A(k) (resp. B(k)) be the set of the k smallest elements in A (resp. B).

Consider D 2 = B \ B(3) and C 2 = A\[x, x+2(q-1)]. If |A∩[x, x+2(q-1)]| ≤ 6,
then C 2 and D 2 are both of cardinality at least a+b+R(q)-6. Hence by the induction hypothesis, we can find an a-set A ′ in C 2 and a (b -3)-set D ′ in D 2 which do not q-interfere. Then, A ′ and B ′ = D ′ ∪ B(3) are the desired sets. (they do not interfere because B(3) ⊂ [x, x + q -1]. Hence we may assume that A(7) ⊂ [x, x + 2(q -1)].

And so on for 2

≤ i ≤ i * . If i is odd, consider C i = A \ A(2 i -1) and D i = B \ [x, x + i(q -1)]. If |B ∩ [x, x + i(q -1)]| ≤ 2 i+1 -2,
then C i and D i are both of cardinality at least 2(a + b) + R(q) -2 i+1 -2. Hence by the induction hypothesis, we can find an (a -2 i + 1)-set C ′ in C i and a b-set B ′ in D i which do not q-interfere. Then, A ′ = C ′ ∪ A(2 i -1) and B ′ are the desired sets. Hence we may assume that B( 2

i+1 -1) ⊂ [x, x + i(q -1)]. If i is odd, consider B i = B \ B(2 i -1) and C i = B \ [x, x + i(q -1)]. If |A ∩ [x, x + i(q -1)]| ≤ 2 i+1 -2, then C i and D i are both of cardinality at least 2(a + b) + R(q) -2 i+1 -2.
Hence by the induction hypothesis, we can find an a-set A ′ in C i and a (b -2 i + 1)-set B ′ in D i which do not q-interfere. Then, A ′ and B ′ = D ′ ∪ B(2 i -1) are the desired sets. Hence we may assume that A( 2

i+1 -1) ⊂ [x, x + i(q -1)].
So, depending on the parity of i * , [x, x + i(q -1)] contains at least 2 i * +1 -1 vertices of either A or B. But this is impossible, because [x, x + i(q -1)] has cardinality less than 2 i * +1 -1 by definition of i * .

Corollary 21.

(i) g 2 (a, b) ≤ a + b + 1.

(ii) for any q ≥ 3, f q (a, b) ≤ a + b + R(q) + q -1.

Remark 22. a + b + 1 may not be replaced by a + b, even if a = b, in Corollary 21 (i). Just consider a = b and Z 4a with A the set of even numbers and B the set of odd numbers. One can check that for any pair of two a-sets A ′ ⊂ A and B ′ ⊂ B 2-interfere.

Theorem 17 derives directly from Corollary 21 and Lemma 19. It can also be generalized to any subgraph H. Indeed in the very same way as Lemma 19, we can prove the following.

Lemma 23. Let G be a graph, H a subgraph of G and M a matching in H. Then

CBC ℓ q (G, H) ≤ h q (CBC ℓ q (G, H -M)).
Hence by induction, we get the following theorem, where χ ′ (H) denotes the chromatic index of H.

Theorem 24. Let G be a graph and H a subgraph of G and let q ≥ 2 be an integer.

Then CBC ℓ q (G, H) ≤ 2 χ ′ (H) q(1+ o(1))χ ℓ (G).
Remark 25. In the case q = 2, one can get rid of the o(1) term and show that CBC ℓ 2 (G, H) ≤ 2 χ ′ (H) χ ℓ (G) + 1. It suffices to observe that we can remove one fixed colour so that the colours behave like on N. Then for each matching M of a proper edge-colouring, we must divide the list by 2 so that there is no 2-interference between vertices of linked by an edge in M.

INRIA

Let G be a graph with vertex set {v 1 , . . . , Alon and Tarsi [3] applied the Combinatorial Nullstellensatz to the graph polynomial to obtain the following theorem on choosability.

v n }. The graph polynomial f G of G is defined by f G (x 1 , . . . , x n ) = ∏{(xi -x j ) | i < j, v i v j ∈ E(G)}.
Theorem 32 (Alon and Tarsi [START_REF] Alon | Colorings and orientations of graphs[END_REF]). Let D be an orientation of a graph G, and let ee(D) and oe(D) respectively the set of even and odd eulerian spanning subdigraphs of D. If ee(D) = oe(D), then for any list assignment L such that

|L(v)| ≥ d + (v) + 1 for all v, the graph G is L-choosable.
Let G be a graph with vertex set {v 1 , v 2 , . . . , v n } and let p and q be two positives integers. Its (p, q)-circular polynomial of G is

CP G p,q (x 1 , x 2 , . . . , x n ) = ∏ v j v j ′ ∈E(G) j< j ′ q-1 ∏ k=-q+1 (x j -exp(2πik/p)x j ′ ).
Let φ : {0, . . . , p -1} → C be the function defined by φ(k) = exp(2πik/p). It is obvious that a mapping c :

V (G){0, . . . , p -1} is a (p, q)-colouring of G if and only if CP G p,q (c(v 1 ), c(v 2 ), . . . , c(v n ) = 0.
Applying the Combinatorial Nullstellensatz to the (p, q)-circular polynomials, Norine, Wong and Zhu [START_REF] Norine | Circular choosability via combinatorial nullstellensatz[END_REF] established a generalization of Theorem 32, from which they deduce the following.

Theorem 33 (Norine, Wong and Zhu [START_REF] Norine | Circular choosability via combinatorial nullstellensatz[END_REF]). Suppose G is a graph and D is an orientation of G which contains no odd directed cycles. Let L be a Z p -list assignment for G such that

|L(v)| = (2q -1)d + D (v) + 1 for each vertex v. Then G is L-(p, q)-colourable.
In this section, we shall extend Theorem 33 to w-circular colouring. We will prove the following theorem.

Theorem 34. Suppose G is a graph with a positive integer edge weighting w. Suppose moreover that D is an orientation of G which contains no odd directed cycles. If L is a Z p -list assignment for G such that |L(v)|

= d + w (v) + 1 for each vertex v, then G is w-circularly L-colourable.
Let G be a graph with vertex set {v 1 , v 2 , . . . , v n }, w an edge weight of G, and p a positive integer. The (p, w)-circular polynomial of G is

CP G p,w (x 1 , x 2 , . . . , x n ) = ∏ v j v j ′ ∈E(G) j< j ′ w(v j v j ′ )-1 ∏ k=-w(v j v j ′ )+1 (x j -exp(2πik/p)x j ′ ).
Observe that when w(e) = q for all e ∈ E(G), then CP G p,w = CP G p,q . It is obvious that a mapping c :

V → Z p is a w-circular colouring of G if and only if CP G p,w (c(v 1 ), c(v 2 ), . . . , c(v n )) = 0. Let γ : Z p → C be defined as γ(l) = exp(2πil/p) for l ∈ Z p . Thus with S i = {γ(a) | a ∈ L(v i )}, the graph G is w-circularly L-colourable if and only if there exist s 1 ∈ S 1 , s 2 ∈ S 2 , . . . , s n ∈ S n such that CP G p,w (s 1 , s 2 , . . . , s n ) = 0. For any orientation D of G is considered, the degree of CP G p,w is ∑ e∈E (2w(e) -1) = ∑ n j=1 d + w (v j ).
Thus by Theorem 31, if there is an orientation D such that the coefficient of the monomial

∏ n j=1 x d + w (v j ) j is nonzero, the graph G is w-circularly L-colourable for any Z p -list assignment L such that |L(v)| = d + w (v) + 1 for all v ∈ V (G). Let D be an orientation of G. A non-negative integer mapping φ : E(D) → Z is w-consistent if 0 ≤ φ(e) ≤ 2w(e) -1 for all e ∈ E(D). It is eulerian if for every vertex v, ∑ e∈E + D (v) φ(e) = ∑ e∈E - D (v)
φ(e).

INRIA

A mapping that is consistent and eulerian is said to be nice. A mapping φ is called even (respectively, odd) if ∑ e∈E(D) φ(e) is even (respectively, odd). For an arc (v j , v j ′ ) of D of weight q and for 0 ≤ φ(e) ≤ 2q-1, the coefficient of x 2q-1-φ(e) j

x φ(e)

j ′ in ∏ q-1 k=-q+1 (x j - exp(2πik/p)x j ′ ) is equal to ∑ J⊆{-q+1,...,q-1} |J|=φ(e) ∏ j∈J (-exp(2πi j/p)) = (-1) φ(e) a φ(e) (p, q),
where

a φ(e) (p, q) = ∑ J⊆{-q+1,...,q-1} |J|=φ(e) ∏ j∈J exp(2πi j/p).
Hence it is easy to see that a w-consistent mapping φ makes a contribution to the monomial

∏ n j=1 x d + w (v j ) j
if and only if it is nice. Moreover, such a mapping contributes for an amount A(p, w, φ) = ∏ e∈E(D) a φ(e) (p, w(e)). Therefore, the coefficient of

n ∏ j=1 x d + w (v j ) j in CP G p,w is ∑ φ nice ∏ e∈E(D) ( -1) φ(e) a φ(e) (w(e)
If L is a Z p -list assignment for G such that |L(v)| = d + w (v)+1 for each vertex v, then G is w-circularly L-colourable.
Observe now that each a l (q, p) is a real because it is equal to its conjugate. We can also see that a 0 (q, p) = a 2q-1 (q, p) = 1. A result of Evans and Montgomery [START_REF] Evans | Problem 6631[END_REF] implies that if p ≥ 2q, then the values of a l (q, p), for fixed q and p, are unimodal. It follows that all values of a l (p, q) are at least 1 -Norine, Wong and Zhu proved this from first principles for certain values of p and q [START_REF] Norine | Circular choosability via combinatorial nullstellensatz[END_REF]. Lemma 36. Let p and q be two positive integers such that p ≥ 2q. For any 0 ≤ l ≤ 2q -1, a l (p, q) ≥ 1.

From Lemmas 35 and 36, we now derive Theorem 34. For a nice mapping φ, let D φ be the multi-digraph obtained from D by replacing each arc (v j , v j ′ ) by φ(e) parallel arcs from v j to v j ′ . Since φ is eulerian, then D φ is an eulerian multi-digraph. Each directed cycle of D φ corresponds to a directed cycle of D. Since D has no directed cycle of odd length, D φ has no directed cycle of odd length. Thus |E(D φ )| is even, i.e. ∑ e∈E(D) φ(e) is even. So D has no odd nice mapping, and so ∑ φ nice and odd A(p, w, φ) = 0. Now Lemma 36 implies that all the A(p, w, φ) are positive. But there is at least one nice even mapping, namely the one for which φ(e) = 0 for all e ∈ E(D). So ∑ φ nice and even A(p, w, φ) > 0.

We shall now apply Theorem 34. We need the following simple lemma which was first proved by Hakimi [START_REF] Hakimi | On the degree of the vertices of a directed graph[END_REF]. It also appears independently in several papers [START_REF] Tarsi | On the decomposition of a graph into stars[END_REF][START_REF] Alon | Star arboricity[END_REF][START_REF] Alon | Colorings and orientations of graphs[END_REF]. Lemma 37. A graph G has an orientation D with maximum outdegree at most ∆ + if and only if Mad(G)/2 ≤ ∆ + .

For a graph G and an edge weighting w, we define M(G, w) := ∑ i∈N * (2i -1)⌈Mad(G i )/2⌉, where G i is the subgraph of G induced by the edges of weight i, for all i ∈ N * .

Corollary 38. Let G be a graph and w an edge-weighting. Then G has an orientation D such that d + w (v) ≤ M(G, w) for all v ∈ V .

Proof. It suffices to orient each G i separately in such a way that the maximum outdegree is at most ⌈Mad(G i )/2⌉, which is possible by Lemma 37. The union of these orientations yields the desired one.

Theorem 34 and Corollary 38 immediately yield the following.

Theorem 39. Let G be a bipartite graph and w an edge weighting. Then G is w-circular (M(G, w) + 1)-choosable.

Proof. By Corollary 38 , G admits an orientation D such that d + w (v) ≤ M(G, w) for all v ∈ V . Since G is bipartite, it has no odd cycles and so D has no directed odd cycles. Hence by Theorem 34, G is (M(G, w) + 1)-choosable.

A stronger result for planar graphs

If G is a bipartite planar graph then Mad(G) < 4, and if T is a tree then Mad(T ) < 2. Thus, Theorem 39 directly implies the following.

Corollary 40. If G is a bipartite planar graph and T a spanning tree of G, then CBC ℓ q (G, T ) ≤ 2q + 2.

When the planar graph G is no longer required to be bipartite, we can use an acyclic orientation D with maximum outdegree 5. Such an orientation exists because a planar graph is 5-degenerate. Considering such an orientation, we derive the following, which corresponds to greedy colour according to a linear ordering extending D.

Corollary 41. Let G be a planar graph and H be a subgraph in G. Then CBC ℓ q (G, H) ≤ (2q -2)∆(H) + 6.

Proof. Let w be the edge-weight defined by w(e) = q if e ∈ E(H) and w(e) = 1 if e ∈ E(G) \ E(H). Then for the orientation D with maximum outdegree 5, we have ∆ + w (D) ≤ (2q -2)∆(H) + 5. Since D is acyclic, it contains no odd directed cycles, and so by Theorem 34, (G, w) is circular ((2q -2)∆(H) + 6)-choosable.

In particular, if G is a planar and M a matching, CBC ℓ q (G, M) ≤ 2q + 4. Using a different technique, we now prove a slightly weaker bound.

Theorem 42. Let G be a planar graph and M be a matching in G. Then CBC ℓ q (G, M) ≤ 2q + 3.

We borrow the approach of Thomassen's 5-choosability proof [START_REF] Thomassen | Every planar graph is 5-choosable[END_REF], and actually establish a slightly stronger result.

Theorem 43. Let G be a near triangulation with outer cycle C, M a matching in G and let L be a list assignment such that:

• |L(v)| ≥ 3 for all v ∈ C \ M; • |L(v)| ≥ 2q + 1 for all v ∈ C ∩ M; INRIA • |L(v)| ≥ 2q + 3 otherwise.
Then any valid precolouring of two adjacent vertices of C can be extended to a circular q-backbone L-colouring of (G, M).

To prove this theorem, we need the following lemma.

Lemma 44. Let q be a positive integer and let S and T be two sets of size 2q and 2q + 3 respectively in Z p . Then there exist two elements a and b of S such that |T \ (

[a] q ∪ [b] q )| ≥ 3.
Proof. The result holds trivially when q = 1.

Let us now prove the case q = 2. If two elements a and b of S are consecutive, then [a] 2 ∪ [b] 2 = 4, and we trivially have the result. So we may assume that the elements of S are pairwise non-consecutive. Let 1 ≤ s 1 ≤ s 2 ≤ s 3 ≤ s 4 ≤ p be the elements of S and set

I = [s 1 ] 2 ∪ [s 2 ] 2 and J = [s 3 ] 2 ∪ [s 4 ] 2 . Because the elements of S are pairwise non-consecutive, |I ∩ J| ≤ 2. But, |I ∩ T | + |J ∩ T | = |(I ∪ J) ∩ T | + |(I ∩ J) ∩ T | ≤ |T | + |I ∩ J| ≤ 9.
Hence either I ∩ T or J ∩ T has size at most 4. Therefore either s 1 and s 2 or s 3 and s 4 are the desired elements of S.

Suppose now that q ≥ 3. We prove the result by induction on p. If two elements a and b of S are consecutive (in particular if p ≤ 4q -1, then [a] q ∪ [b] q = 2q, and we trivially have the result. Thus we may assume that the elements of S are pairwise non-consecutive.

Assume now that that an element, say p, is not in S ∪ T . Then apply induction on Z p-1 with the same S and T . It is easy to see that the two elements a and b such that |T \ ([a]

p-1 q ∪ [b] p-1 q )| ≥ 3 also satisfy |T \ ([a] p q ∪ [b] p q )| ≥ 3. Let 1 ≤ s 1 ≤ s 2 ≤ • • • ≤ s 2q ≤ p be the vertices of S. For 1 ≤ i ≤ 2q-1, I i = [s i , s i+1 ] and let I 2q = [s 2q , r]∪[1, s 1 ].
Set J i = I i \ S for each i. By the above arguments, each J i contains at least one vertex of T , so at most 3 vertices are in T ∩ S. Moreover a vertex of T is in exactly one I i if it is in T \ S and in exactly two I i if it is in T ∩ S. Hence if q ≥ 4, there must be an I i such that |T ∩ I i | = 1. Then s i and s i+1 satisfy |T \ ([s i ] q ∪ [s i+1 ] q )| ≥ 3. If q = 3, then either there is an I i such that |T ∩ I i | = 1 and we get the result, or S ∩ T is one of the two sets {s 1 , s 3 , s 5 } and {s 2 , s 4 , s 6 }. In that case, one can check that |T \ (

[s 1 ] q ∪ [s 2 ] q )| ≥ 3.
Proof of Theorem 43. The proof is by induction on the number of vertices n. The result holds if G is a triangle since there is at least 3 -2 = 1 choice to colour the last vertex v if it is not matched, and at least 2q + 1 -2q = 1 choice to colour the last vertex v if it is matched. Assume now that the result is true for every near triangulation with at most n -1 ≥ 3 vertices, and let G be a near triangulation with n vertices. We let u 1 u 2 . . . u k be the outer cycle of G, and u 1 and u 2 be the two precoloured vertices with respective colours c 1 and c 2 .

Case 1: G has a chord u i u j with i < j. We use the induction hypothesis on the near triangulation whose outer cycle is u 1 u 2 . . . u i u j u j+1 , . . . , u k , u 1 . Next we use the induction hypothesis on the near triangulation whose outer cycle is u i u i+1 . . . u j u i , the two precoloured vertices being u i and u j . The result follows easily.

Case 2: G has no chord. Let v 1 , . . . , v d be the neighbours of u k that do not belong to C. Without loss of generality, we can assume that u k-1 v 1 v 2 . . . v d u 1 is a path. Set G ′ = Gu k , noting that G ′ is a near-triangulation.

We shall distinguish four cases:

•

  Proof. (i) We prove the result by induction on a + b, the result holding trivially when a = 0 or b = 0. Let x be the minimum of A ∪ B. Suppose first x ∈ A ∩ B. Let C = A \ {x, x + 1}, and D = B \ {x, x + 1}. Then |C| = |D| = a + b -2, so by the induction hypothesis, there exist two non-2-interfering sets C ′ ⊂ C and D ′ ⊂ D such that |C ′ | = a -1, |D ′ | = b -1. Setting A ′ = C ′ ∪ {x} and B ′ = D ′ ∪ {x}, we obtain the desired sets. Suppose now x / ∈ A ∩ B. Then x is only in one of these two sets, say A. Let C = A \ {x}, and D = B \ {x + 1}. Then |C| = |D| = a+b-1, so by the induction hypothesis, there exist two non-2-interfering sets C ′ ⊂ C and D ′ ⊂ D such that |C ′ | = a -1, |D ′ | = b. Setting A ′ = C ′ ∪ {x} and B ′ = D ′ , we obtain the desired sets. (ii) We prove the result by induction on a + b.

  , p) = ∑ φ nice and even A(p, w, φ) -∑ φ nice and odd A(p, w, φ). Hence, we get the following lemma. Lemma 35. Suppose a graph G has an orientation D for which ∑ φ nice and even A(p, w, φ) = ∑ φ nice and odd A(p, w, φ).

  Proof of Theorem 34. By Lemma 35, it suffices to show that ∑ φ nice and even A(p, w, φ) = ∑ φ nice and odd A(p, w, φ).

Subcase 1 :

 1 u k u 1 ∈ M. Since L(u k ) ≥ 2q + 1, there exist two colours a and b in L(u k ) \ [c 1 ] q . We define the list assignmentL ′ of G ′ by L ′ (v) := L(v) if v / ∈ {v 1 , v 2 , . . . , v d } and L ′ (v) := L(v) \ {a, b} otherwise. Then |L ′ (v i )| ≥ 2q + 3 -2 = 2q + 1 for each i.Thus we can apply the induction hypothesis to G ′ and L ′ . Now we complete the colouring of G by colouring u k with a if c(u k-1 ) = a and with b otherwise.• Subcase 2: u k-1 u k ∈ M. Since L(u k ) ≥ 2q + 1, there exist two colours a and b in L(u k ) \ {c 1 } such that [a] q ∩ [b] q = / 0. We define the list assignment L ′ of G ′ by L ′ (v) := L(v) if v / ∈ {v 1 , v 2 , . . . , v d } and L ′ (v) := L(v) \ {a, b} otherwise. Again |L ′ (v i )| ≥ 2q + 3 -2 = 2q + 1 for each i.Thus we can apply the induction hypothesis to G ′ and L ′ . Now we complete the colouring of G by colouring u k with a if c(u k-1 ) / ∈ [a] q and with b otherwise.• Subcase 3: u k is matched to v j , 1 ≤ j ≤ d. Since L(u k ) ≥ 2q + 1, by Lemma 44, there exist two colours a and b inL(u k ) \ {c 1 } such that |L(v j ) \ ([a] q ∪ [b] q )| ≥ 3. We define the list assignment L ′ of G ′ by L ′ (v) := L(v) if v / ∈ {v 1 , v 2 , . . . , v d }, L ′ (v j ) := L(v j )\([a] q ∪[b] q ) and and L ′ (v) := L(v)\{a, b} otherwise. Then |L ′ (v i )| ≥ 2q + 3 -2 = 2q + 1 for each i = j.Thus we can apply the induction hypothesis to G ′ and L ′ . Now we complete the colouring of G by colouring u k with a if c(u k-1 ) = a and with b otherwise.• Subcase 4: u k is not matched. Since L(u k ) ≥ 3, there exist two colours a and b in L(u k ) \ {c 1 }. We define the list assignmentL ′ of G ′ by L ′ (v) := L(v) if v / ∈ {v 1 , v 2 , . . . , v d } and L ′ (v) := L(v) \ {a, b} otherwise. Then |L ′ (v i )| ≥ 2q + 3 -2 = 2q + 1 for each i.Thus we can apply the induction hypothesis to G ′ and L ′ . Now we complete the colouring of G by colouring u k with a if c(u k-1 ) = a and with b otherwise.

RR n°8159

2-choosable graphs

In this section we study list backbone colouring of 2-choosable graphs.

Let t and q be two positive integers. The (t, q)-kernel of (G, H) is the maximal subset

By convention, CBC ℓ q (N, N) = 1 if N is the null graph.

Lemma 26. Let t and q be two positive integers, and let G be a graph and M a matching in G, and let K be its

Proof. Let L be an t-list assignment on G in Z r . It is easy to see that for any subgraph

can be extended into a q-backbone L-colouring of (G ′ , H ′ ). The result follows.

Lemma 26 and Theorem 6 immediately imply the following.

Corollary 27. Let G be a graph and H a nonempty subgraph of G. If the heart of G is a single vertex or an even cycle, then

Proof. Clearly, it is enough to prove it for connected graphs. So we may assume that G is connected.

Let H be the heart of G, and let

for some integer m ≥ 1, with u and v its two vertices of degree three, then G -{u, v} has three connected components. Hence H cannot have a perfect matching, and so at least two vertices of H are not matched in N, and so there is a vertex v of H such that

It follows that the (2q, q)-kernel of (G, M) is either the empty set, or a set K such that G[K] is an even cycle and M[K] a perfect matching of G[K]. Hence, by Theorem 6, CBC ℓ q (G[K], M[K]) ≤ 2q, and so by Lemma 26, CBC ℓ q (G, M) ≤ 2q.

Remark 29. In the above prove, Theorem 6 is not necessarily required as it is easy to see that CBC ℓ q (G, M) ≤ 2q for an even cycle G and a matching M.

Proof. Again it is enough to prove the statement for G connected. If H does not contain the heart of G, then one easily sees that the (2q + 1, q)-kernel of (G, H) is either the empty graph or an even cycle. Therefore Theorem 6 and Lemma 26 yield the result.

Weighted circular list colouring via the Combinatorial Nullstellensatz

In this section we shall use the following theorem, called the Combinatorial Nullstellensatz, to establish some results on circular backbone colouring.

Theorem 31. Let F be an arbitrary field, and let P = P(x 1 , . . . , x n ) be a polynomial in F[x 1 , . . . , x n ]. Suppose that the degree deg(P) of P is ∑ n i=1 t i , where each t i is a non-negative integer, and suppose the coefficient of ∏ n i=1 x t i i in P is non-zero. Then, if S 1 , . . . , S n are subsets of F with |S i | > t i , there are s 1 ∈ S 1 , . . . , s n ∈ S n so that P(s 1 , . . . , s n ) = 0. RR n°8159


Laurent Bougrain

Olivier Rochel

Octave Boussaton

Lionel Havet

From the decoding of cortical activities to the control of a JACO robotic arm: a whole processing chain

Keywords: Brain-Machine interfaces, neuroprosthetics, JACO robotic arm, OpenViBE, spike trains, grasping, monkey

This paper presents a complete processing chain for decoding intracranial data recorded in the cortex of a monkey and replicates the associated movements on a JACO robotic arm by Kinova. We developed specific modules inside the OpenViBE platform in order to build a Brain-Machine Interface able to read the data, compute the position of the robotic finger and send this position to the robotic arm. More precisely, two client/server protocols have been tested to transfer the finger positions: VRPN and a light protocol based on TCP/IP sockets. According to the requested finger position, the server calls the associated functions of an API by Kinova to move the fingers properly. Finally, we monitor the gap between the requested and actual fingers positions. This chain can be generalized to any movement of the arm or wrist.

Introduction

Brain-Computer interfaces (BCI) [START_REF] Wolpaw | Brain-computer interfaces for communication and control[END_REF] interpret brain activity to produce commands on a computer or other devices like robotic arms. A BCI therefore allows its user, and especially a severely impaired person, to interact with their environment only using their brain activity.

The main applications of BCIs are the assistance to people with motor disabilities (especially those completely paralyzed suffering from locked-in syndrome), multimedia (eg video games), and more generally the interaction with any automated system (robotics, home automation, etc.). A BCI can be described as a closed loop system (Fig. 1) consisting of six main steps:

1. recording of brain activity (electroencephalography in particular); 2. signal processing (to remove artefacts, apply a band-pass filter); 3. feature extraction (to amplify and recover useful information); 4. classification (to identify the order); 5. translation of the order into a command; 6. feedback (to provide information on the outcome of the order and/or brain activity).

More specifically, impressive results such as [START_REF] Carmena | Learning to control a brain machine interface for reaching and grasping by primates[END_REF] and [START_REF] Velliste | Cortical control of a prosthetic arm for self feeding[END_REF] exist in the neuroscience literature where the cortical activity of a monkey is used to control a complete robotic arm. More and more studies are dedicated to better understand motor control. It is now possible to decode from intracranial data the direction of a movement, the finger flexion or the muscular effort.

Following our long time study of the prediction of the finger flexion from ECoG signals [START_REF] Liang | Decoding finger flexion using amplitude modulation from band-specific ECoG[END_REF] and noninvasive BCI, we are now concerned, as part of a regional initiative1 , with the correct control of a robotic arm in a Brain-Machine Interface. Hence the necessity for a complete processing chain, we developed a solution to control a JACO robotic arm by Kinova from brain signals using the OpenViBE software2 . In section 2, we will introduce the experimental setup, the recorded data, OpenVIBE and the JACO robotic arm. Section 2.3 will present our contribution in terms of new OpenViBE modules, client/server applications and interface for controlling the JACO robotic arm. Then, in the conclusion, we will share our accumulated experience.

Material

We aim at decoding on-line intracranial data corresponding to finger movements recorded in the cortex of a monkey and replicating the movements on a JACO robotic arm by Kinova (Fig. 2). A specific OpenViBE scenario reads the cortical recordings and predicts the position of the fingers using a forecasting model. These positions are sent to an interface that translates the request into basic commands for the JACO arm to execute. Once it has done so, the exact new position is sent back to the interface as feedback and taken into account for the upcoming movements.

Dataset

We are concerned with reproducing the movement of two fingers. The recordings used in this study have been taken on a monkey (macaca nemestrina) that has been trained to perform a precision grip task.

Figure 2: Overview of the experimental setup. Open-ViBE (computer on the right side) runs on a linux system to decode intracranial data and send the finger positions to a C# interface (computer on the left side) that translates them into basic commands for the JACO using the API by Kinova. Screen captures of both computers are respectively available as figures 6 and 8.

The task of the monkey consisted in clasping two independent levers between its index finger and thumb (Fig. 3) whenever given a visual GO signal.

Figure 3: The monkey clasps two independent levers hampered by a spring between its index finger and thumb (from [START_REF] Maier | Contribution of the monkey corticomotoneuronal system to the control of force in precision grip[END_REF]).

In these experiments, 33 corticomotoneuronal cells from the hand area of the motor cortex (area 4) were recorded with glass-insulated platinum-iridium micro-electrodes (refer to [START_REF] Maier | Contribution of the monkey corticomotoneuronal system to the control of force in precision grip[END_REF] for more details about retrieving and filtering the data). Each experiment consists of sequences of neuronal activity signals, or spike trains, associated to the recorded positions of the fingers. The muscular effort of each finger is seen as a trajectory over time. See Fig. 4 for an example of the muscular activities of both fingers. The muscular effort was sampled at 500 Hz and the neuronal activity at 200 kHz, the latter has been downsampled at 500 Hz. We learn the trajectories of the two fingers separately.

Our model is based on a system of first degree linear equations involving the firing rate of the recorded neurons, a set of thresholds associated to them, some synchrony information and the averaged variation of the levers' positions [START_REF] Boussaton | Using neuronal states for transcribing cortical activity into muscular effort[END_REF].

JACO robotic arm

JACO is a robotized arm developed by Kinova 3 . It is a 6-axis robotic manipulator with a three fingered hand . This upper arm has 6 degrees of freedom in total. The arm has sensors (force, position and accelerometer) and can reach an object inside a 90 cm radius sphere at a maximum speed of 30 cm/sec. This arm can be placed on a wheelchair and is especially suitable for a person with a disability of the upper limbs. The hand itself has 3 fingers that can be used in different manners, they can be opened and closed either all together or two fingers: index finger and the thumb. Originally it is possible to use a 3 axis joystick to control the arm.

In addition, we were provided with an API by Kinova including basic instructions to interact with the JACO arm.

OpenViBE

OpenViBE is a C++ open-source software devoted to the design, test and use of Brain-Computer Interfaces [START_REF] Renard | Openvibe: An open-source software platform to design, test and use brain-computer interfaces in real and virtual environments[END_REF]. The OpenViBE platform consists of a set of software modules that can be integrated easily and efficiently to design BCI applications. The key features of the platform are its modularity, its high-performance, its connection with high-end virtual reality displays and it can sustain multiple users. The designer tool enables one to build complete scenarii based on existing software modules using a dedicated graphical language and a simple Graphical User Interface (GUI). This software is available on the INRIA Forge under the terms of the LGPL-V2 license4 .

Our processing chain allows one to control a JACO robotic arm in a variety of ways (Fig. 5). First, it is possible to use a GUI that calls the related function of the API by Kinova. Moreover, it is possible to control the robotic arm from several brain signals such as electroencephalographic (EEG) signals or cortical activities. We added specific modules to the openViBE software that have been designed to build the brain machine interface. Then two different client/server applications have been developed to send the finger position and generate the appropriate function of the API to generate an arm motion. We detail our solutions in the following subsections.

Method

OpenViBE modules

We implemented new OpenViBE modules for building a workflow that read spike trains as inputs and send JACO commands as outputs (Fig. 6)

Spike modules

The usual data type in OpenViBE is a set of digitized analog signals, corresponding to the EEG signals recorded by the BCI devices. The intracranial signals that we consider in this paper are different: they consist of a set of impulses (or spikes, corresponding to the action potentials generated by the neurons) that are recorded with a high timing precision (e.g. 5 µs).

Fortunately, a common feature in many BCI setups is to use a similar data type for representing various events (triggers, stimulations, etc.). These events can be used as a basis for encoding spike trains in OpenViBE, with a 32:32 fixed point precision. We designed a set of new OpenViBE modules to feed spike trains to the system, and subsequently analyze them, while making use of already existing modules Figure 6: Screen capture of the workflow done within OpenViBE. The OpenViBE designer allows the user to build a scenario through a graphical user interface linking processing modules (grey boxes represent our modules and white boxes the existing modules). The "CSV File Reader" module reads the intracortical data from a datafile and sends them to both the forecasting modules that predict index finger and thumb positions. Then the predicted positions are added together to obtain the distance between fingers. Finally, this value is printed on screen and sent by our client to JACO.

(e.g. channel selection, visualization) thanks to the underlying data type used.

Forecasting model

The activity of CM cells, located in the primary motor cortex is recorded in the thumb and index fingers area of a monkey. The activity of the fingers is recorded as they press two levers. We defined a forecasting model that uses a linear combination of the firing rates, some synchrony information between spike trains and averaged variations of the positions of the fingers [START_REF] Boussaton | Using neuronal states for transcribing cortical activity into muscular effort[END_REF]. This model has been implemented in an OpenViBE module.

Interfacing with JACO

By default, the JACO arm can be controlled using a joystick. Moreover, an API by Kinova was available under windows to read sensors and send commands of movement for a specific direction and a specific duration. This API provides a virtual joystick. This mode of operation does not make it possible to specify the final position of the arm. Thus, interacting with the JACO arm via the API necessitates the definition of elementary movements.

Direct control via a GUI

A Graphical User Interface (GUI) for interacting with the arm was designed (Fig. 7). The purpose of this GUI was to test the API and produce elementary movements of the arm. A sequence of discrete movements then allows the arm to move to the expected position. In order to describe larger movements, the GUI application can record and replay some sequences of tiny movements. This feature is useful for testing sequences of tiny moves produced by reinforcement learning techniques.

The API keeps on improving: it now includes support for Linux platform through Mono 5 , it is enriched with new functionalities like angular control and some latencies have been highly reduced.

5 http://www.mono-project.com

VRPN control

The VRPN protocol [START_REF] Taylor | VRPN: A deviceindependent, network-transparent vr peripheral system[END_REF] already implemented in OpenViBE is a natural candidate to control the arm. Thus, we built a VRPN client/server using predefined action IDs which can be interpreted by the JACO arm as virtual joystick commands but sent through our application. The VRPN server was attached to the PC controlling the JACO arm and a dedicated VRPN client box was created in Open-ViBE. The VRPN server was easily built upon the VRPN .Net package 6 under the MIT license. The 1.1.1 release used is although only compatible with .Net 2.0 framework and was not updated recently. In comparison, the version of the API we used complied with the .Net 3.5 framework on Windows platforms. The VPRN server was included in the GUI application defined in paragraph 3.2.1. The recording features also supports the recording of VRPN clients' commands. This VRPN setup with OpenViBE allows one to control the arm directly with available applications within OpenViBE like the P300speller [START_REF] Farwell | Talking off the top of your head: toward a mental prosthesis utilizing eventrelated brain potentials[END_REF]. For this purpose, the VRPN interface was designed with 16 commands to control the arm through a 4 by 4 speller. The commands are a subset of the discrete movements provided in the GUI: On/Off, Forward, Forward Left, Forward Right, Backward, BackwardLeft, BackwardRight, Up, Down, Left, Right, Hand / Arm control switch, LowSpeed, HighSpeed, ShortAction, LongAction.

The VRPN communication suffers from a high latency so another client/server based on TCP/IP sockets is now used between OpenViBE and the arm.

TCP/IP

In an attempt to simplify the whole processing chain we replaced the VRPN link by a custom, simpler network (TCP/IP) connection. This also permitted to reduce the latency between the OpenViBE framework and the server controlling the robotic arm, as well as to remove the dependency from the VRPN libraries. In addition, instead of a list of dedicated commands that used to correspond directly to the atomic controls of the JACO virtual joystick, the OpenViBE pipeline is now outputting a target distance for the fingers to follow. This ensure a better modularity, as we can now hide the robotics details from the BCI side.

This small shift of design also permitted to implement a better control loop on the robotics side. The software API that was available at this time 7 was indeed impaired by a high latency when using certain 6 http://wwwx.cs.unc.edu/ ~chrisv/vrpnnet 7 The newer API is known to be actually faster USB commands (Fig. 8). The significant delay we observed between the transmission of motion control and position feedback generated significant oscillations. To improve the closed loop control, we used a conventional solution in control engineering by introducing a proportional control system. This basic solution has been used waiting for the new version of the API that will reduce delays at the origin of the oscillations.

Figure 8: A variation between the requested and the actual position occurs due to transmission delays (sending of the requested position and reading of the sensors value). Here, we can observe a shift of hundreds of milliseconds.

Conclusion

We built a complete processing chain for interacting with a JACO robotic arm by Kinova. We illustrated this processing chain with decoding intracranial data recorded in the cortex of a monkey and sending the associated movements to JACO. This chain can be generalized to any movement of the arm or wrist.

In our daily work, we use OpenViBE to design Brain-Computer Interfaces and we also contribute to its development. Usually, this software interacts with virtual reality applications using the VRPN protocol. So we had to implement a VRPN client/server to send motion commands to JACO via a API by Kinova. We observed a substantial latency between the JACO and openViBE. Thus, we developed another client/server based on TCP/IP sockets that speeded up the whole computation. Here, simplicity is more profitable than powerful but poorly controlled bricks (VRPN). Another difficulty is that the JACO arm has been designed to be controlled using a joystick. This mode of operation forced us to define elementary movements when using the API by Kinova with input data coming from openViBE. Moreover, the usual data type in OpenViBE is a set of digitized analog signals. This format is not appropriate for spike trains. But the modularity of OpenViBE allowed us to easily define our specific format. Finally, when you push software a little outside their comfort zones as we did here using OpenViBE with non standard data and another output protocol, modularity proves its worth.

In the future, the closed loop control can be improved using the new version of the API which reduces transmission times and using a better PID controller that carries an identification of the dynamics of the fingers. This work will be continued through a realtime control of the JACO using noninvasive EEG signals acquisition systems.

Figure 1 :

 1 Figure 1: Brain-Computer Interface loop : from brain imaging, feature extraction and classification to feedback.

3Figure 4 :

 4 Figure 4: Coordinated finger movements in millimeters, obtained for the index finger (at the top) and thumb (bottom). This is a 25 seconds excerpt of a 21 minutes recording.

Figure 5 :

 5 Figure 5: This diagram shows the different parts that we developed to allow the control of a JACO robotic arm. Our contributions can be gathered in two parts: OpenViBE modules and JACO's interfaces. Elements in bold indicate the solution that we finally selected for this experiment.

Figure 7 :

 7 Figure 7: A screen capture of our GUI that allows the user to control the robotic arm via the API by Kinova.

PRST MISN/Situated Informatics (http://infositu. loria.fr)

http://openvibe.inria.fr

http://openvibe.inria.fr

Acknowledgment

This work has been supported in part by grants from PRST MISN (Région Lorraine/INRIA). This work has been supported in part by CNRS-PIR-Neuro-IC 2010 (Project CorticoRobot). The authors are very thankful to R. Lemon and M. Maier for providing the data set to us. The authors would like to thank Baptiste Payan for his expertise and technical support on OpenViBE.