Reza Naserasr

Lan Anh Pham

Complex and homomorphic chromatic number of signed planar simple graphs

Keywords:

We introduce the notion of complex chromatic number of signed graphs as follows: given the set C k,l = {±1, ±2, . . . , ±k} ∪ {±1i, ±2i, . . . , ±li}, where i = √ -1, a signed graph (G, σ) is said to be (k, l)-colorable if there exists a mapping c of vertices of G to C k,l such that for every edge xy of G we have

The complex chromatic number of a signed graph (G, σ), denoted χ com (G, σ), is defined to be the smallest order of C k,l such that (G, σ) admits a (k, l)-coloring.

In this work, after providing an equivalent definition in the language of homomorphisms of signed graphs, we show that there are signed planar simple graphs which are not 4-colorable. That is to say: there is a signed planar simple graph which is neither (2, 0)-colorable, nor (1, 1)-colorable, nor (0, 2)-colorable. That every signed planar simple graph is (2, 0)-colorable was the subject of a conjecture by Máčajová, Raspaud and Škoviera which was recently disproved by Kardoš and Narboni using a dual notion. We provide a direct approach and a short proof. That every signed planar simple graph is (1, 1)-colorable is a recent conjecture of Jiang and Zhu which we disprove in this work. Noting that (0, 2)-coloring of (G, σ) is the same as (2, 0)-coloring of (G, -σ), this proves the existence of a signed planar simple graph whose complex chromatic number is larger than 4.

Further developing the homomorphism approach, and as an analogue of the 5color theorem, we find three minimal signed graphs each on three vertices, without a K ± 1 (a vertex with both a positive and a negative loop) and each having the property that admits a homomorphism from every signed planar simple graph. Finally we identify several other problems of high interest in colorings and homomorphisms of signed planar simple graphs.

Introduction

A signed graph (G, σ) is a graph (allowing multi edges and loops) together with an assignment σ of signs (i.e. + or -) to the edges of G. The sign of a structure in (G, σ) (such as a subgraph, a walk, etc) is the product of the signs of all of its edges considering multiplicity. Of particular importance are the signs of cycles and closed walks which are invariant under the switching operation defined next.

A switching of a signed graph at a vertex x is to switch signs of all edges incident with x. A switching of (G, σ) is a collection of switchings at each of the elements of a given set X of vertices (which is equivalent to switching of signs of all edges in the edge-cut formed by X and its complement). A digon in a signed graph is a cycle of length 2 where one edge of this cycle is positive and the other edge is negative. A loop of a signed graph is an edge such that its two endpoints are the same. Thus, in particular, a switching at a vertex incident with a loop e is considered as switchings at both ends, and, hence, does not change the sign of e. We use (G, +) (respectively, (G, -)) to denoted a signed graph on G where all edges are positive (negative). A signed graph (G, σ) which is switching equivalent to (G, +) (respectively, (G, -)) is called balanced (respectively, antibalanced ).

Extending the notion of proper colorings of graphs, a notion of (proper) coloring of signed graphs was introduced by T. Zaslavsky in [START_REF] Zaslavsky | Signed graph coloring[END_REF]. That is a coloring c of vertices where colors are (nonzero) integers such that c(x) = σ(xy)c(y) for each edge xy. Various directions of study and extensions of this notion of proper coloring of signed graphs have been recently introduced. Here we propose the following extension which has been developed as a natural optimization problem from the study of homomorphisms of signed graphs.

Definition 1. Given the set C k,l = {±1, ±2, . . . , ±k} ∪ {±1i, ±2i, . . . , ±li}, where i = √ -1, a signed graph (G, σ) is said to be (k, l)-colorable if there exists a mapping c of the vertices of G to C k+l such that for every edge xy of G we have c(x)c(y) = σ(xy)|c(x) 2 |.

Observe that a vertex with both a positive loop and a negative loop admits no complex coloring. This is analogue of the fact that graphs with loop do not admit a proper coloring. For a signed graph (G, σ) which does not contain such a vertex, the complex chromatic number of it, denoted χ com (G, σ), is defined to be the smallest order of a C k,l such that (G, σ) admits a (k, l)-coloring. After defining the notion of homomorphism of graphs and signed graphs in the next section, we will see that this is the most natural extension of chromatic number of graphs to chromatic number of signed graphs from a homomorphism point of view: both are about finding the smallest homomorphic image in absence of a trivial mapping.

We remark two important properties of the complex chromatic number of signed graphs. First is that it is independent of a switching. More precisely, if φ is a (k, l)coloring of (G, σ) and (G, σ ) is obtained from (G, σ) after a switching at a vertex x, then by changing the color of x to -φ(x), while keeping all other colors the same, we have a (k, l)-coloring of (G, σ ). The second is the following observation:

Observation 2. A signed graph (G, σ) is (k, l)-colorable if and only if (G, -σ) is (l, k)- colorable.
More precisely, if φ is a (k, l)-coloring of (G, σ), then iφ is an (l, k)-coloring of (G, -σ).

Homomorphisms and coloring

Given two signed graphs (G, σ) and (H, π), a homomorphism of (G, σ) to (H, π) is a mapping f which maps the vertices and the edges of G to the vertices and the edges of H (respectively) with the property that all incidences are preserved and, moreover, signs of closed walks are preserved as well. An edge-sign preserving homomorphism of (G, σ) to (H, π) is a mapping f which maps the vertices and the edges of G to that of H such that preserves incidences, adjacencies and signs of edges. The following theorem shows a strong connection between these two notions (see [START_REF] Naserasr | Homomorphisms of signed graphs: an update[END_REF] for a proof and more on homomorphisms of signed graphs). Theorem 3. A signed graph (G, σ) admits a homomorphism to a signed graph (H, π) (i.e (G, σ) → (H, π)) if and only if there is a switching σ of σ and an edge-sign preserving homomorphism of (G, σ ) to (H, π).

This shows that the notion of homomorphisms of signed graphs extends the notion of homomorphisms of graphs because a homomorphism of (G, +) to (H, +) is the same as a homomorphism of G to H. One may easily observe that the chromatic number of a graph without a loop is the number of the vertices in a smallest homomorphic image without a loop. Let (K ± 1 ) be the signed graph on one vertex whose edge set consists of one positive and one negative loop. Observing that every signed graph admits a homomorphism to (K ± 1 ), and that this is the only minimal signed graph with this property, we consider the following natural definitions:

Given a signed graph which does not contain (K ± 1 ), we define the homomorphism chromatic number of a signed graph (G, σ), denoted χ hom (G, σ), to be the smallest number of the vertices in a homomorphic image of (G, σ) which does not contain (K ± 1 ). We now show that the homomorphism chromatic number and complex chromatic are almost the same concepts.

Theorem 4. For any signed graph without a (K ± 1 ) we have χ com (G, σ) = 2χ hom (G, σ).

Proof. Let K k-,l+ be the complete complex signed graph on a set X ∪ Y of k + l vertices where X = {x 1 , . . . , x k } is a set of order k and Y = {y 1 , . . . , y l } is a set of order l. Edge set of K k-,l+ consists of: a negative loop at every vertex of X, a positive loop at every vertex of Y and a digon connecting any pair of distinct vertices. We claim that a (k, l)-coloring of (G, σ) is equivalent to a homomorphism of (G, σ) to K k-,l+ . Given a (k, l)-coloring φ of (G, σ), if a vertex v colored +p, then we map v to the vertex x p , if a vertex u is colored -p, then we first apply a switching at u and then map it to x p . Similarly, we map the vertices colored qi or -qi to y q . It is easily verified that this is a one to one correspondence between (k, l)-colorings of (G, σ) and homomorphisms (G, σ) to K k-,l+ .

The claim of the theorem now follows: Suppose χ com G = 2(k + l) and that (G, σ) admits a (k, l)-coloring. Then K k-,l+ is a signed graph on k + l vertices with no (K ± 1 ) to which (G, σ) admits a homomorphism, therefore,

χ com (G, σ) = 2(k + l) ≥ 2χ hom (G, σ).
On the other hand, let (H, π) be a homomorphic image of (G, σ) with the smallest possible number of vertices and assume |v(H)| = p. Then, observing that parallel edges of a same sign are of no importance, one may add edges to (H, π) without creating a (K ± 1 ) until it becomes a K k-,l+ for a choice of k and l (thus p = k + l). Then the given homomorphism of (G, σ) to (H, π) can now be viewed as a homomorphism of (G, σ) to K k-,l+ , proving that (G, σ) admits a (k, l)-coloring. Hence,

χ com (G, σ) ≤ 2(k + l) = 2χ hom (G, σ).
In particular, a signed graph without (K ± 1 ) has complex chromatic number at most 4 if and only if it admits a homomorphism to one of the three signed graphs of Figure 1. (In Figures of this work a blue or solid edge represents a positive edge and a red or dotted edge represents a negative edge). More precisely, the digon with two negative loops D -(left) corresponds to (2, 0)-coloring, the digon with two positive loops D + (middle) corresponds to (0, 2)-coloring and the one with one positive and one negative loop D ± (right) corresponds to (1, 1)-coloring. A comprehensive study of the complex chromatic number then is under way in a joint work with Weiqiang Yu. In this work, we have a look at maximum possible complex chromatic number of signed planar simple graphs. That all signed planar simple graphs are (2, 0)-colorable was the subject of a conjecture by Máčajová, Raspaud and Škoviera [START_REF] Máčajová | The chromatic number of a signed graph[END_REF]. Kardǎnd J. Narboni [START_REF] Kardoš | On the 4-color theorem for signed graphs[END_REF], based on the notion of dual, provided an edge-coloring interpretation of this conjecture, and then, using examples of non-hamiltonian cubic birdgeless planar graphs, disproved the conjecture. Here, we give a direct approach to the problem. Our proof becomes simpler because of the choice of the signature on the gadgets and it leads to families of counterexamples.

That every signed planar simple graph is (1, 1)-colorable is a recent conjecture of Jiang and Zhu [START_REF] Jiang | X. 4-colouring of generalized signed planar graphs[END_REF]. Indeed they have the first step toward introducing the notion of complex coloring of signed graphs. We disprove this conjecture by building a counterexample using similar techniques.

Combined together, these results can be viewed as an existence of a signed planar simple graph whose vertices cannot be partitioned into two parts, each part inducing either a balanced subgraph or an antibalanced subgraph.

Thus, turning our attention to signed graphs on three vertices, we identify three minimal signed graphs on at most three vertices to which every signed planar simple graph admits a homomorphism. This answer the question of "whether a given signed graph (B, π) on at most three vertices bounds the class of signed planar simple graphs" for all but essentially one choice of (B, π) (see Figure 15). One of the main tools in our constructions is the dual of what is known as the Tutte fragment. Considering the classic relation between vertex-coloring and edge-coloring of planar graphs (first shown by Tait in 1890), using the dual of Tutte fragment in coloring problems is not a surprise. For a recent use of this gadget, we refer to [START_REF] Kemnitz | A note on non-4-list colorable planar graphs[END_REF] where the gadget is referred to as the Wenger graph. We note that a strong connection between (2, 0)-coloring and special types of 4-list coloring is established in [START_REF] Zhu | A refinement of choosability of graphs[END_REF].

The gadgets

The construction of the counterexamples is based on several gadgets. We first provide small gadgets to force three vertices of a facial triangle to be multicolored.

Observe that in any {2, 0}-coloring, the vertices of (K 3 , -) can all be colored with a same color. However, as a face of a signed planar graph, we may prevent this by completing the face to a configuration of Figure 2.

Lemma 5. In any {2, 0}-coloring of the graph of Figure 2, the three vertices x, y and z cannot all receive a same color.

Proof. If ϕ(x) = ϕ(y) = ϕ(z) = 1 (or ϕ(x) = ϕ(y) = ϕ(z) = -1)
, then non of u, v and w can be colored +1 or -1. Thus only two colors ±2 can be used on them, but they must receive pairwise distinct color, a contradiction.

Meanwhile, in any {1, 1}-coloring, not only the vertices of (K 3 , -) can all be colored with a same color (e.g.,+1) but also the vertices of (K 3 , +) can all be colored with a same color (e.g.,+i). But similar to the previous lemma, as a face of a signed planar graph, we can prevent this by completing the face to the corresponding configuration of Figure 3 or Figure 4. Lemma 6. In any {1, 1}-coloring of the graph of Figure 3 (or Figure 4), the three vertices x, y and z cannot all receive a same color.

Proof. We will prove that for any (1, 1)-coloring, the three vertices x, y and z of the graph of Since xyz is the negative triangle, x, y, z cannot all receive a same color a ∈ {i, -i}.

If ϕ(x) = ϕ(y) = ϕ(z) = 1 (or ϕ(x) = ϕ(y) = ϕ(z) = -1)
, then non of u, v and w can be colored +1 or -1. Thus only two colors ±i can be used on them, but uvw is a negative triangle, a contradiction.

Remark:

(1) In any (2, 0)-coloring, considering possible switchings of the signed graph of Figure 2, a general statement is to say that vertices x, y and z cannot all receive colors with a same absolute value. It is immediate from the definition that in any (2, 0)-coloring, three vertices of any positive facial triangle cannot all receive colors with a same absolute value;

(2) Applying the statement of Lemma 6 to possible switchings of a triangle, we may conclude that in any (1, 1)-coloring of a facial triangle, one may prevent the use of colors {a, -a} on all three vertices.

Thus from here on, whether we are working on a (2, 0)-coloring or a (1, 1)-coloring, we may assume that the vertices of a facial triangle are not all colored by two colors a and -a. We will refer to this as the triangle property.

Next we build our main gadgets that are based on Wenger graph.

Lemma 7. In a (2, 0)-coloring c of the graph of Figure 5 which satisfies the triangle property, we cannot have c(u) = -c(v).

Proof. Observe that there are two negative faces in this graph, they are: ux 1 x 2 and vx 3 x 4 . Toward a contradiction, assume c is (2, 0)-coloring of this graph where on each of these two negative faces both absolutes values 1 and 2 are used and suppose, without loss of generality, c(u) = 1 and c(v) = -1. We then consider list of available colors at each vertex. At z and t the only available colors are ±2, at x i , for i = 1, 4, 5, the list of available colors is {-1, ±2} and at x i , i = 2, 3, the list of available colors is {+1, ±2}. Currently all colors are available at w, but we claim that its color cannot be ±1. If w is colored -1 then the positive triangle x 4 x 5 t must be properly colored using only ±2, and if w is colored +1, then the positive triangle x 2 x 3 z will face the same problem.

Thus w has to be colored by ±2. As non of the two colors are used yet, and by symmetry among the two colors, assume w is colored -2. Then on the 5-cycle x 1 x 2 x 3 x 4 x 5 each vertex has a list of two available colors: +2 together with either +1 or -1. Furthermore,

w x 1 x 2 x 3 x 4 x 5 z t u v - - Figure 5:
Gadget to forbid opposite colors on two vertices on the edge x 1 x 2 color +2 must be used (at least) once because of the negative face ux 1 x 2 (recall that u is colored 1). Similarly, because of the negative face on the edge x 3 x 4 , the color +2 must be used once. Thus colors ±1 cannot appear on an edge of the 5-cycle, and, therefore, coloring |c| induces a proper 2-coloring of this 5-cycle, a contradiction.

Remark. We presented a simplest form of a signature and used symmetric presentation in our proof. However, one can modify this gadget and still have a similar property. For example, one may change the sign of one of the edges tx 4 or tx 5 and then add the gadget of Figure 2 inside x 4 x 5 t to get a same result. Similarly, if we change the sign of ux 1 and apply triangle property to the face ux 1 x 5 instead of ux 1 x 2 , then we have a similar property.

w x 1 x 2 x 3 x 4 x 5 z t u v Figure 6: Signed graph H 1 w x 1 x 2 x 3 x 4 x 5 z t u v Figure 7: Signed graph H 2
In any (k, l)-coloring c of (G, σ), and for a color a ∈ C k,l we define an a-monochromatic subgraph to be the subgraph induced by the vertices that are colored a or -a.

A crucial but straightforward fact is that:

Observation 8. In any (k, l)-coloring c of (G, σ) an a-monochromatic subgraph cannot contain a negative even closed walk. This concludes the claim of the lemma.

The gadget H 2 of the Figure 7 holds a similar property, as its proof is quite similar to the proof of the previous one, we omit the details.

Lemma 10. Given a (1, 1)-coloring c of the signed graph H 2 of Figure 7 satisfying triangle property, if an a-momochromatic subgraph (H , σ) contains both u and v, then it contains a negative 5-cycle with uv as part of it.

Complex chromatic number of signed planar simple graphs

Using the gadgets we have introduced we may now build signed planar simple graphs that are not (2, 0)-colorable, (1, 1) and (2, 0)-colorable. Putting disjoint copies of them together we get a signed planar simple graph whose complex chromatic number is 6 (or 5 depending on if we allow 0 as a color or not).

4.1 A simple planar signed graph which is not (2, 0) (2, 0) (2, 0)-coloring

Using the gadget in Lemma 7, one can transform a given planar signed graph which has no loop, but may contain digons, and accepts no (2, 0)-coloring into a simple planar signed graph which is not (2, 0)-colorable.

Definition 11. Let (G, σ) be a planar signed (multi) graph with no loops. Define F (G, σ) to be the following simple signed graph. For each pair u, v of vertices, if they are adjacent with more than one edge of a same sign, delete all but one of them. If u and v are adjacent with one positive and one negative edge, then delete the negative uv-edge, and add to the graph a copy F uv of the graph of Figure 5, where each of the two negative triangles are completed by (a switched copy of) the configuration of Figure 2.

Using Lemma 7, we immediately have the following.

Proposition 12. Given a planar signed (multi) graph (G, σ) with no loop, (G, σ) is (2, 0)-colorable if and only if the signed planar simple graph

F (G, σ) is (2, 0)-colorable.
Thus, to build a planar simple graph which is not (2, 0)-colorable, it would be enough to build one with no loop, but allowing digons, which is not (2, 0)-colorable. The easiest and smallest such a construction is to replace each edge of the triangle by a digon (see Figure 8). The simple planar signed graph obtained from this three vertices graph by replacing each negative edge with a gadget of the Figure 5 has 45 vertices. However, there is a face of size 6 in this graph where all edges are positive. One may identify three vertices of this cycle to get an example of simple planar signed graph on 43 vertices which is not (2, 0)-colorable. One may build an example with fewer vertices using the signed graph on the right side of Figure 9. After minimizing the facial cycle of the resulting graph, we have examples on 39 vertices. This is the same order as the smallest graph given in [START_REF] Kardoš | On the 4-color theorem for signed graphs[END_REF], but we note that first of all there is no proof given for the smaller example in [START_REF] Kardoš | On the 4-color theorem for signed graphs[END_REF], and, secondly, that our construction gives several non isomorphic copies, depending on two factors: The possible signature we choose on our gadget, and the choices we have for a vertex of a digon to be the vertex u of the gadget or the vertex v of it. • c(u) = 1 and c(v) = -1. In this case, x 2 and x 3 can only use colors ±2, but they also form a digon.

Thus, without loss of generality, we may assume c(u) = 1 and c(v) = 2. We now claim that on each of the (positive) edges of the 5-cycle x 1 x 2 x 3 x 4 x 5 the coloring c must use two different absolute values, but this would result in a 2-coloring of this odd-cycle, which is not possible. Observe that all these five vertices are adjacent to u by a positive edge thus non of them can be colored 1. Hence, to prove our claim, it would be enough to show that non of the five edges receive colors +2 and -2. This is the case for edges x 2 x 3 and x 4 x 5 because they are part of a digon. Edges x 1 x 5 and x 3 x 4 each together with v form a configuration of Figure 2, and as c(v) = 2, this is the claim of Lemma 5. For the last edge, x 1 x 2 , since each end is adjacent to v by a positive edge, there can be no color +2 on these two vertices.

A simple planar signed graph which is not (1, 1) (1, 1) (1, 1)-coloring

Let H be the signed planar graph obtained from disjoint copies of H 1 of Figure 6 A signed planar simple graph which is not (1, 1)-colorable is now built by replacing the three edges of a triangle each with a copy of H. To calculate the order of the graph that is constructed, we note that for the gadget H i (i = 1, 2) to work we need eleven of its faces to have the triangle property. Thus each H i has 43 vertices, and H has 84 vertices. The final graph then has 249 vertices. One can get an example with a few more vertices by identifying some vertics, but it would be of interest to build a substantially smaller example.

Minimal homomorphism bounds

It follows from the definition of the complex coloring that given a (k, l)-partial coloring c of a signed graph (G, σ), the color c(v) of a neighbor v of a vertex u forbids only one color on u. Thus, it follows that if G is d-degenerate for d < 2(k +l), then (G, σ) admits a (k, l)coloring. Thus, in particular, every signed planar simple graph admits a (3, 0)-coloring, a (2, 1)-coloring, a (1, 2)-coloring and a (0, 3)-coloring.

These claims can be regarded as analogue of the 6-color theorem for planar graphs and can be strengthened to what one might think of as analogue of the 5-color theorem for planar graphs. We will give a short proof using a strong result of Borodin that every planar graph is acyclically 5-colorable. But we will point out in Section 6 at that one may prove the results directly using techniques similar to the known proofs of the 5-color theorem.

Given a signed planar simple graph (G, σ), we consider an acyclic 5-coloring of G and let V 1 , V 2 , V 3 , V 4 and V 5 be the color classes. Since V 1 ∪ V 2 induces a forest, one may apply a switch on this subset of vertices to have all induced edges of a same sign (of our choice) and then map all vertices to a vertex with one loop. After doing the same to V 3 ∪ V 4 , one may map vertices in V 5 to a single vertex (with no loop). This implies that each of the three graphs of Figure 10 is a homomorphism bound for the class of signed planar simple graphs, or even for the larger class of signed graphs whose underlying graph admits a 5-acyclic coloring. We claim here that each of these three signed graphs of Figure 10 is minimal homomorphism bound for the class SP of signed planar simple graphs.

To see that, observe that if we remove one of the vertices, we either get one of the graphs of Figure 1 or a subgraph of one of them which we have already shown cannot bound SP. If in T --or T ++ we delete any of the edges that is not a loop, or delete an edge incident with z in T +-, the result then maps to one of the three graphs of Figure 1 and we have already seen that they cannot bound the class of all signed planar simple graphs. Thus, up to symmetries and isomorphism, we have two cases to consider: Removing one of the loops, thus we have the graph T -of Figure 11, we will build a signed planar simple graph (G, σ) which does not map to T -and we note that if we have a positive loop instead then (G, -σ) works. The other case is T (depicted in Figure 12) which is obtained from T +-by removing one of the two xy edges. Note that the two resulting signed graphs are switching equivalent. We will also build an example of signed planar simple graph that does not map to T .

Mapping to T -

Let T -be the signed graph obtained from the signed graph on the left of Figure 10 by removing the loop on the vertex y. It is not difficult to show that a signed graph (G, σ) maps to T -if and only if (G, σ) admits a coloring by the elements of Z 4 satisfying c(x) -σ(xy)c(y) = 0 where the operation are taken (mod 4). Disproving a conjecture of Kang and Steffen, Zhu [START_REF] Zhu | A refinement of choosability of graphs[END_REF] built a signed planar simple graph which does not admits a Z 4 -coloring. However, since we have already built the main gadgets, and to highlight the homomorphism properties of T -, we give the following construction.

Observe that if a signed graph (G, σ) maps to T -, then V (G) is partitioned into two sets V 1 and V 2 such that V 1 (set of the vertices that are mapped to x) induces an antibalanced signed graph and V 2 (set of the vertices that are mapped to y or z) induces a signed bipartite graph. Thus to build a signed planar simple graph which does not map to T -it would be enough to build one for which in any 2-coloring of vertices we have:

• either a monochromatic positive odd cycle, or • a monochromatic negative odd cycle in each color, or • a monochromatic negative even cycle in each color.

Toward building an example which satisfies the property, we may again use the gadget of Figure 2 to assume that in every 2-coloring of our signed planar simple graphs the triangle property holds, otherwise we would have a monochromatic positive triangle, but T -has no positive loop.

We then consider the following variation of Lemma 9 which is easily verified by modifying the proof: Lemma 15. Given 2-coloring c of the signed graph H 1 of Figure 6 satisfying triangle property, if c induces no monochromatic positive odd cycle and if c(u) = c(v) = a, then the color a induces a monochromatic negative even cycle.

We may now build a signed planar simple graph (G, σ) which does not map to T -. Start with a planar embedding of (K 4 , +) and for each edge xy of it add a copy of H 1 where x is identified with u, y is identified with v and xy is replaced by the edge uv. Let c be a 2-coloring of (G, σ). We claim that one of the three conditions will hold. If three vertices of the original K 4 are colored the same, then we already have a positive triangle. Else, of the four vertices two are colored a and the other two are colored b. Applying Lemma 15 on the copy of H 1 corresponding to two vertices colored a, we get a negative even cycle all whose vertices are colored a. Applying it on the other two vertices, we get a negative even cycle all whose vertices are colored b. This completes the proof of our claim.

Mapping to T

Let T be the singed graph obtained from T +-by removing the negative xy-edge, see Figure 12 for a depiction. We will use the fact that remaining xy-edge in T is a positive edge and build a signed planar simple graph (G, σ) which dones not map to it. We note that a switching at x would change sign of xy-edge to negative and thus our example would also not map to T +--e if e was the positive xy-edge. The following observation is the key tool in building a signed planar simple graph which does not map to T . Lemma 16. A signed positive triangle admits an edge-sign preserving homomorphism to the subgraph of T induced by {x, y} if and only if all its edges are positive.

Proof. That is because there are two essentially different signatures on a positive triangle. Either all the edges are positive in which case we must map two of the vertices to y and the third is free to map to x or y. Or there are two negative edges, in this case as the only negative edge on the subgraph induced by x and y is the negative loop on x, all vertices must be mapped to x, but that would create a positive loop at x.

To build a signed planar simple graph which does not map to T , we first consider the signed outer planar graph (G, σ) of Figure 13. We show that: Proof. Assume to the contrary that (G, σ) maps to T -z. Then there is a switching σ of σ under which (G, σ ) admits an edge-sign preserving mapping to T -z. In such a signature, by Lemma 16, each of the positive triangles suv, tvw and rwu must consist of only positive edges, but then the triangle vuw is a positive triangle in (G, σ ), however as it is a negative triangle in (G, σ), σ cannot be a switching of σ.

In other words, in any mapping of (G, σ) to T at least one vertex should be mapped to z. Let (G, σ) * be the signed graph obtained from (G, σ) by adding a twin copy s , t , r of s, t, r (respectively) and adding edges ss , tt and rr , see Figure 14. Observe that, in a mapping of (G, σ) * of T , of the pair s, s at most one can be mapped to z. If non of u, v, w is mapped to z, then we will have a copy of (G, σ) which is mapped to T -z, contradicting Lemma 17.

To complete the construction, we may now consider a planar embedding of (K 4 , -) and for each edge uv of it, add two new vertices s uv and s uv . Then connect both of them to one of u and v with positive edges, and to the other with negative edges. Finally, connect s uv to s uv (of any sign, but say with a positive sign to have isomorphic copies of Figure 14). Observe that, on each triangle of (K 4 , -) we have built a copy of (G, σ) * . We claim that this signed planar simple graph does not map to T . That is because at most one of the four vertices of K 4 can map to z, hence, there is a triangle of (K 4 , -) non of whose vertices is mapped to z, the subgraph isomorphic to (G, σ) * built on this triangle then would lead to a contradiction. The example then has 16 vertices.

Remaining three vertices signed graphs

Based on the previous discussion for all but two singed graphs on three vertex we know if they bound the class of signed planar simple graphs. These two are depicted in Figure 15 and Figure 16. Here, strengthening constructions of Section 4, we show that the signed graph T 2 on the right of the figure also does not bound the class SP, leaving only one unsolved case among 3 vertices signed graphs.

Theorem 18. There exists a signed planar simple graph which does not map to the signed graph T 2 of Figure 16.

To prove this theorem, we will view a T 2 -coloring of a signed graph (G, σ) as a 2coloring, using colors c 1 and c 2 where vertices mapped to x are colored c 1 and vertices Let (G, σ) be a planar graph and assume that it admits a T 2 -coloring. Let c be the corresponding 2-coloring. Then applying the gadget of Figure 4 on each of the positive facial triangle of (G, σ) we either build a sign planar simple graph which does not map to T 2 , or we are assured that no facial positive triangle of (G, σ) is monochromatic under c. To obtain a similar conclusion of facial negative triangles we need an extension of our gadgets depicted in Figure 17. Proof. We consider the two cases separately. Suppose u, v and w are colored c 1 (i.e., they are mapped to vertex x in T 2 -coloring). Then, since uvs is a positive triangle, s, and similarly r and t, are colored c 2 . But then we have a monochromatic positive triangle on which we have the construction of Figure 4. Now suppose u, v and w are colored c 2 (i.e., they are mapped to either y or z in T 2coloring). Since they induce a connected subgraph, they all must map to a same vertex of T 2 and as they induce a negative triangle, they all must map to z. Then, by similar arguments, vertices s, r and t all must be mapped to vertex x of T 2 , however they induce a positive triangle.

We now consider the gadgets H 1 and H 2 of Figure 6 and Figure 7 where each facial triangle, depending on its sign, is either completed to a (possibly a switching equivalent) copy of the signed graph of Figure 4, or Figure 17. This ensures that in any 2-coloring corresponding to a T 2 -coloring of these graphs the triangle property can be enforced. The construction of a signed planar simple graph that does not map to T 2 is then completed as in Section 4.2. The signed graph H obtained from H 1 and H 2 by identifying the uv edge has property that in any 2-coloring satisfying triangle property, if u and v are coloring the same, then there is a monochromatic negative even cycle. The construction then is completed by using three copies of H where edges corresponding to uv form a triangle.

Concluding remarks

In this work, we have first of all introduced the notions of complex-coloring and complexchromatic number of signed graphs which extend the notion of 0-free coloring of signed graphs introduced by T. Zaslavsky. We will show in forthcoming works that the notion is of high interests on its own, for example we show that the problem of finding the largest possible complex chromatic number on a given complete graph is strongly related to the Ramsey numbers.

We have shown that the concept is a natural optimization problem from a homomorphism point of view. And then we showed that signed planar simple graphs may need more than 4 colors. Here, we have only considered (k, l)-colorings which are extensions of 0-free colorings. One could analogously allow 0 to be in the set of colors. Then the set of the vertices colored 0 must induce an independent set of the graph. This, similar to the work of [START_REF] Máčajová | The chromatic number of a signed graph[END_REF], would allow for the complex chromatic number to be an odd integer as well. That signed planar simple graphs are 5-colorable with this definition is already observed.

From a homomorphism point of view, we determined three minimal graphs on three vertices each of which bounds the class of signed planar simple graphs. In analogy to the coloring of planar graphs (not signed), our results say that four colors are not enough for coloring all signed planar simple graphs but five colors are enough. We used the fact that planar graphs are acyclically 5-colorable to prove that each of these three signed graphs indeed bounds the class of signed planar simple graphs, but we would like to point out that the techniques for proving the 5-color theorem works here as well and one does not really need the acyclic coloring result. We give a bit more details for mapping of to T --, the other two are similar.

To map a signed graph (G, σ) to T --, one must find a switching σ of σ after which (G, σ ) admits an edge-sign preserving mapping to T --. However, if a vertex v is mapped to z, then a switch at v would not affect the homomorphism properties. Thus for each vertex v of (G, σ) we have five possibilities: 1. map it to z, 2. switch and map it to x (we may then say it is mapped to -x), 3. do not switch and map it to x (or simply map it to +x), 4. map it to -y, 5. map to +y. Then observe that in a partial mapping of (G, σ) to T , each vertex that is already mapped forbids exactly one of the five options from the list of availablities at a neighboring vertex. For example, if u is mapped to z, then it forbids z from being used on any of its neighbors. If u is mapped to -x and has a positive connection to v, then it forbids the option of -x on v. One may then complete a proof of the fact that T -bounds the class of signed planar simple graphs by either using the Kempe chain argument or employing Thomassen's list coloring proof.

Thus except for the signed graph T 1 of Figure 15 and the signed graph T 1 , obtained from T 1 where the loop on the vertex x is positive, we have determined for each signed graph on three vertices if it bounds the class of signed planar simple graphs.

A closely related problem is the following:

Problem 20. Can the vertices of every signed planar simple graph be partitioned to two parts non of which induces a negative closed walk of even length?

It is not hard to check that the existence of such a partition for (G, σ) is equivalent to a mapping of (G, σ) to the signed graph of Figure 18. For one direction, observe that in such a mapping, the vertices mapped to x or t will form one part of the partition and those mapped to y and z form the other part. For the opposite direction, as it is observed in [START_REF] Naserasr | Homomorphisms of signed graphs: an update[END_REF], a connected signed graph with no negative even closed walk is either balanced or antibalanced. Therefore, each connected component, if (G, σ) admits a 2-partition non of which induces a negative even closed walk, the subgraph induced on each part maps to a graph on two vertices, one having a positive loop, the other having a negative loop.

A counterexample for this problem will also work as common counterexample for the three signed graphs of Figure 1 as it contains all three as a subgraph. Among singed graphs of order five there are two, depicted in Figure 19, that are of special interest. The one of the left is homomorphism equivalent of the Problem 7.6 in [START_REF] Steffen | Concepts of signed graph coloring European J. Combin[END_REF]. The one on the right implies an upper bound of 5 on the circular chromatic number of signed planar simple graphs in the sense of [START_REF] Naserasr | Circular chromatic number of signed graphs[END_REF].

It is also natural to ask for a homomorphism bound which itself is a signed simple graph. Existence of such a bound on 80 vertices, even in the stronger sense of edgesign preserving homomorphisms, follows from a result of Alon and Marshal [START_REF] Alon | Homomorphisms of edge-colored graphs and Coxeter groups[END_REF]. This is improved to 48 in [START_REF] Naserasr | Homomorphisms of signed graphs[END_REF] and to 40 in [START_REF] Ochem | Homomorphisms of 2-edge-colored trianglefree planar graphs[END_REF]. A lower bound of 10 is also given in [START_REF] Naserasr | Homomorphisms of signed graphs[END_REF]. It is shown in [START_REF] Ochem | Homomorphisms of 2-edge-colored trianglefree planar graphs[END_REF], that, furthermore, if there is a bound on 10 vertices, it has to be the signed graph obtained from Signed Paley Graph on F 9 by adding a universally positive vertex.

Figure 1 :

 1 Figure 1: The homomorphism targets for complex 4-coloring

Figure 2 :

 2 Figure 2: (2, 0)-coloring a negative triangle

Figure 4 :

 4 Figure 3: (1, 1)-coloring a negative triangle

Lemma 9 .

 9 Given a (1, 1)-coloring c of the signed graph H 1 of Figure6satisfying triangle property, if an a-monochromatic subgraph (H , σ) contains both u and v, then it contains a positive 5-cycle with the edge uv as part of it.Proof. Consider a (1, 1)-coloring c of the graph H 1 which satisfies the triangle property. Furthermore, assume c(u), c(v) ∈ A = {a, -a} and let B = {b, -b} be the other two colors in C 1,1 . Applying triangle property on the faces utv and uzv, we have c(t) ∈ B and c(z) ∈ B.Depending on whether c(w) ∈ A or c(w) ∈ B we consider two case:• c(w) ∈ A. The triangle zx 2 x 3 implies that either c(x 2 ) ∈ A or c(x 3 ) ∈ A. Case c(x 2 ) ∈ A. Asux 2 wx 5 is a negative even cycle in which three of its vertices are in a-monochromatic subgraph, c(x 5 ) ∈ B. If c(x 4 ) ∈ A, then ux 2 wx 4 v is a positive 5-cycle in the a-monochromatic subgraph. Thus c(x 4 ) ∈ B, but then tx 4 x 5 is a b-monochromatic facial triangle which violates triangle property. Case c(x 2 ) ∈ B. Then c(x 3 ) ∈ A because of the triangle zx 2 x 3 . Hence c(x 4 ) ∈ B because of the triangle wx 3 x 4 , and c(x 5 ) ∈ B because of the positive 5-cycle ux 5 wx 3 v. But then tx 4 x 5 violates the triangle property. • c(w) ∈ B. The triangle ux 1 x 2 implies that either c(x 1 ) ∈ B or c(x 2 ) ∈ B. Case c(x 1 ) ∈ B. Then c(x 2 ), c(x 5 ) ∈ A because of the triangles wx 1 x 2 and wx 1 x 5 . Now considering the negative even cycle ux 2 x 3 v, and by Observation 8, we have c(x 3 ) ∈ B and similarly, because of the negative 4-cycle ux 5 x 4 v, we have c(x 4 ) ∈ B, but then wx 3 x 4 violates the triangle condition. Case c(x 2 ) ∈ B. Then c(x 1 ), c(x 3 ) ∈ A because of the triangles wx 1 x 2 and wx 2 x 3 . This in turn implies that c(x 4 ), c(x 5 ) ∈ B because of the triangles ux 1 x 5 and vx 3 x 4 . But then the triangle tx 4 x 5 violates the triangle property.

Figure 8 :Figure 9 :

 89 Figure 8: Smallest not (2, 0)-colorable graph without a loop

and H 2

 2 of Figure7by identifying the vertices labeled u together, vertices labeled v together and edge uv together. The result then is a signed planar simple graph that has the following property.Lemma 14. In any (1, 1)-coloring c of the signed graph H, either c(u) ∈ {+1, -1} and c(v) ∈ {i, -i} or c(v) ∈ {+1, -1} and c(u) ∈ {i, -i}.Proof. Otherwise, c(u), c(v) ∈ {a, -a} for a = 1 or a = i. Then by Lemma 9, we have an a-monochromatic positive 5-cycle in H 1 part of H which contains uv and by Lemma 10, we have an a-monochromatic negative 5-cycle in H 2 part of H which contains uv. Combined together, and after removing the edge uv we get an a-monochromatic negative 8-cycle, contradicting Obervation 8.

Figure 10 :

 10 Figure 10: Three minimal homomorphism bounds of signed planar simple graphs

Figure 11 :

 11 Figure 11: T -does not bound SP

Figure 12 :

 12 Figure 12: T +--(xy) -does not bound SP

Figure 14

 14 Figure 13: (G, σ) → T -z

Figure 15 :Figure 16 :

 1516 Figure 15: Does T 1 bound SP?

Lemma 19 .

 19 In a 2-coloring c of the graph of Figure17which corresponds to a T 2 -coloring of this graph, vertices u, v and w cannot be monochromatic.

Figure 17 :

 17 Figure 17: T 2 -coloring a negative triangle

Figure 18 :

 18 Figure 18: The configuration associated to Problem 20

Figure 19 : 5 -

 195 Figure 19: 5-vertices bound on SP?

Acknowledgement. We would like to thanks Zhouningxin Wang for discussions on this subject. This work is supported by the French ANR project HOSIGRA (ANR-17-CE40-0022).


Julie Déserti
email: deserti@math.univ-paris-diderot.fr

DEGREE GROWTH OF POLYNOMIAL AUTOMORPHISMS AND BIRATIONAL MAPS: SOME EXAMPLES

We provide the existence of new degree growths in the context of polynomial automorphisms of C k : if k is an integer ≥ 3, then for any ℓ ≤ k-1 2 there exist polynomial automorphisms f of C k such that deg f n ∼ n ℓ . We also give counter-examples in dimension k ≥ 3 to some classical properties satisfied by polynomial automorphisms of C 2 .

We provide the existence of new degree growths in the context of birational maps of P k C : assume k ≥ 3; forall 0 ≤ ℓ ≤ k there exist birational maps φ of P k C such that deg φ n ∼ n ℓ .

INTRODUCTION

Let f be a polynomial automorphism of C 2 , then either (deg f n ) n∈N is bounded, or (deg f n ) n∈N grows exponentially. In higher dimensions there are intermediate growths:

Theorem A. Let k be an integer ≥ 3. For any ℓ ≤ k-1 2 there exist polynomial automorphisms

f of C k such that deg f n ∼ n ℓ .
The group of polynomial automorphisms of C 2 has a structure of amalgamated product ( [START_REF] Jung | Über ganze birationale Transformationen der Ebene[END_REF]); using this rigidity a lot of properties of polynomial automorphisms of C 2 have been established. All these properties show a dichotomy; up to conjugacy there are two types of polynomial automorphisms of C 2 : the elementary ones and the Hénon ones. Furthermore if f and g are two polynomial automorphisms of C 2 and H ∞ denotes the line at infinity (we view C 2 in P 2 C ), then (P 1 ) : f is algebraically stable if and only if (deg f n ) n∈N grows exponentially; (P 2 ) : for any n ≥ 1 the equality deg f n = (deg f ) n holds if and only if f does not preserve a fibration in hyperplanes; (P 3 ) : the sequences (deg f n ) n∈N and (deg g n ) n∈N have the same growth if and only if the configurations of f (H ∞ ), f -1 (H ∞ ), Ind( f ), Ind( f -1 ) and g(H ∞ ), g -1 (H ∞ ), Ind(g), Ind(g -1 ) are the same; (P 4 ) : deg f 2 = (deg f ) 2 if and only if deg f n = (deg f ) n for any n ∈ N (see [START_REF] Furter | On the degree of iterates of automorphisms of the affine plane[END_REF]Proposition 3]). Note that in (P 1 ), (P 2 ) and (P 4 ) one can add "if and only if f is of Hénon type".

Fact B.

We give counter-examples to Properties (P 1 ), (P 2 ), (P 3 ) and (P 4 ) in dimension ≥ 3.

Nevertheless one can prove a similar result to property P 4 :

Proposition C. Let f be a polynomial automorphism of C k . Then deg f i = (deg f ) i for 1 ≤ i ≤ k if and only if deg f n = (deg f ) n for any n ≥ 1.
If φ is a birational self map of P 2 C , then (deg φ n ) n∈N is either bounded, or grows linearly, or grows quadratically, or grows exponentially ( [START_REF] Diller | Dynamics of bimeromorphic maps of surfaces[END_REF]). In this context there exist other types of growth in higher dimension. Lin has studied the degree growth of monomial maps of P k C (see [START_REF] Lin | Algebraic stability and degree growth of monomial maps[END_REF]); he proves in particular that if A is a k × k integer matrix with nonzero determinant, then there exist two constants α ≥ β ≥ 0 and a unique integer 0 ≤ ℓ ≤ k -1 such that for any n ∈ N β ρ(A) ℓ n ℓ ≤ deg φ n A ≤ α ρ(A) ℓ n ℓ where ρ(A) denotes the spectral radius of A and φ A the monomial map associated to A. Does there exist in dimension k birational maps of P k C with growth n ℓ with ℓ > k -1 ? Theorem D. Assume k ≥ 3; forall 0 ≤ ℓ ≤ k there exist birational maps φ of P k C such that deg φ n ∼ n ℓ . Note that there exists a birational self map f of P 3

C such that deg f n ∼ n 4 (see [START_REF] Urech | Remarks on the degree growth of birational transformations[END_REF]).

Acknowledgement. I am very grateful to

f : C k → C k , z 0 , z 1 , . . . , z k-1 ) → ( f 0 (z 0 , z 1 , . . . , z k-1 ), f 1 (z 0 , z 1 , . . . , z k-1 ), . . . , f k-1 (z 0 , z 1 , . . . , z k-1 )
that is bijective. The set of polynomial automorphisms of C k form a group denoted Aut(C k ).

The automorphisms of C k of the form ( f 0 , f 1 , . . . , f k-1 ) where f i depends only on z i , z i+1 , . . ., z k-1 are called elementary automorphisms and form a subgroup E k of Aut(C k ). Moreover we have the inclusions

GL(C k ) ⊂ Aff k ⊂ Aut(C k )
where Aff k denotes the group of affine maps

f : (z 0 , z 1 , . . . , z k-1 ) → f 0 (z 0 , z 1 , . . . , z k-1 ), f 1 (z 0 , z 1 , . . . , z k-1 ), . . . , f k-1 (z 0 , z 1 , . . . , z k-1 )
with f i affine; Aff k is the semi-direct product of GL(C k ) with the commutative subgroups of translations. The subgroup Tame k ⊂ Aut(C k ) generated by E k and Aff k is called the group of tame automorphisms. If k = 2 one has: Theorem 2.1 ([6]). In dimension 2 the group of tame automorphisms coincides with the whole group of polynomial automorphism; more precisely

Aut(C 2 ) = Aff 2 * Aff 2 ∩E 2 E 2 .
But this is not the case in higher dimension: Tame 3 Aut(C 3 ) (see [START_REF] Shestakov | The tame and the wild automorphisms of polynomial rings in three variables[END_REF]).

Another important result in dimension 2 is the following: [START_REF] Friedland | Dynamical properties of plane polynomial automorphisms[END_REF]). Let f be an element of Aut(C 2 ). Then, up to conjugacy, -either f belongs to E 2 , -or f can be written as

Theorem 2.2 ([
ϕ ℓ • ϕ ℓ-1 • . . . ϕ 1
where

ϕ i : (z 0 , z 1 ) → (z 1 , P i (z 1 ) -δ i z 0 ), δ i ∈ C * , P i ∈ C[z 1 ], deg P i ≥ 2.
We denote by H the set of polynomial automorphisms of C 2 can be written up to conjugacy as

ϕ ℓ • ϕ ℓ-1 • . . . ϕ 1
where

ϕ i : (z 0 , z 1 ) → (z 1 , P i (z 1 ) -δ i z 0 ), δ i ∈ C * , P i ∈ C[z 1 ], deg P i ≥ 2.
The elements of H are of Hénon type.

From now one we will denote f = (

f 0 , f 1 , . . . , f k-1 ) instead of f : (z 0 , z 1 , . . . , z k-1 ) → f 0 (z 0 , z 1 , . . . , z k-1 ), f 1 (z 0 , z 1 , . . . , z k-1 ), . . . , f k-1 (z 0 , z 1 , . . . , z k-1 ) .
The algebraic degree deg

f of f = ( f 0 , f 1 , . . . , f k-1 ) ∈ Aut(C k ) is max(deg f 0 , deg f 1 , . . . , deg f k-1 ).

The Cremona group.

A rational self map f of P k C can be written z 0 : z 1 : . . . :

z k f 0 (z 0 , z 1 , . . . , z k ) : f 1 (z 0 , z 1 , . . . , z k ) : . . . : f k (z 0 , z 1 , . . . , z k )
where the f i 's are homogeneous polynomials of the same degree ≥ 1 and without common factor of positive degree. The degree of f is the degree of the f i . If there exists a rational self map g of P k C such that f g = g f = id we say that the rational self map f of

P k C is birational. The set
(P k C ) ≃ PGL(k + 1; C) of automorphisms of P k C . The indeterminacy set Ind( f ) of f is the set of the common zeros of the f i 's. The exceptional set Exc( f ) of f is the (finite) union of subvarieties M i of P k
C such that f is not injective on any open subset of M i .

A little bit of dynamics.

Let f be a polynomial automorphism of C k . One can see f as a birational self map of P k C still denoted f . We will say that f is algebraically stable if for any n > 0

f n {z k = 0} Ind( f n )
is not contained in Ind( f ). This is equivalent to the fact that (deg f ) n = deg f n for any n > 0. For instance elements of H are algebraically stable.

Remark 2.3. Note that in dimension 2 one usually says that f is algebraically stable if for any n > 0

f n {z 2 = 0} Ind( f n ) ∩ Ind( f ) = / 0.
Be careful this is not equivalent in higher dimension: consider for instance

f = 5z 2 0 + z 2 2 + 6z 0 z 2 + z 1 , z 2 2 + z 0 , z 2 ; then
-on the one hand (-1 : 0 : 1 : 0) belongs to {z 3 = 0} Ind( f ) and f (-1 : 0 :

1 : 0) = (0 : 1 : 0 : 0) ∈ Ind( f ) = {(0 : 1 : 0 : 0)}. -on the other hand for any n ≥ 1 deg f n = (deg f ) n .
The algebraic degree of a birational map f of P n C (resp. a polynomial automorphism of C k ) is not a dynamical invariant so we introduce the dynamical degree

λ( f ) = lim n→+∞ (deg f n ) 1/n
which is a dynamical invariant. In other words if f ∈ Bir(P k C ) (resp. Aut(C k )), then for any g ∈ Bir(P k C )

(resp. g ∈ Aut(C k )) one has λ( f ) = λ(g f g -1 )
. For any element f in H the algebraic and dynamical degrees coincide; more precisely if

f = ϕ ℓ • ϕ ℓ-1 • . . . • ϕ 1 where ϕ i = (z 1 , P i (z 1 ) -δ i z 0 ), δ i ∈ C * , P i ∈ C[z 1 ], deg P i ≥ 2 one has ([4]) λ( f ) = ℓ ∏ i=1 degϕ i ≥ 2. A polynomial automorphism f is in E k if and only if for any n ≥ 1 the equality deg f = deg f n holds hence λ( f ) = 1.
In other words a polynomial automorphism f of C 2 belongs to H if and only if λ( f ) > 1. There is an other characterization of the automorphisms of Hénon type:

Theorem 2.4 ([7]). The centralizer of f in Aut(C 2 ), that is g ∈ Aut(C 2 ) | f g = g f
, is countable if and only if f belongs to H .

AUTOMORPHISMS WITH POLYNOMIAL GROWTHS

3.1. The growths of a polynomial automorphisms and its inverse.

If f is a polynomial automorphism of C k , then (deg f , deg f -1
) is the bidegree of f . There is a relationship between deg f and deg f -1 (see [START_REF] Bass | The Jacobian conjecture and inverse degrees[END_REF]):

deg f -1 ≤ (deg f ) k-1 deg f ≤ (deg f -1 ) k-1 (3.1)
As a result if f is a polynomial automorphism of C k , the degree growths of f and f -1 are linked:

Proposition 3.1. Let f be a polynomial automorphism of C k . -The sequence (deg f n ) n∈N is bounded if and only if the sequence (deg f -n ) n∈N is bounded.
-The sequence (deg f n ) n∈N grows exponentially if and only if (deg f -n ) n∈N grows exponentially.

-If deg f n ≃ n p and deg f -n ≃ n q for some integers p, q ≥ 1, then (p, q) ∈ q + 1 k , q , . . . , (kq, q) . Remark 3.2. When we write "The sequence (deg f n ) n∈N grows exponentially if and only if (deg f -n ) n∈N grows exponentially" it does not mean that (deg f n ) n∈N and (deg f -n ) n∈N have exactly the same behavior: the polynomial automorphism of C 3 given by f = (z

2 0 + z 1 + z 2 , z 2 0 + z 1 , z 0 ) satisfies forall n ≥ 1 deg f n = 2 n deg f -n = 2 [ n+1 2 ]

Examples of polynomial automorphisms with new polynomial growths. Let us now give examples of polynomial automorphisms with polynomial growths.

Lemma 3.3. Let us consider the polynomial automorphism of C 3 given by

f = z 1 + z 0 z d 2 , z 0 , z 2 where d ≥ 1. One has deg f n = dn + 1 and deg f n = deg f -n for any n ≥ 1. Proof. Assume n ≥ 1. Set f n = ( f 0,n , f 1,n , z 2 ) and δ n = deg f n . Note that δ 1 = d + 1 and since f n = f f n-1 = ( f 1,n-1 + f 0,n-1 z d 2 , f 0,n-1 , z 2 ) one has δ n = max deg f 1,n-1 , deg f 0,n-1 + d, deg f 0,n-1 , 1 . But f 1,n-1 = f 0,n-2 and d ≥ 1 so δ n = deg f 0,n-1 + d = δ n-1 + d.
Similarly one can prove: Lemma 3.4. Let us consider the polynomial automorphism of C 5 given by

g = z 1 + z 0 z d 2 , z 0 , z 2 , z 4 + z p 0 z 3 , z 3 where p ≥ d ≥ 1. One has for any n ≥ 1 deg g n = pd 2 n 2 + p(2 -d) 2 n + 1 and deg g n = deg g -n for any n ≥ 1.
Let us consider the polynomial automorphism of C 7 given by

h = z 1 + z 0 z d 2 , z 0 , z 2 , z 4 + z p 0 z 3 , z 3 , z 6 + z ℓ 3 z 5 , z 5 where ℓ ≥ p ≥ d ≥ 1. For any n ≥ 1 deg h n = 1 + ℓ 1 - p 2 + pd 3 n + ℓp(1 -d) 2 n 2 + ℓpd 6 n 3 and deg h n = deg h -n .
So Lemma 3.3 gives an example f of polynomial automorphism of C 3 with linear growth; from f one gets a polynomial automorphism g of C 5 such that deg g n ∼ n 2 , and from g one gets a polynomial automorphism h of C 7 such that deg h n ∼ n 3 (Lemma 3.4). By repeating this process one gets the following statement:

Proposition 3.5. There exist polynomial automorphisms

f of C 2k+1 , k ≥ 2, such that deg f n ∼ n k .
Theorem A follows from Proposition 3.5.

A consequence.

Come back to f = (z 1 + z 0 z d 2 , z 0 , z 2 ) and consider the birational map of P 4 C given by F = ( f , z p 0 z 3 ), that is F = (z 1 + z 0 z d 2 , z 0 , z 2 , z p 0 z 3 ). Assume that d ≤ p. Then one can prove by induction that for any n ≥ 1

degF n = pd 2 n 2 + p(2 -d) 2 n + 1.
Let us now define the birational map

F of P 5 C by G = (z 1 + z 0 z d 2 , z 0 , z 2 , z p 0 z 3 , z ℓ 3 z 4 ); for any n ≥ 1 one has deg G n = ℓpd 6 n 3 + 1 - 3d 4 ℓpn 2 + 13 12 pd -2p + 1 ℓn - ℓpd 2 + ℓp + 1.
Repeating this process one gets Proposition 3.6. If k ≥ 3, then for any 0 ≤ ℓ ≤ k -2 there exist birational maps

F of P k C such that deg F n ∼ n ℓ .

PROPERTIES (P i )

Note that Theorem 2.4 can be also stated as follows: the centralizer of a polyonomial automorphism f of C 2 is countable if and only if (deg f n ) n∈N grows exponentially. This property is not true in higher dimension: there exist polynomial automorphisms of C 3 with uncountable centralizer and exponential degree growth ( [START_REF] Bisi | On commuting polynomial automorphisms of C k , k ≥ 3[END_REF]). Let us now that this is also the case for other properties, and in particular for (P 1 ), (P 2 ), (P 3 ), (P 4 ).

4.1. Property (P 1 ). Property (P 1 ) is not satisfied in dimension 3:

Proposition 4.1. If f = z 2 , (z 2 2 + z 0 ) 2 + z 2 2 + z 0 + z 1 , z 2 2 + z 0 then -Ind( f ) = {z 2 = z 3 = 0} and z 3 = 0 is blown down by f onto (0 : 1 : 0 : 0) ∈ Ind( f ), -for all n ≥ 1 one has deg f n = 2 n+1 .
4.2. Property (P 2 ). Property (P 2 ) does not hold in higher dimension:

Proposition 4.2. The polynomial automorphism f of C 3 given by z 2 0 + z 1 , z 0 , z 2 + 1 preserves the fibration z 2 = cst and for all n ≥ 1 the equality deg f n = 2 n holds.

The polynomial automorphism g of C 3 given by z 2 1 + z 0 z 1 + z 2 , z 1 + 1, z 0 preserves the fibration z 1 = cst and for all n ≥ 1 the equality deg g n = n + 1 holds. 4.3. Property (P 3 ). Property (P 3 ) is not satisfied in dimension 3. Proposition 4.3. Let us consider the polynomial automorphisms f and g of C 3 defined by

f = z 0 + z 1 + z 2 , z 2 0 + z 0 + z 1 , z 0 , g = z 2 1 + z 0 + z 1 + z 2 , z 1 , z 0 . For all n ≥ 1 one has    deg f 2n = 2 n+1 , deg f 2n+1 = 2 n+1 deg f -n = 2 n deg g n = deg g -n = 2
The automorphism f sends z 3 = 0 onto (0 : 1 : 0 : 0) and f -1 sends z 3 = 0 onto (0 : 1 : 1 : 0). Furthermore Ind( f ) = {z 0 = z 3 = 0} and Ind( f -1 ) = {z 2 = z 3 = 0}.

The automorphism g sends z 3 = 0 onto (1 : 0 : 0 : 0) and g -1 sends z 3 = 0 onto (0 : 0 : 1 : 0). Besides Ind(g) = {z 1 = z 3 = 0} and Ind(g -1 ) = {z 2 = z 3 = 0}. 4.4. Property (P 4 ). In [START_REF] Furter | On the degree of iterates of automorphisms of the affine plane[END_REF] Furter proves that if f is a polynomial automorphism of C 2 then deg f 2 = (deg f ) 2 if and only if deg f n = (deg f ) n for all n ∈ N. This property does not hold in higher dimension: consider for instance the polynomial automorphism f given by

f = (z 2 1 + z 5 , z 2 5 + z 4 , z 2 , z 1 , z 0 , z 2 4 + z 3 ). One can check that deg f = 2, deg f 2 = 4, deg f 3 = 8 but deg f 4 = 8.
Let f be a polynomial automorphism of C k . For any integer n ≥ 0 set Ω n = f n (z k-1 = 0) Ind( f n ) ; note that Ω n ⊂ (z k-1 = 0) for any n. We say that f is not algebraically stable after ℓ steps if ℓ is the smallest integer such that Ω ℓ ⊂ Ind( f ).

Let us first remark that if

Ω 1 ∩ Ind( f ) = / 0, then Ω 2 = f (Ω 1 ) ⊆ Ω 1 so Ω 2 ∩ Ind( f ) = / 0. By induction one gets for any n ≥ 1 that Ω n ∩ Ind( f ) = / 0 and deg f n = (deg f ) n , i.e. f is algebraically stable.
Let us now assume that Ω 1 ∩ Ind( f ) = / 0. Then:

(1) Either Ω 1 ⊂ Ind( f ), that is f is not algebraically stable after 1 step.

(

) Or Ω 1 ⊂ Ind( f ) hence Ω 2 = f Ω 1 Ind( f ) ⊆ Ω 1 . 2
-Either dim Ω 2 = dim Ω 1 , so Ω 2 = Ω 1 and then Ω n = Ω 1 for any n; in particular Ω n ⊂ Ind( f ) for any n and f is algebraically stable.

-Or dim Ω 2 < dim Ω 1 , then either Ω 2 ⊂ Ind( f ) and f is not algebraically stable after 2 steps or Ω 2 ⊂ Ind( f ) and we come back to the previous alternative, that is either dim

Ω 3 = dim Ω 2 or dim Ω 3 < dim Ω 2 .
Since for any n one has 0 ≤ dim Ω n ≤ k -1 one gets that either f is algebraically stable, or f is not algebraically stable after at most k -1 steps.

Hence one can state: Proposition 4.4. Let f be a polynomial automorphism of C k . Either f is algebraically stable, or f is not algebraically stable after ℓ steps, with ℓ ≤ k -1.

In other words deg

f i = (deg f ) i for 1 ≤ i ≤ k if and only if deg f n = (deg f ) n for any n ≥ 1.

BIRATIONAL MAPS WITH NEW POLYNOMIAL GROWTHS

Let us first recall that One can also check that

Ψ 3 = P n Q n , R n S n , U n
V n where U n = z 0 z 2 P 1 P 2 . . . P n-1 and V n = Q 1 Q 2 . . . Q n-1 have no common factor. Since s i ∼ i 2 one gets: Let us now consider the birational self map of P 4 C defined in the affine chart z 4 = 1 by

Ψ 4 (z 0 , z 1 , z 2 , z 3 ) = z 1 + 2 3 , z 0 z 1 -1 3 z 1 + 1 , z 0 z 2 , z 2 z 3 .
One can check that

Ψ 4 = P n Q n , R n S n , U n V n , W n X n where W n = W 1 U 1 U 2 . . .U n-1 and X n = X 1 V 1 V 2 . . .V

Lemma 5 . 1 (, z 0 z 1 -1 3 z 1 + 1 satisfies deg ϕ n ∼ n 2 . 3 , z 0 z 1 -1 3 z 1 + 1 , z 0 z 2 .

 5113112313112 [START_REF] Diller | Dynamics of bimeromorphic maps of surfaces[END_REF]). The birational self map ϕ of P 2 C given in the affine chart z 2 = 1 byϕ(z 0 , z 1 ) = z 1 + 2 3 Denote ϕ n by P n Q n , R n S n where P n , Q n , R n and S n denote some elements of C[z 0 , z 1 ] without common factor. Set p n = deg P n , q n = deg Q n , r n = deg R n and s n = deg S n . The following equalities hold (by iteration) s n-1 + 1 q n = s n-1 r n = s n + 1 deg ϕ n = s n-1 + s n + 1Let us now consider the birational self map of P 3 C given in the affine chart z 3 = 1 by Ψ 3 (z 0 , z 1 , z 2 ) = z 1 + 2

Lemma 5 . 2 .

 52 The birational self mapΨ 3 of P 3 C satisfies deg Ψ 3 ∼ n 3 .

The group of polynomial automorphisms of C k . A polynomial automorphism f

  Dominique Cerveau for his constant support.

	CONTENTS
	1. Introduction	1
	2. Recalls, definitions, notations	2
	3. Automorphisms with polynomial growths	4
	4. Properties (P i )	5
	5. Birational maps with new polynomial growths	7
	References	8
	2. RECALLS, DEFINITIONS, NOTATIONS
	2.1. of C k is a polyno-
	mial map of the type

  n-1 have no common factor. Since degU n ∼ n 3 and degV n ∼ n 3 one has: Lemma 5.3. The birational self map Ψ 4 of P 4 C satisfies deg Ψ 4 ∼ n 4 .

By repeating this process one gets: Theorem 5.4. Let k be an integer ≥ 3. There exist birational maps φ of P k C such that degφ n ∼ n k . This statement and Lin's result ( [START_REF] Lin | Algebraic stability and degree growth of monomial maps[END_REF]) imply Theorem D.