Chunhui Lai
email: zjlaichu@public.zzptt.fj.cn

An extremal problem on potentially

Keywords: AMS Subject Classifications: 05C07, 05C35 graph, degree sequence, potentially Kp,1,1-graphic sequence

A sequence S is potentially Kp,1,1 graphical if it has a realization containing a Kp,1,1 as a subgraph, where Kp,1,1 is a complete 3-partite graph with partition sizes p, 1, 1. Let σ(Kp,1,1, n) denote the smallest degree sum such that every n-term graphical sequence S with σ(S) ≥ σ(Kp,1,1, n) is potentially Kp,1,1 graphical. In this paper, we prove that σ(Kp,1,1, n) ≥ 2[((p + 1)(n -1) + 2)/2] for n ≥ p + 2. We conjecture that equality holds for n ≥ 2p + 4. We prove that this conjecture is true for p = 3.

Introduction

If S = (d 1 , d 2 , . . . , d n ) is a sequence of non-negative integers, then it is called graphical if there is a simple graph G of order n, whose degree sequence (d(v 1 ), d(v 2 ), . . . , d(v n )) is precisely S. If G is such a graph then G is said to realize S or be a realization of S. A graphical sequence S is potentially H graphical if there is a realization of S containing H as a subgraph, while S is forcibly H graphical if every realization of S contains H as a subgraph. Let σ(S) = d(v 1 ) + d(v 2 ) + . . . + d(v n ), and [x] denote the largest integer less than or equal to x. We denote G+H as the graph with V (G+H) = V (G) V (H) and E(G + H) = E(G) E(H) {xy : x ∈ V (G), y ∈ V (H)}. Let K k , and C k denote a complete graph on k vertices, and a cycle on k vertices, respectively. Let K p,1,1 denote a complete 3-partite graph with partition sizes p, 1, 1.

Given a graph H, what is the maximum number of edges of a graph with n vertices not containing H as a subgraph? This number is denoted ex(n, H), and is known as the Turán number. This problem was proposed for H = C 4 by Erdős [START_REF] Erdős | On sequences of integers no one of which divides the product of two others and some related problems[END_REF] in 1938 and in general by Turán [START_REF] Turán | On an extremal problem in graph theory[END_REF]. In terms of graphic sequences, the number 2ex(n, H)+2 is the minimum even integer l such that every n-term graphical sequence S with σ(S) ≥ l is forcibly H graphical. Here we consider the following variant: determine the minimum even integer l such that every n-term graphical sequence S with σ(S) ≥ l is potentially H graphical. We denote this minimum l by σ(H, n). Erdős, Jacobson and Lehel [START_REF] Erdős | Graphs realizing the same degree sequences and their respective clique numbers[END_REF] showed that σ(K k , n) ≥ (k-2)(2n-k+1)+2 and conjectured that equality holds. They proved that if S does not contain zero terms, this conjecture is true for k = 3, n ≥ 6. The conjecture is confirmed in [START_REF] Gould | Potentially G-graphic degree sequences[END_REF], [START_REF] Jiong | An extremal problem on the potentially P k -graphic sequences[END_REF], [START_REF] Jiong | The smallest degree sum that yields potentially P k -graphical sequences[END_REF], [START_REF] Jiong | On the potentially P k -graphic sequences[END_REF] and [START_REF] Jiong-Sheng | The Erdős-Jacobson-Lehel conjecture on potentially P k -graphic sequence is true[END_REF].

Gould, Jacobson and Lehel [START_REF] Gould | Potentially G-graphic degree sequences[END_REF] also proved that σ(pK

2 , n) = (p-1)(2n-2)+2 for p ≥ 2; σ(C 4 , n) = 2[ 3n-1 2 ]
for n ≥ 4. Luo [START_REF] Luo | On potentially C k -graphic sequences[END_REF] characterized the potentially C k graphic sequence for k = 3, 4, 5. Yin and Li [START_REF] Jian | An extremal problem on potentially K r,s -graphic sequences[END_REF] gave sufficient conditions for a graphic sequence being potentially K r,s -graphic, and determined σ(K r,r , n) for r = 3, 4. Lai [START_REF] Chunhui | A note on potentially K 4 -e graphical sequences[END_REF] proved that σ(K 4 -e, n) = 2[ 3n- 1 2 ] for n ≥ 7. In this paper, we prove that σ(K p,1,1 , n) ≥ 2[((p + 1)(n -1) + 2)/2] for n ≥ p + 2. We conjecture that equality holds for n ≥ 2p + 4. We prove that this conjecture is true for p = 3.

2 Main results.

Theorem 1 σ(K p,1,1 , n) ≥ 2[((p + 1)(n -1) + 2)/2], for n ≥ p + 2. Proof: If p = 1, by Erdős, Jacobson and Lehel [4], σ(K 1,1,1 , n) ≥ 2n, Theorem 1 is true.
If p = 2, by Gould, Jacobson and Lehel [START_REF] Gould | Potentially G-graphic degree sequences[END_REF],

σ(K 2,1,1 , n) = σ(K 4 -e, n) ≥ σ(C 4 , n) = 2[(3n -1)/2], Theorem 1 is true. Then we can suppose that p ≥ 3.
We first consider odd p.

If n is odd, let n = 2m + 1, by Theorem 9.7 of [2], K 2m is the union of one 1-factor M and m -1 spanning cycles C 1 1 , C 1 2 , . . . , C 1 m-1 . Let H = C 1 1 C 1 2 . . . C 1 p-1 2 + K 1 (1)
Then H is a realization of ((n -1) 1 , p n-1 ), where the symbol x y stands for y consecutive terms x. Since K p,1,1 contains two vertices of degree p + 1 while ((n -1) 1 , p n-1 ) only contains one integer n -1 greater than degree p, ((n -1) 1 , p n-1 ) is not potentially K p,1,1 graphic. Thus

σ(K p,1,1 , n) ≥ (n -1) + p(n -1) + 2 = 2[((p + 1)(n -1) + 2)/2]. (2)
Next, if n is even, let n = 2m + 2, by Theorem 9.6 of [START_REF] Harary | Graph Theory[END_REF], K 2m+1 is the union of m spanning cycles

C 1 1 , C 1 2 , . . . , C 1 m . Let H = C 1 1 C 1 2 . . . C 1 p-1 2 + K 1 (3)
Then H is a realization of ((n -1) 1 , p n-1 ), and we are done as before. This completes the discussion for odd p. Now we consider even p. If n is odd, let n = 2m + 1, by Theorem 9.7 of [START_REF] Harary | Graph Theory[END_REF], K 2m is the union of one 1-factor M and m -

1 spanning cycles C 1 1 , C 1 2 , . . . , C 1 m-1 . Let H = M C 1 1 C 1 2 . . . C 1 p-2 2 + K 1 ( 4
)
Then H is a realization of ((n -1) 1 , p n-1 ), and we are done as before.

Next, if n is even, let n = 2m + 2, by Theorem 9.6 of [START_REF] Harary | Graph Theory[END_REF], K 2m+1 is the union of m spanning cycles

C 1 1 , C 1 2 , . . . , C 1 m . Let C 1 1 = x 1 x 2 . . . x 2m+1 x 1 H = (C 1 1 C 1 2 . . . C 1 p 2 + K 1 ) -{x 1 x 2 , x 3 x 4 , . . . , x 2m-1 x 2m , x 2m+1 x 1 }
Then H is a realization of ((n -1) 1 , p n-2 , (p -1) 1 ). It is easy to see that ((n -1) 1 , p n-2 , (p -1) 1 ) is not potentially K p,1,1 graphic. Thus

σ(K p,1,1 , n) ≥ (n -1) + p(n -2) + p -1 + 2 = 2[((p + 1)(n -1) + 2)/2].
This completes the discussion for even p, and so finishes the proof of Theorem 1 ✷ Theorem 2 For n = 5 and n ≥ 7,

σ(K 3,1,1 , n) = 4n -2.
For n = 6, if S is a 6-term graphical sequence with σ(S) ≥ 22, then either there is a realization of S containing K 3,1,1 or S = (4 6 ). (Thus σ(K 3,1,1 , 6) = 26.)

Proof: By Theorem 1, for n ≥ 5, σ(K 3,1,1, n) ≥ 2[((3 + 1)(n -1) + 2)/2] = 4n -2.
We need to show that if S is an n-term graphical sequence with σ(S) ≥ 4n -2, then there is a realization of S containing a K 3,1,1 (unless S = (4 6 )). Let

d 1 ≥ d 2 ≥ • • • ≥ d n ,
and let G be a realization of S.

Case n = 5: If a graph has size q ≥ 9, then clearly it contains a K 3,1,1 , so that σ(K 3,1,1 , 5) ≤ 4n -2.

Case n = 6: If σ(S) = 22, we first consider d 6 ≤ 2. Let S ′ be the degree sequence of G -v 6 , so σ(S ′ ) ≥ 22 -2 × 2 = 18. Then S ′ has a realization containing a K 3,1,1 . Therefore S has a realization containing a K 3,1,1 . Now we consider d 6 ≥ 3. It is easy to see that S is one of (5 2 , 3 4 ), (5 1 , 4 2 , 3 3 ) or (4 4 , 3 2 ). Obviously, all of them are potentially K 3,1,1 -graphic. Next, if σ(S) = 24, we first consider d 6 ≤ 3. Let S ′ be the degree sequence of G -v 6 , so σ(S ′ ) ≥ 24 -3 × 2 = 18.

Then S ′ has a realization containing a K 3,1,1 . Therefore S has a realization containing a K 3,1,1 . Now we consider d 6 ≥ 4. It is easy to see that S = (4 6 ). Obviously, (4 6 ) is graphical and (4 6 ) is not potentially K 3,1,1 graphic. Finally, suppose that σ(S) ≥ 26. We first consider d 6 ≤ 4. Let S ′ be the degree sequence of G -v 6 , so σ(S ′ ) ≥ 26 -2 × 4 = 18. Then S ′ has a realization containing a K 3,1,1 . Therefore S has a realization containing a K 3,1,1 . Now we consider d 6 ≥ 5. It is easy to see that S = (5 6 ). Obviously, (5 6) is potentially K 3,1,1 -graphic.

Case n = 7: First we assume that σ(S) = 26. Suppose d 7 ≤ 2 and let S ′ be the degree sequence of G -v 7 , so σ(S ′ ) ≥ 26 -2 × 2 = 22. Then S ′ has a realization containing a K 3,1,1 or S ′ = (4 6 ). Therefore S has a realization containing a K 3,1,1 or S = (5 1 , 4 5 , 1 1 ). Obviously, (5 1 , 4 5 , 1 1 ) is potentially K 3,1,1 -graphic. In either event, S has a realization containing a K 3,1,1 . Now we assume that d 7 ≥ 3. It is easy to see that S is one of (6 1 , 5 1 , 3 5 ), (6 1 , 4 2 , 3 4 ), (5 2 , 4 1 , 3 4 ), (5 1 , 4 3 , 3 3 ) or (4 5 , 3 2 ). Obviously, all of them are potentially K 3,1,1 -graphic. Next, if σ(S) = 28, Suppose d 7 ≤ 3. Let S ′ be the degree sequence of G -v 7 , so σ(S ′ ) ≥ 28 -3 × 2 = 22. Then S ′ has a realization containing a K 3,1,1 or S ′ = (4 6 ). Therefore S has a realization containing a K 3,1,1 or S = (5 2 , 4 4 , 2 1 ). Obviously, (5 2 , 4 2 , 2 1 ) is potentially K 3,1,1 -graphic. In either event, S has a realization containing a K 3,1,1 . Now we assume that d 7 ≥ 4, then S = (4 7 ). Clearly, (4 7 ) has a realization containing a K 3,1,1 . Finally, suppose that σ(S) ≥ 30. If d 7 ≤ 4. Let S ′ be the degree sequence of G -v 7 , so σ(S ′ ) ≥ 30 -2 × 4 = 22. Then S ′ has a realization containing a K 3,1,1 or S ′ = (4 6 ). Therefore S has a realization containing a K 3,1,1 or S = (5 3 , 4 3 , 3 1 ). Clearly, (5 3 , 4 3 , 3 1 ) has a realization containing a K 3,1,1 . In either event, S has a realization containing a K 3,1,1 . Now we consider d 7 ≥ 5. It is easy to see that σ(S) ≥ 5 × 7 = 35. Obviously σ(S) ≥ 36.

Clearly, S has a realization containing a K 3,1,1 .

We proceed by induction on n. Take n ≥ 8 and make the inductive assumption that for 7 ≤ t < n, whenever S 1 is a t-term graphical sequence such that

σ(S 1 ) ≥ 4t -2 (5)
then S 1 has a realization containing a K 3,1,1 . Let S be an n-term graphical sequence with σ(S) ≥ 4n -2.

If d n ≤ 2, let S ′ be the degree sequence of G -v n . Then σ(S ′ ) ≥ 4n -2 -2 × 2 = 4(n -1) -2.
By induction, S ′ has a realization containing a K 3,1,1 . Therefore S has a realization containing a K 3,1,1 . Hence, we may assume that d n ≥ 3. By Proposition 2 and Theorem 4 of [START_REF] Gould | Potentially G-graphic degree sequences[END_REF] (or Theorem 3.3 of [START_REF] Jiong | An extremal problem on the potentially P k -graphic sequences[END_REF] ) S has a realization containing a K 4 . By Lemma 1 of [START_REF] Gould | Potentially G-graphic degree sequences[END_REF], there is a realization

G of S with v 1 , v 2 , v 3 , v 4 , the four vertices of highest degree containing a K 4 . If d(v 2 ) = 3, then 4n -2 ≤ σ(S) ≤ n -1 + 3(n -1) = 4n -4. This is a contradiction. Hence, we may assume that d(v 2 ) ≥ 4. Let v 1 be adjacent to v 2 , v 3 , v 4 , y 1 . If y 1 is adjacent to one of v 2 , v 3 , v 4 , then G contains a K 3,1,1 . Hence, we may assume that y 1 is not adjacent to v 2 , v 3 , v 4 . Let v 2 be adjacent to v 1 , v 3 , v 4 , y 2 .
If y 2 is adjacent to one of v 1 , v 3 , v 4 , then G contains a K 3,1,1 . Hence, we may assume that y 2 is not adjacent to v 1 , v 3 , v 4 . Since d(y 1 ) ≥ d n ≥ 3, there is a new vertex y 3 , such that y 1 y 3 ∈ E(G).

Case 1: Suppose y 3 v 3 ∈ E(G). If y 3 v 4 ∈ E(G), then G contains a K 3,1,1 . Hence, we may assume that y 3 v 4 / ∈ E(G). Then the edge interchange that removes the edges y 1 y 3 , v 3 v 4 and v 2 y 2 and inserts the edges y 1 v 2 , y 3 v 4 and y 2 v 3 produces a realization G ′ of S containing a K 3,1,1 .

Case 2: Suppose y 3 v 3 / ∈ E(G). Then the edge interchange that removes the edges y 1 y 3 , v 3 v 4 and v 2 y 2 and inserts the edges y 1 v 2 , y 3 v 3 and y 2 v 4 produces a realization G ′ of S containing a K 3,1,1 . This finishes the inductive step, and thus Theorem 2 is established. ✷

Acknowledgements

The author thanks Prof. Therese Biedl for her valuable suggestions. The author thanks the referees for many helpful comments.

† Project Supported by NNSF of China(10271105), NSF of Fujian, Science and Technology Project of Fujian, Fujian Provincial Training Foundation for "Bai-Quan-Wan Talents Engineering", Project of Fujian Education Department and Project of Zhangzhou Teachers College. 1365-8050

We make the following conjecture:

This conjecture is true for p = 1, by Theorem 3.5 of [START_REF] Erdős | Graphs realizing the same degree sequences and their respective clique numbers[END_REF], for p = 2, by Theorem 1 of [START_REF] Chunhui | A note on potentially K 4 -e graphical sequences[END_REF], and for p = 3, by the above Theorem 2.


Mohammad Hosseini Dolama

Eric Sopena

On the maximum average degree and the incidence chromatic number of a graph

Keywords: incidence coloring, k-degenerated graph, planar graph, maximum average degree

We prove that the incidence chromatic number of every 3-degenerated graph G is at most ∆(G) + 4. It is known that the incidence chromatic number of every graph G with maximum average degree mad(G) < 3 is at most ∆(G) + 3. We show that when ∆(G) ≥ 5, this bound may be decreased to ∆(G) + 2. Moreover, we show that for every graph G with mad(G) < 22/9 (resp. with mad(G) < 16/7 and ∆(G) ≥ 4), this bound may be decreased to ∆(G) + 2 (resp. to ∆(G) + 1).

Introduction

The concept of incidence coloring was introduced by Brualdi and Massey (3) in 1993.

Let G = (V (G), E(G)) be a graph. An incidence in G is a pair (v, e) with v ∈ V (G), e ∈ E(G), such that v and e are incident. We denote by I(G) the set of all incidences in G. For every vertex v, we denote by I v the set of incidences of the form (v, vw) and by A v the set of incidences of the form (w, wv). Two incidences (v, e) and (w, f ) are adjacent if one of the following holds: (i) v = w, (ii) e = f or (iii) the edge vw equals e or f .

A k-incidence coloring of a graph G is a mapping σ of I(G) to a set C of k colors such that adjacent incidences are assigned distinct colors. The incidence chromatic number χ i (G) of G is the smallest k such that G admits a k-incidence coloring.

For a graph G, let ∆(G), δ(G) denote the maximum and minimum degree of G respectively. It is easy to observe that for every graph G we have χ i (G) ≥ ∆(G) + 1 (for a vertex v of degree ∆(G) we must use ∆(G) colors for coloring I v and at least one additional color for coloring A v ). Brualdi and Massey proved the following upper bound:

Theorem 1 (3) For every graph G, χ i (G) ≤ 2∆(G).
Guiduli [START_REF] Guiduli | On incidence coloring and star arboricity of graphs[END_REF] showed that the concept of incidence coloring is a particular case of directed star arboricity, introduced by Algor and Alon [START_REF] Algor | The star arboricity of graphs[END_REF]. Following an example from (1), Guiduli proved that there exist graphs G with χ i (G) ≥ ∆(G) + Ω(log ∆(G)). He also proved that For every graph G, χ i (G) ≤ ∆(G) + O(log ∆(G)).

Concerning the incidence chromatic number of special classes of graphs, the following is known:

1365-8050 c 2005 Discrete Mathematics and Theoretical Computer Science (DMTCS), Nancy, France

• For every n ≥ 2, χ i (K n ) = n = ∆(K n ) + 1 (3).

• For every m ≥ n ≥ 2, χ i (K m,n ) = m + 2 = ∆(K m,n ) + 2 (3).

• For every tree T of order n ≥ 2, χ i (T ) = ∆(T ) + 1 (3).

• For every Halin graph G with ∆(G) ≥ 5, χ i (G) = ∆(G) + 1 [START_REF] Wang | The incidence coloring number of Halin graphs and outerplanar graphs[END_REF].

• For every k-degenerated graph G, χ i (G) ≤ ∆(G) + 2k -1 (5).

• For every K 4 -minor free graph G, χ i (G) ≤ ∆(G) + 2 and this bound is tight [START_REF] Hosseini Dolama | Incidence coloring of k-degenerated graphs[END_REF].

• For every cubic graph G, χ i (G) ≤ 5 and this bound is tight [START_REF] Maydanskiy | The incidence coloring conjecture for graphs of maximum degree 3[END_REF].

• For every planar graph G, χ i (G) ≤ ∆(G) + 7 [START_REF] Hosseini Dolama | Incidence coloring of k-degenerated graphs[END_REF].

The maximum average degree of a graph G, denoted by mad(G), is defined as the maximum of the average degrees ad(H) = 2 • |E(H)|/|V (H)| taken over all the subgraphs H of G.

In this paper we consider the class of 3-degenerated graphs (recall that a graph G is k-degenerated if δ(H) ≤ k for every subgraph H of G), which includes for instance the class of triangle-free planar graphs and the class of graphs with maximum average degree at most 3. More precisely, we shall prove the following: In fact we shall prove something stronger, namely that one can construct for these classes of graphs incidence colorings such that for every vertex v, the number of colors that are used on the incidences of the form (w, wv) is bounded by some fixed constant not depending on the maximum degree of the graph.

1. If G is a 3-degenerated graph, then χ i (G) ≤ ∆(G) + 4 (Theorem 2). 2. If G is a graph with mad(G) < 3, then χ i (G) ≤ ∆(G) + 3 (Corollary 5).
More precisely, we define a (k, ℓ)-incidence coloring of a graph G as a k-incidence coloring σ of G such that for every vertex

v ∈ V (G), |σ(A v )| ≤ ℓ.
We end this section by introducing some notation that we shall use in the rest of the paper. Let G be a graph. If v is a vertex in G and vw is an edge in G, we denote by Let G be a graph and σ ′ a partial incidence coloring of G, that is an incidence coloring only defined on some subset I of I(G). For every uncolored incidence (v, vw) ∈ I(G) \ I, we denote by F σ ′ G (v, vw) the set of forbidden colors of (v, vw), that is:

N G (v) the set of neighbors of v, by d G (v) = |N G (v)| the degree of v, by G \ v
F σ ′ G (v, vw) = σ ′ (A v ) ∪ σ ′ (I v ) ∪ σ ′ (I w ).
( We shall often say that we extend such a partial incidence coloring σ ′ to some incidence coloring σ of G. In that case, it should be understood that we set σ(v, vw) = σ ′ (v, vw) for every incidence (v, vw) ∈ I.

) v w u c a v w (2) d u 1 v a 2 u 3 b 3 (3) b 2 u 2 a b G ′ G ′ G ′ 1
We shall make extensive use of the fact that every (k, ℓ)-incidence coloring may be viewed as a (k ′ , ℓ)incidence coloring for any k ′ > k. Drawing convention. In a figure representing a forbidden configuration, all the neighbors of "black" or "grey" vertices are drawn, whereas "white" vertices may have other neighbors in the graph.

3-degenerated graphs

In this section, we prove the following: Theorem 2 Every 3-degenerated graph G admits a (∆(G)+4, 3)-incidence coloring. Therefore, χ i (G) ≤ ∆(G) + 4.

Proof: Let G be a 3-degenerated graph. Observe first that if ∆(G) ≤ 3 then, by Theorem 1, χ i (G) ≤ 2∆(G) < ∆(G) + 4 ≤ 7 and every (∆(G) + 4)-incidence coloring of G is obviously a (∆(G) + 4, 3)incidence coloring.

Therefore, we assume ∆(G) ≥ 4 and we prove the theorem by induction on the number of vertices of G. If G has at most 5 vertices then G ⊆ K 5 . Since for every k > 0, χ i (K n ) = n, we obtain χ i (G) ≤ χ i (K 5 ) = ∆(K 5 ) + 1 = 5, and every 5-incidence coloring of G is obviously a (∆(G) + 4, 3)incidence coloring. We assume now that G has n + 1 vertices, n ≥ 5, and that the theorem is true for all 3-degenerated graphs with at most n vertices.

Let v be a vertex of G with minimum degree. Since G is 3-degenerated, we have d G (v) ≤ 3. We consider three cases according to d G (v).

d G (v) = 1:
Let w denote the unique neighbor of v in G (see Figure 1.(1)). Due to the induction hypothesis, the graph

G ′ = G \ v admits a (∆(G) + 4, 3)-incidence coloring σ ′ . We extend σ ′ to a (∆(G) + 4, 3)- incidence coloring of G. Since |F σ ′ G (w, wv)| = |σ ′ (I w ) ∪ σ ′ (A w )| ≤ ∆(G) -1 + 3 = ∆(G) + 2,
there is a color a such that a / ∈ F σ ′ G (w, wv). We then set σ(w, wv) = a and σ(v, vw) = b, for any color b in σ ′ (A w ).

d G (v) = 2:
Let u, w be the two neighbors of v in G (see Figure 1.( 2)). Due to the induction hypothesis, the graph G ′ = G \ v admits a (∆(G) + 4, 3)-incidence coloring σ ′ . We extend σ ′ to a (∆(G) + 4, 3)incidence coloring σ of G as follows. We first set σ(v, vu) = a for a color

a ∈ σ(A u ) (if d G (u) = 1, we have the case 1). Now, if |σ ′ (A w )| ≥ 2, there is a color b ∈ σ ′ (A w )\{a} and if |σ ′ (A w )| = 1, since |F σ G (v, vw)| = |σ ′ (I w ) ∪ {a}| ≤ ∆(G) -1 + 1 = ∆(G), there is a color b distinct from a such that b / ∈ F σ G (v, vw).
We set σ(v, vw) = b. We still have to color the two incidences (u, uv) and (w, wv). Since a ∈ σ ′ (A u ), we have Observe first that for every i,

|F σ G (u, uv)| = |σ ′ (I u ) ∪ σ ′ (A u ) ∪ {a, b}| ≤ ∆(G) -1 + 3 + 2 -1 = ∆(G) + 3. Therefore, there is a color c such that c / ∈ F σ G (u, uv).
1 ≤ i ≤ 3, since |F σ ′ G (v, vu i )| ≤ ∆(G) -1 and since we have ∆(G) + 4 colors, we have at least five colors which are not in F σ ′ G (v, vu i ).
Moreover, if |A ui | < 3 then any of these five colors may be assigned to the incidence (v, vu i ) whereas we have only three possible choices (among these five) if |A ui | = 3. In the following, we shall see that having only three available colors is enough, and therefore assume that |σ ′ (A ui )| = 3 for every i, 1 ≤ i ≤ 3.

We define the sets B and B i,j as follows:

-∀ i, j, 1 ≤ i, j ≤ 3, i = j, B i,j := (σ ′ (I ui ) ∪ σ ′ (A ui )) ∩ σ ′ (A uj ) -B := 1≤i,j≤3 B i,j , i = j.
We consider now four subcases according to the degrees of u 1 , u 2 and u 3 :

1. ∀ i, 1 ≤ i ≤ 3, d G (u i ) < ∆(G).
In this case, since we have 3 colors for the incidence (v, vu i ) for every i,

1 ≤ i ≤ 3, we can find 3 distinct colors a 1 , a 2 , a 3 such that a i / ∈ F σ ′ G (v, vu i ). We set σ(v, vu i ) = a i for every i, 1 ≤ i ≤ 3.
We still have to color the three incidences

(u i , u i v), 1 ≤ i ≤ 3. Since a i ∈ σ(A ui ), we have |F σ G (u i , u i v)| = |σ(I ui )∪σ(A ui )∪{a 1 , a 2 , a 3 }| ≤ ∆(G)-2+3+3-1 = ∆(G)+3 for every i, 1 ≤ i ≤ 3. So, there exist three colors b 1 , b 2 , b 3 such that b i / ∈ F σ G (u i , u i v), 1 ≤ i ≤ 3. We can extend σ ′ to a (∆(G) + 4, 3)-incidence coloring σ of G by setting σ(u i , u i v) = b i for every i, 1 ≤ i ≤ 3.

Only one of the vertices u i is of degree ∆(G).

We can suppose without loss of generality that

d G (u 1 ), d G (u 2 ) < ∆(G) and d G (u 3 ) = ∆(G). Since |σ ′ (I u3 )∪σ ′ (A u3 )| = ∆(G)-1+3 = ∆(G)+2 and |σ ′ (A u1 )| = 3, we have B 3,1 = ∅. Let a 1 ∈ B 3,1 . Since |σ ′ (A ui )| = 3 for every i, 1 ≤ i ≤ 3, there exist two distinct colors a 2 and a 3 distinct from a 1 such that a 2 ∈ σ ′ (A u2 ) and a 3 ∈ σ ′ (A u3 ). We set σ(v, vu i ) = a i for every i, 1 ≤ i ≤ 3.
We still have to color the three incidences of form (u i , u i v). Since a 1 ∈ B 3,1 and a 3 ∈ σ ′ (A u3 ) we have:

|F σ G (u 3 , u 3 v)| = |σ ′ (I u3 ) ∪ σ(A u3 ) ∪ {a 1 , a 2 , a 3 }| ≤ ∆(G) -1 + 3 + 3 -1 -1 = ∆ + 3
and since a i ∈ σ ′ (A ui ) for every i = 1, 2 we have:

|F σ ′ G (u i , u i v)| = |σ ′ (I ui ) ∪ σ ′ (A ui ) ∪ {a 1 , a 2 , a 3 }| ≤ ∆(G) -2 + 3 + 3 -1 = ∆ + 3.
Therefore, there exist three colors b

1 , b 2 , b 3 such that b i / ∈ F σ G (u i , u i v)∪{a 1 , a 2 , a 3 }, 1 ≤ i ≤ 3. We can extend σ ′ to a (∆(G) + 4, 3)-incidence coloring σ of G by setting σ(u i , u i v) = b i for every i, 1 ≤ i ≤ 3.

Only one vertex among the u i 's is of degree less than ∆(G).

We can suppose without loss of generality that

d G (u 1 ) < ∆(G) and d G (u 2 ) = d G (u 3 ) = ∆(G).
Similarly to the previous case, we have B 2,1 = ∅ and B 3,2 = ∅. We consider two cases:

B 2,1 = B 3,2 Let a 1 ∈ B 2,1 , a 2 ∈ B 3,2 \ {a 1 } and a 3 ∈ σ ′ (A u3 ) \ {a 1 , a 2 }. We set σ(v, vu i ) = a i for every i, 1 ≤ i ≤ 3.
We still have to color the three incidences

(u i , u i v), 1 ≤ i ≤ 3. Since a 1 ∈ σ ′ (A u1 ) we have: |F σ G (u 1 , u 1 v)| = |σ ′ (I u1 ) ∪ σ(A u1 ) ∪ {a 1 , a 2 , a 3 }| ≤ ∆(G) -2 + 3 + 3 -1 = ∆(G) + 3
and since a i ∈ B i+1,i for i = 1, 2 and a j ∈ σ ′ (A uj ) for j = 2, 3, we have:

|F σ G (u i , u i v)| = |σ ′ (I ui ) ∪ σ(A ui ) ∪ {a 1 , a 2 , a 3 }| ≤ ∆(G) -1 + 3 + 3 -1 -1 = ∆(G) + 3. Therefore, there exist three colors b 1 , b 2 , b 3 such that b i / ∈ F σ G (u i , u i v), 1 ≤ i ≤ 3. We can extend σ ′ to a (∆(G) + 4, 3)-incidence coloring σ of G by setting σ(u i , u i v) = b i for every i, 1 ≤ i ≤ 3. B 2,1 = B 3,2 Let a 1 ∈ B 2,1 = B 3,2 , a 2 ∈ σ ′ (A u2 ) \ {a 1 } and a 3 ∈ σ ′ (A u3 ) \ {a 1 , a 2 }. We set σ(v, vu i ) = a i for every i, 1 ≤ i ≤ 3.
We still have to color the three incidences

(u i , u i v), 1 ≤ i ≤ 3. Since a 1 ∈ σ ′ (A u1 ) we have: |F σ G (u 1 , u 1 v)| = |σ ′ (I u1 ) ∪ σ(A u1 ) ∪ {a 1 , a 2 , a 3 }| ≤ ∆(G) -2 + 3 + 3 -1 = ∆(G) + 3
and since a 1 ∈ B 2,1 = B 3,2 and a j ∈ σ ′ (A uj ) for j = 2, 3, we have:

|F σ G (u i , u i v)| = |σ ′ (I ui ) ∪ σ(A ui ) ∪ {a 1 , a 2 , a 3 }| ≤ ∆(G) -1 + 3 + 3 -1 -1 = ∆(G) + 3.
Therefore, there exist three colors b

1 , b 2 , b 3 such that b i / ∈ F σ G (u i , u i v), 1 ≤ i ≤ 3. We can extend σ ′ to a (∆(G) + 4, 3)-incidence coloring σ of G by setting σ(u i , u i v) = b i for every i, 1 ≤ i ≤ 3. 4. d G (u 1 ) = d G (u 2 ) = d G (u 3 ) = ∆(G).
Similarly to the case (b) we have B i,j = ∅ for every i and j, 1 ≤ i, j ≤ 3 and thus |B| ≥ 1.

We prove first that in this case |B| ≥ 2. Suppose that |B| = |{x}| = 1; in other words,

((σ ′ (I ui ) ∪ A ′ ui ) ∩ A ′ uj )
= {x} for every i and j, 1 ≤ i, j ≤ 3. Thus we have:

|σ ′ (A u1 ) ∪ σ ′ (I u1 ) ∪ σ ′ (A u2 ) ∪ σ ′ (A u3 )| = ∆(G) -1 + 3 + 3 + 3 -1 -1 = ∆(G) + 6. (1)
But the relation ( 1) is in contradiction with the fact that σ ′ is a (∆(G) + 4, 3)-incidence coloring and we then get |B| ≥ 2.

Let a 1 and a 2 be two distinct colors in B. We can suppose without loss of generality that a 1 ∈ B 2,1 and a 2 ∈ B 3,2 . We consider the two following subcases:

B 1,3 \ {a 1 , a 2 } = ∅ Let a 3 be a color in B 1,3 \ {a 1 , a 2 }. We set σ(v, vu i ) = a i for every i, 1 ≤ i ≤ 3. Since a i ∈ B j,i = (σ ′ (I uj ) ∪ σ ′ (A uj )) ∩ σ ′ (A ui ), j = i + 1 mod 3, and
a i ∈ σ ′ (A ui )
for every i, 1 ≤ i ≤ 3, we have:

|F σ G (u i , u i v)| = |σ ′ (I ui ) ∪ σ ′ (A ui ) ∪ {a 1 , a 2 , a 3 }| ≤ ∆(G) -1 + 3 + 3 -1 -1 = ∆(G) + 3.
Therefore, there exist three colors b

1 , b 2 , b 3 such that b i / ∈ F σ G (u i , u i v), 1 ≤ i ≤ 3. We can extend σ ′ to a (∆(G) + 4, 3)-incidence coloring σ of G by setting σ(u i , u i v) = b i for every i, 1 ≤ i ≤ 3. B 1,3 \ {a 1 , a 2 } = ∅ Since B 1,3 = ∅ we can suppose without loss of generality that a 2 ∈ B 1,3 . Let a 3 ∈ σ ′ (A u3 ) \ {a 1 , a 2 }. We set σ(v, vu i ) = a i for every i, 1 ≤ i ≤ 3. Since a i ∈ B j,i = (σ ′ (I uj ) ∪ σ ′ (A uj )) ∩ σ ′ (A ui ), j = i + 1 mod 3, and
a i ∈ σ ′ (A ui ) for i = 1, 2, we have: |F σ G (u i , u i v)| = |σ ′ (I ui ) ∪ σ ′ (A ui ) ∪ {a 1 , a 2 , a 3 }| ≤ ∆(G) -1 + 3 + 3 -1 -1 = ∆(G) + 3
and since a 2 ∈ σ ′ (I u1 ) ∪ σ ′ (A u1 ) and a 1 ∈ σ ′ (Au 1 ) we have:

|F σ G (u 1 , u 1 v)| = |σ ′ (I u1 ) ∪ σ ′ (A u1 ) ∪ {a 1 , a 2 , a 3 }| ≤ ∆(G) -1 + 3 + 3 -1 -1 = ∆(G) + 3.
Therefore, there exist three colors b

1 , b 2 , b 3 such that b i / ∈ F σ G (u i , u i v), 1 ≤ i ≤ 3. We can extend σ ′ to a (∆(G) + 4, 3)-incidence coloring σ of G by setting σ(u i , u i v) = b i for every i, 1 ≤ i ≤ 3.
It is easy to check that in all cases we obtain a (∆(G) + 4, 3)-incidence coloring of G and the theorem is proved.

✷

Since every triangle free planar graph is 3-degenerated, we have:

Corollary 3 For every triangle free planar graph G, χ i (G) ≤ ∆(G) + 4.
3 Graphs with bounded maximum average degree

In this section we study the incidence chromatic number of graphs with bounded maximum average degree. The following result has been proved in [START_REF] Hosseini Dolama | Incidence coloring of k-degenerated graphs[END_REF].

Theorem 4 Every k-degenerated graph G admits a (∆(G) + 2k -1, k)-incidence coloring.
Since every graph G with mad(G) < 3 is 2-degenerated, we get the following:

Corollary 5 Every graph G with mad(G) < 3 admits a (∆(G) + 3, 2)-incidence coloring. Therefore,

χ i (G) ≤ ∆(G) + 3.
Concerning planar graphs, we have the following:

Observation 6 (2) For every planar graph G with girth at least g, mad(G) < 2g/(g -2).

Hence, we obtain:

Corollary 7 Every planar graph G with girth g ≥ 6 admits a (∆(G) + 3, 2)-incidence coloring. Therefore, χ i (G) ≤ ∆(G) + 3.

Proof: By Observation 6 we have mad(G) < 2g/(g -2) ≤ (2 × 6)/(6 -2) = 3 and we get the result from Corollary 5. ✷

If the graph has maximum degree at least 5, the previous result can be improved:

Theorem 8 Every graph G with mad(G) < 3 and ∆(G) ≥ 5 admits a (∆(G)+2, 2)-incidence coloring. Therefore, χ i (G) ≤ ∆(G) + 2.
Proof: Suppose that the theorem is false and let G be a minimal counter-example (with respect to the number of vertices). We first show that G must avoid all the configurations depicted in Fig. 2.

v u 1 u 2 u 3 u 4 u 5 w 1 w 2 w 3 w 4 v w v w 2 w 1 (2) d G (w 2 ) < 5 (3) d G (v) = 5 (1) d G (v) = 1
G ′ = G \ v admits a (∆(G) + 2, 2)-incidence coloring σ ′ . We extend σ ′ to a (∆(G) + 2, 2)-incidence coloring σ of G. Since |F σ G (w, wv)| = |σ ′ (I w ) ∪ σ ′ (A w )| ≤ ∆(G) -1 + 2 = ∆(G) + 1
, there is a color a such that a / ∈ F σ G (w, wv). We set σ(w, wv) = a and σ(v, vw) = b, for any color b in σ ′ (A w ). ( 2) Let w 1 , w 2 denote the two neighbors of v in G. Due to the minimality of G, the graph

G ′ = G \ v admits a (∆(G) + 2, 2)-incidence coloring σ ′ . We extend σ ′ to a (∆(G) + 2, 2)-incidence coloring σ of G. Since |F σ G (w 1 , w 1 v)| = |σ ′ (I w1 ) ∪ σ ′ (A w1 )| ≤ ∆(G) -1 + 2 = ∆(G) + 1 and since we have ∆(G) + 2 possible colors, there is a color a such that a / ∈ F σ G (w 1 , w 1 v). We set σ(w 1 , w 1 v) = a. If |σ ′ (A w2 ) \ {a}| ≥ 1 then there is a color b ∈ σ ′ (A w2 ) \ {a} and if σ ′ (A w2 ) = {a}, since |F σ G (v, vw 2 )| = |σ ′ (I w2 )∪{a}| ≤ 3+1 = 4 ≤ ∆(G)-1, there is a color b such that b / ∈ F σ G (v, vw 2 ). We set σ(v, vw 2 ) = b. Now, if |σ ′ (A w1 ) \ {b}| ≥ 1 then there is a color c ∈ σ ′ (A w1 ) \ {b} and if σ ′ (A w1 ) = {b}, since |F σ G (v, vw 1 )| = |σ(I w1 ) ∪ {b}| ≤ ∆(G) + 1, there is a color c such that c / ∈ F σ G (v, vw 1 ). We set σ(v, vw 1 ) = c. Since |F σ G (w 2 , w 2 v)| = |σ ′ (I w2 ) ∪ σ(A w2 ) ∪ {c}| ≤ 3 + 2 + 1 = 6 ≤ ∆(G) + 1, there is a color d such that d / ∈ F σ G (w 2 , w 2 v) and we set σ(w 2 , w 2 v) = d. (3) Let u i , 1 ≤ i ≤ 5,
denote the five neighbors of v and w i denote the other neighbor of u i in G (see Figure 2.(3)). Due to the minimality of G, the graph G ′ = G \ v admits a (∆(G) + 2, 2)-incidence coloring σ ′ . We extend σ ′ to a (∆(G) + 2, 2)-incidence coloring σ of G.

Let

a i = σ ′ (w i , w i u i ), 1 ≤ i ≤ 5.
Since we have ∆(G) + 2 ≥ 7 colors, there is a color x distinct from a i for every i, 1 ≤ i ≤ 5.

Since |F σ ′ G (u i , u i w i )| = |σ ′ (I wi )| ≤ ∆(G)
we have two possible colors for the incidence (u i , u i w i ) for every i, 1 ≤ i ≤ 5. So, we can suppose that σ ′ (u i , u i w i ) = x for every i,

1 ≤ i ≤ 5. We set σ(u i , u i v) = x for every i, 1 ≤ i ≤ 5. Since F σ G (v, vu i ) = {x, σ ′ (u i , u i w i )} for every i, 1 ≤ i ≤ 5
, and since we have at least 7 colors, there is 5 distinct colors c 1 , c 2 ,. . ., c 5 such that c i / ∈ {x, σ ′ (u i , u i w i )}, 1 ≤ i ≤ 5, and we set σ(v, vu i ) = c i for every i, 1 ≤ i ≤ 5.

It is easy to check that in every case we have obtained a (∆(G) + 2, 2)-incidence coloring of G, which contradicts our assumption.

We now associate with each vertex v of G an initial charge d(v) = d G (v), and we use the following discharging procedure: each vertex of degree at least 5 gives 1/2 to each of its 2-neighbors.

We shall prove that the modernized degree d * of each vertex of G is at least 3 which contradicts the assumption mad(G) < 3 (since u∈G d * (u) = u∈G d(u)). Let v be a vertex of G; we consider the possible cases for old degree d G (v) of v (since G does not contain the configuration 2(1), we have d G (v) ≥ 2):

d G (v) = 2.
Since G does not contain the configuration 2(2) the two neighbors of v are of degree at least 5.

Therefore, v receives 1/2 from each of its neighbors so that

d * (v) = 2 + 1/2 + 1/2 = 3. 3 ≤ d G (v) ≤ 4.
In this case we have

d * (v) = d G (v) ≥ 3. d G (v) = 5.
Since G does not contain the configuration 2(3) at least one of the neighbors of v is of degree at least 3 and v gives at most 4 × 1/2 = 2. We obtain

d * (v) ≥ 5 -2 = 3. d G (v) = k ≥ 6. In this case v gives at most k × (1/2) so that d * (v) ≥ k -k/2 = k/2 ≥ 6/2 = 3.
Therefore, every vertex in G gets a modernized degree of at least 3 and the theorem is proved. ✷

Remark 9

The previous result also holds for graphs with maximum degree 2 and for graphs with maximum degree 3 (by the result from ( 6)) but the question remains open for graphs with maximal degree 4.

As previously, for planar graphs we obtain:

Corollary 10 Every planar graph G of girth g ≥ 6 with ∆(G) ≥ 5 admits a (∆(G) + 2, 2)-incidence coloring. Therefore, χ i (G) ≤ ∆(G) + 2.

For graphs with maximum average degree less than 22/9, we have:

Theorem 11 Every graph G with mad(G) < 22/9 admits a (∆(G)+2, 2)-incidence coloring. Therefore,

χ i (G) ≤ ∆(G) + 2.
Proof: It is enough to consider the case of graphs with maximum degree at most 4, since for graphs with maximum degree at least 5 the theorem follows from Theorem 8. Suppose that the theorem is false and let G be a minimal counter-example (with respect to the number of vertices and edges). Observe first that we have ∆(G) ≥ 3 since otherwise we obtain by Theorem 1 that

χ i (G) ≤ 2∆(G) ≤ ∆(G) + 2 and every (∆(G) + 2)-incidence coloring of G is obviously a (∆(G) + 2, 2)-incidence coloring.
We first show that G cannot contain any of the configurations depicted in Figure 3.

(1) This case is similar to case 1 of Theorem 8. (2) Let x (resp. y) denote the other neighbor of u (resp. v) in G. Due to the minimality of G, the graph (3) Let u 1 , u 2 and u 3 denote the three neighbors of v and w i denotes the other neighbor of u i , 1

u x y v v v u u 2 u 1 w 1 w 2 w 3 (1) (2) (3)
G ′ = G\uv admits a (∆(G)+2, 2)-incidence coloring σ ′ . We extend σ ′ to a (∆(G)+2, 2)-incidence coloring σ of G. Suppose σ ′ (u, ux) = a, σ ′ (v, vy) = b, σ ′ (x, xu) = c
≤ i ≤ 3, in G. Due to the minimality of G, the graph G ′ = G \ v admits a (∆(G) + 2, 2)-incidence coloring σ ′ . We extend σ ′ to a (∆(G) + 2, 2)-incidence coloring σ of G.
Suppose that a i = σ ′ (w i , w i u i ), 1 ≤ i ≤ 3. Since we have ∆(G) + 2 ≥ 5 colors, there is a color x distinct from a i for every i, 1 ≤ i ≤ 3.

Since |F σ ′ G (u i , u i w i )| = |σ ′ (I wi )| ≤ ∆(G)
we have at least two colors for the incidence (u i , u i w i ) for every i, 1 ≤ i ≤ 3. Thus, we can suppose σ ′ (u i , u i w i ) = x for every i, 1 ≤ i ≤ 3. We then set σ(u i , u i v) = x for every i,

1 ≤ i ≤ 3. Since F σ G (v, vu i ) = {x, σ ′ (u i , u i w i )} for every i, 1 ≤ i ≤ 3
, and since we have at least 5 colors, there are

3 distinct colors c 1 , c 2 et c 3 such that c i / ∈ {x, σ ′ (u i , u i w i )}, 1 ≤ i ≤ 3. We then set σ(v, vu i ) = c i for every i, 1 ≤ i ≤ 3.
Therefore, in all cases we obtain a (∆(G) + 2, 2)-incidence coloring of G, which contradicts our assumption.

We now associate with each vertex v of G an initial charge d(v) = d G (v), and we use the following discharging procedure: each vertex of degree at least 3 gives 2/9 to each of its 2-neighbors.

We shall prove that the modernized degree d * of each vertex of G is at least 22/9 which contradicts the assumption mad(G) < 22/9. Let v be a vertex of G; we consider the possible cases for old degree d G (v) of v (since G does not contain the configuration 3(1), we have

d G (v) ≥ 2): d G (v) = 2.
Since G does not contain the configuration 3(2) the two neighbors of v are of degree at least 3. Therefore, v receives then 2/9 from each of its neighbors so that d * (v) = 2 + 2/9 + 2/9 = 22/9. Therefore, every vertex in G gets a modernized degree of at least 3 and the theorem is proved. ✷ By considering cycles of length ℓ ≡ 0 (mod 3), we get that the upper bound of Theorem 11 is tight. previously, for planar graphs we obtain:

Corollary 12 Every planar graph G of girth g ≥ 11 admits a (∆(G) + 2, 2)-incidence coloring. Therefore,

χ i (G) ≤ ∆(G) + 2.
Finally, for graphs with maximum average degree less than 16/7, we have:

Theorem 13 Every graph G with mad(G) < 16/7 and ∆(G) ≥ 4 admits a (∆(G) + 1, 1)-incidence coloring. Therefore, χ i (G) = ∆(G) + 1.

Proof: Since for every graph G, χ i (G) ≥ ∆(G) + 1, it is enough to prove that G admits a (∆(G) + 1, 1)incidence coloring. Suppose that the theorem is false and let G be a minimal counter-example (with respect to the number of vertices). We first show that G cannot contain any of the configurations depicted in Figure 4.

(1) This case is similar to case 1 of Theorem 8.

(2) Let u i , i = 1, 2, be the two neighbors of v and w i denote the other neighbor of u i in G. Due to the minimality of G, the graph G ′ = G \ v admits a (∆(G) + 1, 1)-incidence coloring σ ′ . We extend σ ′ to a (∆(G) + 1, 1)-incidence coloring σ of G.

Suppose that σ ′ (w 1 , w

1 u 1 ) = a, σ ′ (u 1 , u 1 w 1 ) = b, σ ′ (w 2 , w 2 u 2 ) = c and σ ′ (u 2 , u 2 w 2 ) = d. Since |F σ ′ G ′ (w 1 , w 1 u 1 ) ∪ {c}| = |σ ′ (I w1 ) \ {a} ∪ σ ′ (A w1 ) ∪ {c}| ≤ ∆(G) -2 + 1 + 1 = ∆(G)
, we can suppose that a = c. We then set σ(v, vu 1 ) = a and σ(v, vu 2 ) = c.

Now, since F σ G (u 1 , u 1 v) ∪ F σ G (u 2 , u 2 v) = {a, b, c
, d} and since we have at least ∆(G) + 1 ≥ 5 colors, there is a color x such that x / ∈ {a, b, c, d}. We then set σ(u

1 , u 1 v) = σ(u 2 , u 2 v) = x.
(3) Let u i , 1 ≤ i ≤ 3 be the three neighbors of v, x i denote the other neighbor of u i and w i denote the other neighbor of x i in G. Due to the minimality of G, the graph G ′ = G \ {v, u 1 , u 2 , u 3 } admits a (∆(G) + 1, 1)-incidence coloring σ ′ . We extend σ ′ to a (∆(G) + 1, 1)-incidence coloring σ of G.

Suppose that σ ′ (w i , w i x i ) = a i and σ ′ (x i , x i w i ) = b i for every i,

1 ≤ i ≤ 3. Since |F σ ′ G (w i , w i x i )∪ {b 1 }| = |σ ′ (I wi ) \ {a i } ∪ {b i , b 1 }| ≤ 2 2 = 4 for i = 2, 3
, and since we have ∆(G) + 1 ≥ 5 colors, we can suppose that a 2 = b 1 = a 3 . We then set σ(u i , u i x i ) = a i and σ(u i , u i v) = b 1 for every i,

1 ≤ i ≤ 3. Since F σ G (v, vu j ) ∪ F σ G (x j , x j u j ) = {b 1 , b j , a j } for j = 2, 3
, there are two distinct colors c 2 and c 3 such that c j / ∈ {b 1 , b j , a j }, j = 2, 3. We set σ(v, vu j ) = σ(x j , x j u j ) = c j , j = 2, 3.

Now, since F σ ′ G (v, vu 1 ) ∪ F σ ′ G (x 1 , x 1 u 1 ) = {a 1 , b 1 , c 2 , c 3
} and since we have at least 5 colors, there is a color c

1 such that c 1 / ∈ {a 1 , b 1 , c 2 , c 3 }. We then set σ(v, vu 1 ) = σ(x 1 , x 1 u 1 ) = c 1 .
Therefore, in all cases we obtain a (∆(G) + 1, 1)-incidence coloring of G, which contradicts our assumption.

We now associate with each vertex v of G an initial charge d(v) = d G (v), and we use the following discharging procedure: (R1) each vertex of degree 3 gives 2/7 to each of its 2-neighbors which has a 2-neighbor adjacent to a 3-vertex and gives 1/7 to its other 2-neighbors.

(R2) each vertex of degree at least 4 gives 2/7 to each of its 2-neighbors and gives 1/7 to each 2-vertex which is adjacent to one of its 2-neighbors.

We shall prove that the modernized degree d * of each vertex of G is at least 16/7 which contradicts the assumption mad(G) < 16/7. Let v be a vertex of G, we consider the possible cases for old degree d G (v) of v (since G does not contain the configuration 4(1), we have d G (v) ≥ 2):

d G (v) = 2.
In this case we consider five subcases:

1. v has two 2-neighbors, say z 1 and z 2 . Let y i be the other neighbor of z i , i = 1, 2, in G. Since G does not contain the configuration 4(2), y i is of degree ∆(G) ≥ 4 for i = 1, 2. Each y i , i = 1, 2, gives 1/7 to v so that d * (v) = 2 + 1/7 + 1/7 = 16/7.

2. v is adjacent to a 3-vertex z 1 and a 2-vertex which is itself adjacent to a 3-vertex. In this case v receives 2/7 from z 1 and we have d * (v) = 2 + 2/7 = 16/7.

3. v is adjacent to a 3-vertex z 1 and a 2-vertex which is itself adjacent to a vertex z 2 of degree at least 4. In this case v receives 1/7 from z 1 and 1/7 from z 2 so that d * (v) = 2 + 1/7 + 1/7 = 16/7.

4. v is adjacent to two 3-vertices that both gives 1/7 to v so that d * (v) = 2 + 1/7 + 1/7 = 16/7.

5. One of the two neighbors of v is of degree at least 4. In this case v receives at least 2/7 so that d * (v) ≥ 2 + 2/7 = 16/7.

d G (v) = 3.
Let u 1 , u 2 and u 3 be the three neighbors of v. We consider two subcases according to the degrees of u i 's.

1. One of the u i 's is of degree at least 3, say u 1 . In this case v gives at most 2/7 to u 2 and 2/7 to u 3 so that d * (v) ≥ 3 -2/7 -2/7 = 17/7 ≥ 16/7.

2.

All the u i 's are of degree 2. Let x i be the other neighbor of u i in G, 1 ≤ i ≤ 3.

(a) One of the x i 's is of degree at least 3, say x 1 . In this case v gives 1/7 to u 1 , at most 2/7 to u 2 and at most 2/7 to u 3 . We then have d * (v) ≥ 3 -1/7 -2/7 -2/7 = 16/7. (b) All the x i 's are of degree 2. Let w i be the other neighbor of x i in G, 1 ≤ i ≤ 3. Since G does not contain the configuration 4(2) we have d G (w i ) ≥ 3 for every i, 1 ≤ i ≤ 3, and since G does not contain the configuration 4(3), at most one of the w i 's, 1 ≤ i ≤ 3, can be of degree 3. Thus, we can suppose without loss of generality that d G (w 1 ) and d G (w 2 ) ≥ 4. In this case, v gives 1/7 to w 1 , 1/7 to w 2 and at most 2/7 to w 3 . We then have d * (v) ≥ 3 -1/7 -1/7 -2/7 = 17/7 ≥ 16/7.

d G (v) = k ≥ 4.
In this case, v gives at most k × (2/7 + 1/7) = 3k/7 so that d * (v) ≥ k -3k/7 = 4k/7 ≥ 16/7.

Therefore, every vertex in G gets a modernized degree of at least 16/7 and the theorem is proved. ✷

Considering the lower bound discussed in Section 1, we get that the upper bound of Theorem 13 is tight.

Remark 14 For every graph G, the square of G, denoted by G 2 , is the graph obtained from G by linking any two vertices at distance at most 2. It is easy to observe that providing a (k, 1)-incidence coloring of G is the same as providing a proper k-vertex-colouring of G 2 , for every k (by identifying for every vertex v the color of A v in G with the color of v in G 2 ). By considering the cycle C 4 on 4 four vertices (note that C 2 4 = K 4 ) we get that the previous result cannot be extended to the case ∆ = 2. Consider now the graph H obtained from the cycle C 5 on five vertices by adding one pending edge with a new vertex. Since H 2 contains a subgraph isomorphic to K 5 , we similarly get that the previous result cannot be extended to the case ∆ = 3.

As previously, for planar graphs we obtain:

Corollary 15 Every planar graph G of girth g ≥ 16 and with ∆(G) ≥ 4 admits a (∆(G) + 1, 1)incidence coloring. Therefore, χ i (G) = ∆(G) + 1.

3 .

 3 If G a graph with mad(G) < 3 and ∆(G) ≥ 5, then χ i (G) ≤ ∆(G) + 2 (Theorem 8). 4. If G is a graph with mad(G) < 22/9, then χ i (G) ≤ ∆(G) + 2 (Theorem 11). 5. If G is a graph with mad(G) < 16/7 and ∆(G) ≥ 4, then χ i (G) = ∆(G) + 1 (Theorem 13).

  the graph obtained from G by deleting the vertex v and by G \ vw the graph obtained from G by deleting the edge vw.

a 3 a 1 b 1 bFig. 1 :

 111 Fig. 1: Configurations for the proof of Theorem 2

  Similarly, since b ∈ σ(A w ), we have |F σ G (w, wv)| ≤ ∆(G) + 3 and there exists a color d such that d / ∈ F σ G (w, wv). We can extend σ ′ to a (∆(G) + 4, 3)-incidence coloring σ of G by setting σ(u, uv) = c and σ(w, wv) = d. d G (v) = 3: Let u 1 , u 2 and u 3 be the three neighbors of v in G (see Figure 1.(3)). Due to the induction hypothesis, the graph G ′ = G \ v admits a (∆(G) + 4, 3)-incidence coloring σ ′ .

a 1 a 2 a 3 a 4 a 5 w 5 Fig. 2 :( 1 )

 521 Fig. 2: Forbidden configurations for the proof of Theorem 8 (1) Let w denote the unique neighbor of v in G. Due to the minimality of G, the graphG ′ = G \ v admits a (∆(G) + 2, 2)-incidence coloring σ ′ . We extend σ ′ to a (∆(G) + 2, 2)-incidence coloring σ of G. Since |F σ G (w, wv)| = |σ ′ (I w ) ∪ σ ′ (A w )| ≤ ∆(G) -1 + 2 = ∆(G) + 1, there is a color a such that a / ∈ F σ G (w, wv). We set σ(w, wv) = a and σ(v, vw) = b, for any color b in σ ′ (A w ). (2) Let w 1 , w 2 denote the two neighbors of v in G. Due to the minimality of G, the graph G ′ = G \ v admits a (∆(G) + 2, 2)-incidence coloring σ ′ . We extend σ ′ to a (∆(G) + 2, 2)-incidence coloring σ of G.

3 Fig. 3 :

 33 Fig. 3: Forbidden configurations for the proof of Theorem 11

  and σ ′ (y, yv) = d. Suppose first that |{a, b, c, d}| = 4. In that case, we set σ(u, uv) = d and σ(v, vu) = c. Now, if |{a, b, c, d}| ≤ 3, we set σ(u, uv) = e and σ(v, vu) = f for any e, f / ∈ {a, b, c, d}.

( 2 ) 3 u2Fig. 4 :

 234 Fig. 4: Forbidden configurations for the proof of Theorem 13


Arthur Holshouser

Harold Reiter
email: hbreiter@email.uncc.edu

Two Pile Move-Size Dynamic Nim

Keywords: Nim, dynamic, combinatorial games

 for a discussion of the single pile game.

Introduction

Two players alternate removing counters from two piles. Each player in his turn first chooses one of the piles, which can change from move to move. He then removes counters from this pile.

An ordered triple (a, b, x) = (b, a, x) of positive integers is called a position, where a and b represent the sizes of the two piles of counters, and x represents the greatest number of counters that can be removed from the chosen pile on the next move. A function f : Z + → Z + is given which determines the maximum size of the next move in terms of the current move size. Thus a move in a game is an ordered pair of positions (a, b, x) → (ak, b, f (k)), where 1 ≤ k ≤ min(a, x), or (a, b, x) → (a, bk, f (k)), where 1 ≤ k ≤ min(b, x). The game ends as soon as one of the two piles is empty, and the winner is the last player to move in the game. At the start of the game, the position (a, b, x) is specified.

We started this project by studying the strategy for the simple move functions f (k) = k, f (k) = 2k, and f (k) = 3k. We then noticed that the smallest winning move size for each of these three functions is computed by the same formula, which we will soon state in the main theorem. We then took upon ourselves the problem of finding (with proof) all functions f : Z + → Z + for which this formula works. This paper gives the complete solution to this problem. This also explains why many of the functions that we must include may seem quite artificial.

As an example, consider the function f (k) = k and the initial position (a, b, x) = [START_REF] Epp | A Note on Takeaway Games[END_REF]4,[START_REF] Conway | On Games and Numbers[END_REF]. This means the first moving player can take 1 or 2 counters from either pile. Suppose he removes 2 counters from the pile with 4 counters. The move can be depicted as (3, 4, 2) → (3, 4 -2, f (2)) = (3, 2, 2). Then the second moving player can remove 1 or 2 from either pile. Suppose he takes 2 from the pile with 2 counters. He wins the game because he has created an empty pile.

Notation. The set of positive integers is denoted by Z + and B = {1, 2, 4, 8, 16, 32, . . . }, the binary base.

Definition 1.

For each positive integer N, g(N) is the greatest power of 2 that divides N. Also, g(0) = ∞. Thus g(1) = 1, g(24) = 8 since 8 | 24 and 16 does not divide 24. Observe that N ≥ g(N), and g(N) ∈ B when N ∈ Z + .

Admissible Functions

Definition 2. A function f : Z + → Z + , f (∞) = ∞, is called admissible if it satisfies the following four conditions: 1. For all N ∈ Z + , f (g(N)) ≤ f (N).

For all

N ∈ B, f (N) < 4N. 3. For all N ∈ B, N ≤ f (N).

For all N

∈ B, f (N) < 2N or N + f (N) ≤ f (2N).
The admissible functions are precisely the ones that satisfy our main theorem. It is easy to see that f (N) = N, f (N) = 2N, f (N) = 3N satisfy these 4 conditions, but f (N) = 4N does not. Also, if r > 0 is a real number, f (N) = ⌊rn⌋ satisfies these 4 conditions if and only if 1 ≤ r < 4. Also, f (N) = ⌈rn⌉ satisfies these 4 conditions if and only if 1 ≤ r ≤ 3. Of course, the functions included in Definition 2 can be far more complex than any of these 'primitive' functions.

We now make the problem more precise.

The Problem

Two players play the game using an admissible function f . If a, b are the two pile sizes, the pile position can be denoted either as (a, b) or as (b, a). For every pile position (a, b), we wish to compute L(a, b), which we define as the least winning move size. This means that a winning move is a remove L(a, b) counters from one of the piles. Of course, L(a, b) by itself does not necessarily tell the player from which pile L(a, b) is to be removed. However, this fact will be revealed in the proof that we soon give. We also state this strategy immediately after the main theorem. Also, if x < L(a, b), the removal of x counters must be a losing move no matter from which of the two piles x counters is removed.

The Solution

We define L(a, b) = ∞ if a = 0 or b = 0 because the game is over once one pile is empty. We can easily see that L(a, b) is the least x ∈ {1, 2, 3, . . . , min{a, b}} such that

f (x) < L(a -x, b) or f (x) < L(a, b -x). Of course, L(a, b) = L(b, a).
In this paper, it is more convenient to denote a pile position as (a, N), where a ≤ b and N = ba. Thus (a, N) means that 'a' is the smaller pile size and N is the difference between the larger pile size and the smaller pile size. Hence we wish to compute L(a, N), 0 ≤ a, 0 ≤ N. Of course, L(0, N) = ∞.

The following theorem finds L(a, N) for all admissible functions.

Main Theorem. Let f : Z + → Z + be an admissible function. For all positions (a, N), where a ≥ 1, the least winning move L(a, N) is computed by the following rule:

Case 1 If a ≤ f (g(N)), then L(a, N) = a. Case 2 If a > f (g(N)), then L(a, N) = g(N). Since g(0) = ∞, f (∞) = ∞ and a < ∞, this means L(a, 0) = a.
Strategy. The strategy also provides a partial outline of the proof of the main theorem.

Case 1 If a ≤ f (g(N)), then L(a, N) = a. The moving player removes a counters from the smaller pile and wins immediately.

Case 2 If a > f (g(N)), then L(a, N) = g(N)
and, from Note 1, which we state and prove in section 5, g(N) < a. The strategy has two subcases.

A. Suppose g(Ng(N)) ≥ 4g(N). This includes the subcase where Ng(N) = 0. The moving player removes g(N) counters from the larger pile.

B. Suppose g(Ng(N)) = 2g(N). Observe that (2(B)1) and (2(B)2) below are not mutually exclusive.

(1) Suppose f (g(N) < 2g(N)). Then the moving player removes g(N) from the larger pile.

(

) Suppose g(N) + f (g(N)) ≤ f (2g(N)). If f (g(N)) < a -g(N) 2
, then the moving player removes g(N) from the smaller pile. But if f (g(N)) ≥ ag(N), then the moving player removes g(N) from the larger pile.

Remark. At the end of the paper, we show that the main theorem is true for an arbitrary f :

Z + → Z + , f (∞) = ∞, if and only if f is admissible. 5 Preliminary Work Note 1. In case 1, L(a, N) = a ≤ f (g(N)). In case 2, L(a, N) = g(N) ≤ f (g(N)) < a, where we note that g(N) ≤ f (g(N)) is true by Condition 3 on f since g(N) ∈ B = {1, 2, 4, 8, . . . }. Therefore, if the main theorem is true for a position (a, N), a ≥ 1, then L(a, N) ≤ a and L(a, N) ≤ f (g(N)). Of course, L(a, N) ≤ a
is also clear since the removal of a counters from the smaller pile is an immediate win. We will prove the main theorem by first proving three lemmas.

Lemma 1. For all x, N ∈ Z + , if g(x) < g(N) and x < N, then g(x) = g(N -x) = g(N + x). If g(x) < g(N) and x > N then g(x) = g(N + x).
Proof. Use the binary representation.

Corollary. If x, N ∈ Z + and x < g(N), then g(x) ≤ x < g(N) ≤ N which implies g(x) = g(N -x) = g(N + x).
Lemma 2. Let f : Z + → Z + be admissible. Suppose x, y ∈ B and x < y. Then f (x) ≤ f (y).

Proof. Suppose f (x) > f (y). Then it is easy to see that there exists x ∈ B such that f (x) > f (2x), since f cannot be non-decreasing on {x, 2x, 4x, 8x, . . . , y}. Now since 2x ∈ B, we know by Condition 3 on

f that f (2x) ≥ 2x. Therefore, f (x) > f (2x) ≥ 2x. This means f (x) > 2x. Therefore, since x ∈ B, we know by Condition 4 on f that x + f (x) ≤ f (2x). Therefore, f (x) < f (2x), which contradicts the fact that f (x) > f (2x).
Given the position (a, N), suppose we remove x counters from the larger pile. The new position becomes (a, Nx) as long as 0 ≤ Nx. However, if Nx < 0, the new position becomes (a + Nx, x -N). This is because when Nx < 0, the smaller pile size becomes a + Nx, the larger pile size becomes 'a' , and the difference between the larger and smaller pile size becomes x -N. We now state Lemma 3. Lemma 3. Suppose f is admissible and the conclusion of the main theorem is true for all positions (a, N), a ≥ 1. For the position (a, N), suppose a ≤ f (g(N)). That is, (a, N) comes under Case 1 of the main theorem ( 4). Suppose x counters are removed from the larger pile, where N < x < a + N. The new position becomes (a + Nx, x -N), where 1 ≤ a + Nx < a and 1 ≤ x -N. Then it cannot be the case that f (x) < L(a + Nx, x -N).

Proof. Since the main theorem is true for the position (a + Nx, x -N) and also 1 ≤ a + Nx < a, 1 ≤ x -N, we know by note 1 that L(a + Nx, x -N) ≤ min a + Nx, f (g(x -N)) . We now consider two cases:

Case A: g(x) = g(N), and Case B:

g(x) = g(N). Case A Since g(x) = g(N) and x -N ≥ 1, it is easy to see that g(x) ≥ g(x -N). Note that g(x) ∈ B, g(x - N) ∈ B. Now from lemma 2 and Condition 1 on f , we know that f (x) ≥ f (g(x)) ≥ f (g(x -N)).
Therefore, if f (x) < L(a + Nx, x -N), we would have (by combining the above information)

f (x) < L(a + N -x, x -N) ≤ f (g(x -N)) ≤ f (x), a contradiction since f (x) < f (x) is impossible.
Case B Since we are assuming in lemma 3 that a ≤ f (g(N)), we have

a ≤ f (g(N)) = f (g(x)) ≤ f (x), where f (g(x)) ≤ f (x) from Condition 1 on f . Therefore, a ≤ f (x). Now f (x) < L(a + N -x, x -N) implies f (x) < L(a + N -x, x -N) ≤ a + N -x < a ≤ f (x), a contradiction since f (x) < f (x) is impossible.
It is important to note that although lemma 3 assumes the main theorem is true for all positions (a, N), a ≥ 1, it can also be used later in the induction argument since 1 ≤ a + Nx < a, the induction will be on a, and we will only be interested in the position (a + Nx, x -N).

Proof of the Main Theorem

Starting the Induction

We now prove that the main theorem is true for all positions (a, N), a ≥ 1, by mathematical induction on a. Of course, L(0, N) = ∞. Now L(1, N) = 1 is obvious for all N since the removal of 1 counter from the smaller pile is an immediate win. Also, a = 1 ≤ f (g(N)) is true for all N, which means that the theorem requires L(1, N) = 1.

Since the induction is started, we can assume the theorem is true for all positions (a, N), a = 1, 2, . . . , a-1, a ≥ 2. We will now prove that the theorem is true for all positions (a, N). We do this by induction on N in the order (a, 0), (a, 1), (1, 2), (a, 3), . . . . First, note that for all positions (a, N), a ≥ 1, it is true that L(a, N) ≤ a. This is because the removal of a counters from the smaller pile is an immediate win since a is the smaller pile size. We now show that L(a, 0) = a, as is required by the theorem. By symmetry, since a = b, we see that L(a, 0) is the least x ∈ {1, 2, . . . , a} such that f (x) < L(ax, x). First, we show that x / ∈ {1, 2, 3, . . . , a -1}. Now f (g(x)) ≤ f (x) by Condition 1 on f . From note 1 (since ax ≥ 1) and from the induction, we know that L(ax, x) ≤ f (g(x)) ≤ f (x). Therefore, if x ∈ {1, 2, . . . , a -1} and f (x) < L(ax, x), we would have f (x) < L(ax, x) ≤ f (x), a contradiction. Of course, when x = a, we have the obvious fact that f (x) = f (a) < L(aa, a) = L(0, a) = ∞. Therefore, L(a, 0) = a is true, as it should be.

Main Induction

Next, we deal successively with L(a, N), N ≥ 1 and N starting at N = 1 and increasing. We assume that main theorem is true for N ∈ {1, 2, . . . , N -1}, and we show it is true for (a, N).

To evaluate L(a, N), we must find the least x ∈ {1, 2, 3, . . . , a} such that (a) f (x) < L(a, Nx), and Nx ≥ 0, or

(b) f (x) < L(a -x, N + x),
where we note in (a) that we only need to consider x where Nx ≥ 0. This is because of two reasons. First, when a > f (g(N)), we need to prove L(a, N) = g(N). Now g(N) ≤ N when N ∈ Z + . Therefore, we only need to consider x in the range 1, 2, 3, . . . g(N), and obviously 0 ≤ Nx in this range. Second, when a ≤ f (g(N)), lemma 3 along with the mathematical induction of those (a, N)'s that we have already dealt with shows us that f (x) < L(a + Nx, x -N) is impossible when 1 ≤ a + Nx < a and Nx < 0. Note that 1 ≤ a + Nx < a when x ∈ {1, 2, 3, . . . , a}, 1 ≤ N, and Nx < 0 which means that the induction on a can be used. This means that lemma 3 can be used with the induction on a since a+N -x < a, a technicality that we mentioned above. We will now consider two cases for (a, N), which correspond to the two cases given in the main theorem.

The Two Cases

Case 1 a ≤ f (g(N)). We must show L(a, N) = a.

Case 2 a > f (g(N)). We must show L(a, N) = g(N).

Case 1 a ≤ f (g(N)). We must show L(a, N) = a. Therefore, we must show that the least x ∈ {1, 2, 3, . . . , a} such that (a) or (b) is true is x = a. Of course, (b) is true for = a since f (a) < L(a-a, N +a) = L(0, N +a) = ∞. So let us show that x ∈ {1, 2, 3, . . . , a -1} will not work in (a) or (b).

We take care of (a) first, and we consider two subcases for (a). Of course, we can assume Nx ≥ 0 in (a) as we have already shown.

Subcase A f (x) ≥ a. If (a) is true, we have f (x) < L(a, N -x) ≤ a ≤ f (x), a contradiction. Note that L(a, N -x)
≤ a is true since for any position (a, N), a ≥ 1, it is always true that L(a, N) ≤ a since a is the smaller pile size.

Subcase B f (x) < a. We have f (x) < a ≤ f (g(N)) from the definitions of Subcase B and Case 1. First, suppose g(N) ≤ g(x). Since g(N) ∈ B, g(x) ∈ B, from lemma 2 and Condition 1 on f we have

f (g(N)) ≤ f (g(x)) ≤ f (x), a contradiction since f (x) < f (g(N)) is true. Therefore, g(x) < g(N) is true. x < N is true since x ≤ N. So by lemma 1, g(x) = g(N -x). Therefore, f (g(N - x)) = f (g(x)) ≤ f (x) by Condition 1 on f . Of course, 1 ≤ N -x is true since x < N. Now if (a) is true, we have f (x) < L(a, N -x) and N -x ≥ 0. Actually N -x ≥ 1. Therefore, f (x) < L(a, N -x) ≤ f (g(N -x)) ≤ f (x), a contradiction. Note 1 and the induction hypothesis implies that L(a, N -x) ≤ f (g(N -x)) since N -x < N and 1 ≤ a.
We next show that x ∈ {1, 2, 3, . . . , a -1} will not work in (b). We consider two subcases.

Subcase A: f (x) ≥ a -x. If (b) is satisfied, f (x) < L(a -x, N + x) ≤ a -x ≤ f (x), a contradiction. Note that L(a -x, N + x) ≤ a -x since L(a, N) ≤ a when a ≥ 1, and 1 ≤ a -x = a. Subcase B: f (x) < a -x. This means that x + f (x) < a. First suppose g(x) ≥ g(N). Therefore, f (x) ≥ f (g(x)) ≥ f (g(N)), by Condition 1 on f and lemma 2 since g(x) ∈ B, g(N) ∈ B. Therefore, x + f (x) ≥ x + f (g(N)) ≥ x + a, definition of Case 1, > a > x + f (x), a contradiction since x + f (x) > x + f (x) is impossible. Therefore, g(x) < g(N) is true. This implies g(x) = g(N + x), lemma 1. Thus f (x) ≥ f (g(x)) = f (g(N + x)) , by Condition 1 on f . But if x satisfies (b), we have f (x) < L(a -x, N + x) ≤ f (g(N + x)) ≤ f (x), a contradiction. By note 1 and the induction L(a -x, N + x) ≤ f ( g(N + x)) since 1 ≤ a -x < a.
We now deal with Case 2.

Case 2

a > f (g(N)). We must show L(a, N) = g(N). Therefore, we must show that the least x ∈ {1, 2, 3, . . . , a} such that (a) or (b) is satisfied is x = g(N) . Of course, N ≥ 1. Note that g(N) ≤ f (g(N)) < a , by Condition 3 on f (since g(N) ∈ B) and the definition of Case 2. Also, remember g(N) ≤ N.

Dealing with x ∈ {1, 2, . . . , g(N) -1}.

Let us first show that x ∈ {1, 2, 3, . . . , g(N) -1} will not work in (a) or (b). Note that Nx ≥ 1 when

x < g(N) ≤ N. Now x < g(N) implies g(x) = g(N -x) = g(N + x) by lemma 1. Therefore, by Condition 1 on f , f (x) ≥ f (g(x)) = f (g(N -x)) = f (g(N + x)).
If (a) is satisfied by x < g(N), we have f (x) < L(a, Nx), 1 ≤ Nx . Therefore, by note 1, the fact that 1 ≤ Nx, and the induction (since

N -x < N), we have f (x) < L(a, N -x) ≤ f (g(N -x)) ≤ f (x), a contradiction. If (b) is satisfied, we have f (x) < L(a -x, N + x) ≤ f (g(N + x)) ≤ f (x), a contradiction. Note that 1 ≤ a -x is true since x < g(N) ≤ f (g(N)
) < a, (as stated above). Thus L(ax, N + x) ≤ f (g(N + x)) follows by note 1, the induction (since ax < a) and 1 ≤ ax.

Dealing with x = g(N).

Let us now show that x = g(N) will satisfy at least one of (a) or (b). We consider two possibilities. Remember, g(N) < a and g(N) ≤ N.

First, suppose g(N-g(N)) g(N)

≥ 4. This also includes the case where Ng(N) = 0, so that g(Ng(N)) = ∞. We show that x = g(N) satisfies (a). That is f (x) < L(a, Nx), 0 ≤ Nx. Of course, 0 ≤ Nx is obvious since g(N) ≤ N. Letting x = g(N), we have g(Nx) ≥ 4x. But f (x) < 4x is true by Condition 2 on f since x = g(N) ∈ B. Therefore, f (x) < 4x ≤ g(Nx). Therefore, f (x) < g(Nx). Also, f (x) = f (g(N)) < a, by the definition of Case 2. Therefore, f (x) = f (g(N)) < L(a, Nx), since f (x) < a and f (x) < g(Nx) and L(a, Nx) ∈ {a, g(Nx)} where we note that L(a, Nx) ∈ {a, g(Nx)} is true by induction since 0 ≤ Nx < N. This means that (a) is satisfied by x = g(N).

Next, suppose g(N-g(N)) g(N)

4. This means g(N-g(N))

g(N) = 2. Now by Condition 4 on f , x = g(N) satisfies either f (x) < 2x or x + f (x) ≤ f (2x) since x = g(N) ∈ B, where B = {1, 2, 4, 8, . . . }. First, suppose f (x) < 2x. We show that x = g(N) satisfies (a). That is, we show f (x) < L(a, N -x) and N -x ≥ 0. Of course, N -x = N -g(N) ≥ 0 is true. Letting x = g(N) in g(N -g(N)) = 2g(N), we have g(N -x) = 2x. This means f (x) = f (g(N)) < 2x = g(N -x). Therefore, f (x) < g(N -x). Also, f (x) = f (g(N)) < a, by the definition of Case 2. Therefore, f (x) = f (g(N)) < L(a, N -x) since f (x) < a, f (x) < g(N -x) and L(a, N -x) ∈ {a, g(N -x)} by the mathematical induction since N -x < N.
This means (a) is satisfied by x = g(N).

We assume x = g(N) satisfies x + f (x) ≤ f (2x) along with the above assumption that x = g(N) satisfies g(Nx) = 2x. Now g(Ng(N)) = 2g(N) implies 4g(N) ≤ g(N + g(N)) since N must be of the binary form

N = XXXX • • • X1100 • • • 00.
That is 4x ≤ g(N + x).

We now consider two subcases, where x = g(N). Recall that f (g(N)) < a in Case 2.

Subcase A:

f (x) < a -x. We show that (b) is satisfied by x = g(N). That is, we show f (x) < L(a -x, N + x). Remember, x = g(N) < a. Now f (x) < 4x, by Condition 2 on f since x = g(N) ∈ B. Therefore, we know f (x) < a -x and f (x) < 4x ≤ g(N + x), when x = g(N). Therefore, f (x) < L(a -x, N + x) since f (x) < a -x, f (x) < g(N + x), 1 ≤ a -x and L(a -x, N + x) ∈ {a -x, g(N + x)}, by the induction since a -x < a. This means (b) is satisfied by x = g(N).
Subcase B: f (x) ≥ ax. We now show that (a) is satisfied by x = g(N). This means that we show f (x) < L(a, Nx). Of course, 0 ≤ Ng(N) = Nx.

Now a ≤ x + f (x) ≤ f (2x)
, by the definition of Subcase B and the above assumption about x. Therefore, a ≤ f (2x). Also, g(Nx) = 2x from the above assumption. Therefore, f (g(Nx)) = f (2x). Thus a ≤ f (2x) = f (g(Nx)). That is, a ≤ f (g(Nx)). Therefore, the induction on the main theorem implies L(a, N -x) = a since N -x < N and a ≤ f (g(N -x)). Also by the definition of Case 2, f (x) = f (g(N)) < a. Therefore, f (x) < L(a, Nx), which means that (a) is satisfied by x = g(N).

We now state the converse of the main theorem.

Converse Theorem. Suppose f : Z + → Z + , f (∞) = ∞, is given, and we play our game with this function f . Suppose also that the conclusion of the main theorem is true for f . Then it is also true that f satisfies all of the 4 conditions listed in Definition 2.

Proof.

(1) We show that f satisfies Condition 1. Therefore, suppose there exists x ∈ Z + such that f (g(x)) > f (x).

We show that this leads to a contradiction. Consider the position (a, N) = ( f (g(x)) + x, 0). Now since the main theorem is true, L( f (g(x)) + x, 0) = f (g(x)) + x. Let us now remove x counters from one of the equal piles. This gives the new position (a, N) = ( f (g(x)), x). Now a = f (g(x)) and f (g(N)) = f (g(x)). Thus a ≤ f (g(N)). Therefore, ( f (g(x)), x) comes under Case 1 of the main theorem, which means L( f (g(x)), x) = f (g(x)).

This also means f (x) < L( f (g(x)), x) = f (g(x)) since we are assuming that f (x) < f (g(x)). Now since x < f (g(x))+x, this means that L( f (g(x))+x, 0) = f (g(x))+x cannot be true, which contradicts the main theorem.

1365-8050 c 2005 Discrete Mathematics and Theoretical Computer Science (DMTCS), Nancy, France

b. f (x) < L( f (x), 4x). Now L(a, N) ≤ a is always true when a ≥ 1 since a is the smaller pile size.

Therefore, (x) < L( f (x), 4x) ≤ f (x) must be true, which is impossible.

The Mis ère Version

The strategy given in this paper cannot be used to play the misère version of this game. The misère version is a totally different game.


Ingrid Falk
email: ifalk@unistra.fr

Delphine Bernhard
email: dbernhard@unistra.fr

Christophe Gérard
email: christophegerard@unistra.fr

From Non Word to New Word: Automatically Identifying Neologisms in French Newspapers

Keywords: neologisms, semi-automatic neologism detection, classification, French, topic modeling

In this paper we present a statistical machine learning approach to formal neologism detection going some way beyond the use of exclusion lists. We explore the impact of three groups of features: form related, morpho-lexical and thematic features. The latter type of features has not yet been used in this kind of application and represents a way to access the semantic context of new words. The results suggest that form related features are helpful at the overall classification task, while morpho-lexical and thematic features better single out true neologisms.

Introduction

The work we present in this paper is concerned with the semi-automatic detection of French neologisms in online newspaper articles. The system we develop, called Logoscope, retrieves newspaper articles from several RSS feeds in French on a daily basis. Using exclusion lists it identifies unknown words, which are then presented to a linguist to decide which of these are valid neologisms. For example, Table 1 shows the most frequent unknown words, collected on July 12, 2013 and resulting from this procedure. The table also illustrates a major drawback of this method. Clearly most of these forms are not interesting neologism candidates: in many cases they are not even valid words and a linguist expert would have to tediously scan a large part of the list before finding interesting candidates. lmd (18) twitter/widgets (7) india-mahdavi (3) pic (this (18) garde-à (6) kilomètresc (2) lazy-retina (9) ex-PPR (4) geniculatus (2) onload (9) pro-Morsi (4) margin-bottom (2) onerror ( 9) tuparkan (4) politique» (2) amp;euro (7) candiudature (3) . . . In this study we investigate methods to select among the detected unknown forms those which most probably represent interesting neologism candidates. We address this task by casting it into a supervised classification problem. The classification is based on different types of features extracted from the collected newspaper articles. A further objective of this paper is to explore which kinds of features are most helpful at detecting the most interesting neologism candidates. The paper is organized as follows. We first briefly present previous work and relate our study to these earlier efforts.

We then detail the resources and methods our experiments are based on and finally present their results.

Previous Work

Methods for the automatic or semi-automatic identification of neologisms mainly target the coinage of new words or changes in part-of-speech (grammatical neologisms), while semantic neologisms are only seldom dealt with.

Identification of Grammatical Neologisms

Grammatical neologisms correspond to attested word forms which are used with a new part-of-speech. This is a rather rare phenomenon, which may nevertheless cause problems for POS taggers. [START_REF] Janssen | NeoTag: a POS Tagger for Grammatical Neologism Detection[END_REF] describes NeoTag, a language independent tagger and lemmatizer, which takes grammatical neologisms explicitly into account. After tagging, the tagged corpus is compared with a lexicographic resource, in order to detect words whose categories are different in the corpus and in the resource.

Given that grammatical neologisms are scarce, we do not address this phenomenon for the time being, but rather focus on the detection of new word forms.

Detection of New Word Forms

For this task, two different types of methods may be distinguished:

• Methods based on lists containing known words in the target language, which are used to identify unknown words. These lists are usually called exclusion lists ;

• Methods relying on various statistical measures or machine learning applied to diachronic corpora.

The use of exclusion lists is by far the most common method. For French, the POMPAMO tool [START_REF] Ollinger | La créativité lexicale : des pratiques sociales aux textes[END_REF] uses an exclusion list made of the French lexicon MORPHALOU 2.0 [START_REF] Romary | Standards going concrete: from LMF to Morphalou[END_REF], a list of named entities and lexicons provided by the user. In addition to the lexicons, the tool uses filters which detect non-alphanumeric characters, numbers and composed word forms. [START_REF] Issac | Cybernéologisme : Quelques outils informatiques pour l'identification et le traitement des néologismes sur le web[END_REF] also describes several filters, aimed at eliminating unwanted neologism candidates not found in the exclusion list. The first filter eliminates non words by looking for bigrams and trigrams of characters which are not found in French. The second filter targets words which are concatenated due to missing spaces and looks for all the possible combinations in a dictionary. Finally, spelling errors are identified by finding corrections with the Levenshtein distance. Systems relying on exclusion lists have also been developed for languages other than French. CENIT -Corpus-based English Neologism Identifier Tool - [START_REF] Roche | Cenit : Système de détection semi-automatique des néologismes[END_REF] uses additional filters which aim at detecting proper nouns. For German, the Wortwarte platform1 collects neologisms on a daily basis [START_REF] Lemnitzer | Mots nouveaux et nouvelles significations -que nous apprennent les mots composés ? Cahiers de lexicologie[END_REF]. All these methods rely on simple heuristics and require that the candidates be manually validated by an expert. Statistical measures can be employed when neologisms are studied from a diachronic point of view. [START_REF] Garcia-Fernandez | Méthodes pour l'archéologie linguistique: datation par combinaison d'indices temporels[END_REF] use the Google Books Ngrams to identify the date of coinage of new words, based on cumulative frequencies for a time period going from 1700 to 2008. The cumulative frequency curve of neologisms is exponential. New words are identified when this cumulative frequency exceeds a given threshold. [START_REF] Cabré | Towards a new approach to the study of neology[END_REF] also exploit this property to identify neologisms in Spanish newspaper texts. Finally, machine learning can be employed to automatically classify neologism candidates. [START_REF] Stenetorp | Automated Extraction of Swedish Neologisms using a Temporally Annotated Corpus[END_REF] presents a method to rank words extracted from a temporally annotated corpus. The features correspond to the number of occurrences of the word in the corpus, the distribution of its occurrences over time, the points in time when the word is observed, lexical cues (quotes, enclosing in specific HTML tags), the presence in dictionaries, and spell-checking.

The main limitation of diachronic methods is that they necessitate a corpus covering a large time span. Moreover, neologisms can only be detected some time after their first occurrence.

The work we present here is an attempt to combine the two main approaches. We use exclusion lists as filters but also apply machine learning techniques to select the most probable neologism candidates. Since we expect the users of our system to be interested in the creation of new words for different reasons and to have different views on the phenomenon, we did not rely on a very specific definition of neologisms. Moreover, our goal is to detect neologisms on their first occurrence, on a daily basis. As a consequence, we do not include diachronic features in our study.

Detection of Novel Word Senses

Here, the aim is to detect new word senses for attested word forms. It is only recently that computational -automatic or semi-automatic-approaches have been proposed for this task. One reason may be its difficulty: in many cases, new word senses may be rather infrequent and thus challenging to detect with corpus-based methods [START_REF] Cook | Automatic identification of words with novel but infrequent senses[END_REF][START_REF] Lau | Word sense induction for novel sense detection[END_REF].

Several different strategies may be employed: (i) study compound word forms, (ii) rely on local lexico-syntactic contexts, or (iii) analyse the wider themes of the text.

For German, [START_REF] Lemnitzer | Mots nouveaux et nouvelles significations -que nous apprennent les mots composés ? Cahiers de lexicologie[END_REF] proposes analyzing novel compound word forms to detect new senses of the base word forms. However, this idea has not been automatized yet. [START_REF] Cook | Automatic identification of words with novel but infrequent senses[END_REF] compare lexico-syntactic representations of word contexts in corpora corresponding to two time periods. They then use synthetic examples built from the Senseval dataset to evaluate their system for the identification of semantic change.

Contextual information is also used by [START_REF] Boussidan | Using topic salience and connotational drifts to detect candidates to semantic change[END_REF] who propose several clues for the detection of semantic change, relying on a co-occurrence based geometrical model. Their model is able to represents thematic clusters but the approach is not fully automatic. Following the same idea, [START_REF] Lau | Word sense induction for novel sense detection[END_REF] apply topic modeling in order to perform word sense induction, and thus detect novel word senses. In this case, topic modeling is not applied to whole documents but to contexts representing target words.

For the identification of novel word senses, two corpora are used: one reference corpus, to represent standard uses and known word senses, and a newer corpus with unknown word senses. Words senses are induced on both corpora and then words are tagged with their most likely sense. A novelty score is then computed, based on the senses observed in the reference corpus and in the newer corpus.

In our work, we do not focus on the detection of novel word senses, as we only target the identification of new word forms. Our work is nevertheless related to previous work in this domain in that we use topic modeling in order to represent the thematic context of unknown words forms, under the assumption that some thematic contexts are more prone to the coinage of words than others.

Experimental Setting

The Data

For our experiments we collected a corpus of French RSS feeds, from the newspapers and on the dates shown in Table 2. We preprocessed the corpus and only kept the journalistic content. The articles were then segmented in sentences and tokenized using the TinyCC tools.2 Finally the tokens were filtered using an exclusion list based mainly on Morphalou [START_REF] Romary | Standards going concrete: from LMF to Morphalou[END_REF] and Wortschatz [START_REF] Biemann | Language-Independent Methods for Compiling Monolingual Lexical Data[END_REF]. We also detect Named Entities using a slightly modified version of the CasEN NER utility [START_REF] Maurel | Cascades de transducteurs autour de la reconnaissance des entités nommées[END_REF]. Finally, we end up with a list of 692 unknown words after filtering. The list of unknown words was further manually categorized into the following classes:

• Plausible words whose form is correct in French. Non words mainly correspond to spelling errors (e.g. candiudature), foreign words (e.g. lazy-retina) and source code which was not stripped from the HTML file (e.g. onload).

• Neologisms which are the candidates our system should eventually extract. Plausible words which are not neologisms correspond mainly to words which should be included in the exclusion lists. 3We performed two series of (supervised) classification experiments. For both the items to be classified are the unknown words not found in the exclusion list (cf.

Features

We explored the effect on the classification of three groups of features: form features, morpho-lexical features and thematic features, an overview of which is presented in Table 3. The form features are the most obvious features to be used in such a classification task. They are related to the form or construction of the string at hand, and are language independent. Table 3a shows some examples of these features. Table 3b gives an overview of the main morpho-lexical features. First, these features check whether particular prefixes and suffixes are present and whether some characters indicate particular languages. 4 Second, we assess the probability that the form might be a spelling error by using the aspell tool. 5 This tool suggests a list of known spellings close to the tested form. The feature we use is the Levenshtein distance to the best guess (or 100 if there is no suggestion).

Based on the observation that unknown forms often arise from missing white space we use a further group of morpho-lexical features to check whether other known forms are possibly included in the form at hand. This group of features is derived from the results of the Aho-Corasick string matching algorithm [START_REF] Aho | Efficient string matching: an aid to bibliographic search[END_REF] 6 which suggests a list of known forms present in the unknown form at hand. Obviously these features depend on morpho-lexical characteristics of French. Since one of the goals of the Logoscope project is to provide means for observing the creation of new words in an enlarged textual context we also focus on the influence of thematic features on the automatic identification of neologisms (Table 3c). Our hypothesis is that these features supply interesting additional information not provided by form related and morpho-lexical features. Besides the obvious Newspaper feature, we attempt to capture the thematic context using topic modeling [START_REF] Steyvers | Probabilistic Topic Models[END_REF]. Topic models are based on the idea that documents are mixtures of topics, where a topic is a probability distribution over words. Given a corpus of documents, standard statistical techniques are used to invert this process and infer the topics (in terms of lists of words) that were responsible for generating this particular collection of documents.

The learned topic model can then be applied to an unseen document and we can thus estimate the thematic content of this document in terms of the inferred topics.

In our experimental setting we use topic modeling as follows. We first assemble a set of general journalistic themes from a large collection of newspaper articles. Based on these topics we then estimate the thematic content of the larger textual context of the unknown words we investigate.

Several studies ( [START_REF] Blei | Topic models[END_REF][START_REF] Hoffman | Online Learning for Latent Dirichlet Allocation[END_REF][START_REF] Hoffman | Stochastic variational inference[END_REF]) show that in general tens or hundreds of thousand documents are needed for a thorough thematic analysis of this kind and that the number of extracted topics is of 100-300. However, for the preliminary study presented here we collected 4,755 articles from the newspapers shown in Table 3c and restricted the number of extracted topics to 10. Each unknown form is associated with 20 topic features (2 features for each of the extracted 10 topics). The first set of 10 features is obtained by first concatenating the sentences containing the unknown form. We then apply the obtained topic model to this text and obtain topic proportions estimating its thematic content. The unknown form is then associated with these topic proportions, representing the weight of each topic in its phrasal contexts. To compute the values of the second set of the 10 topic features we apply our topic model to each article containing the unknown form. For each topic, the unknown form is then associated with the maximal proportion for this topic found in the articles containing the form. Thus, these features represent the predominant topics of the articles containing the unknown forms.

Methodology

The most straightforward way to cast our neologism detection problem into a supervised classification task is to consider the 81 validated neologisms as the positive examples and the remaining 611 unknown words as the negative Length: Number of characters Whether the form contains particular signs, digits, whether it is capitalised, Relative and absolute frequency wrt. to documents and sentences (a) Examples of form related features.

Language Whether the form contains characters indicating a particular language (French, English, German or Spanish, 5 features).

Prefix/suffix 0 or 1 depending on whether a particular prefix or suffix is present. Prefixes: ultra-, super-, dé-, ré-, . . . (69 in total) Suffixes: -iste, -ation, -isme, -itude, . . . (30 in total) Spelling spell-checker (aspell): Is it a spelling error? (2 features) Aho-Corasick algorithm [START_REF] Aho | Efficient string matching: an aid to bibliographic search[END_REF]: Does the form contain other known forms? (4 features) Table 3: Features examples in the training data. This is one of the classification scenarios (called Neologisms) we investigate using the three groups of features presented in Section 3.2. We saw two reasons to also experiment with a second classification scenario. First, as mentioned earlier, it is not always clear when exactly an unknown word turns into a neologism. Second, the strongly imbalanced data suggests that the resulting classification model may possibly be inaccurate. In this second scenario (called Plausible words) we consider the 265 plausible words as positive training examples (and the remaining 427 as negative examples) and explore the impact of the different feature sets on the resulting classifications. The two classification scenarios and the involved data items are illustrated in Figure 1.

Classifier

We used an SVM classifier as implemented in LibSVM [START_REF] Chang | LIBSVM: A library for support vector machines[END_REF] and the Weka tookit [START_REF] Hall | The WEKA data mining software: an update[END_REF]. In the Neologisms classification setting we accounted for the strongly imbalanced data by oversampling the positive class. 7 We then used the LibSVM classifier implemented in Weka with the default settings. 8 In the Plausible words classification scenario the class distribution is less imbalanced, so we used the resampling technique proposed in Weka. We also used a radial basis kernel and performed a grid search for the optimal cost and γ parameters. 9

We perform a 10-fold cross-validation and report precision, recall and F-measure for each class separately and for both classes taken together. We also report the number of detected true neologisms.

When applying the Neologisms classification technique, the detected true neologisms are a direct result of the classification process. In contrast, the Plausible words classification scenario results in those unknown forms which are considered to be plausible words, but which are not necessarily true neologisms. Since ultimately we are interested in these, we also rank the found positive items using the probability estimates output by the LibSVM tool. We then evaluate how many of the true neologisms were among the 81 10 words with highest probability.

Results and Discussion

Results. Table 6 shows the results obtained in the two classification scenarios: Plausible words on the left hand side of Table 6 and Neologisms on the right hand side. We performed the classifications with combinations of the groups of features described in Section 3.2.: form related features, morpho-lexical features and thematic features.

The results are given in terms of precision, recall and Fmeasure for each class and for the overall classification obtained through 10-fold cross validation. We also present the correctly identified neologisms: in the Neologisms scenario these are simply the items classified correctly as positive, whereas in the case of the Plausible words setting these are 7 Oversampling is a classification technique which helps to deal with imbalanced data. The instances of the minority class are duplicated in order to obtain approximately as many instances as in the majority class. We used the Weka cost sensitive classifiers to achieve this.

8 An exponential kernel with cost 1 and γ = 0. 9 We used the scripts provided with the LibSVM tool [START_REF] Chang | LIBSVM: A library for support vector machines[END_REF] for this. 10 Recall that there are 81 validated neologisms to be detected. the validated neologisms ranking in one of the top 81 positions.

First the results show that using the machine learning techniques presented here, the unknown words filtered by our system can be reordered and presented to a human expert in a more meaningful way. Table 4 shows a possible reordering produced by our system. All classifiers show a reasonable performance with respect to the measure which is most relevant for our application: the recall for the positive class, which reflects the number of identified true neologisms.11 Regarding the overall F-measure, the behaviour of both sets of classifiers was similar. The best results were achieved with attribute sets involving the form features (form and thematic features for the Plausible words classification and form attributes only for the Neologisms classification).

For both scenarios the classifications with overall best Fmeasure identified the less validated neologisms.

The settings which provide the best balance between global F-measure and the number of identified neologisms are form+lex for Plausible words and form+lex+theme for Neologisms.

The results suggest that the features used in our experiments were sufficiently powerful to support the Neologism classification scenario outweighing the unbalanced data and the difficulty of the classification task.

Groups of features. The morpho-lexical features proved to be helpful for neologism detection in both classification scenarios. Interestingly, while in the Plausible words setting form features also had a strong impact, in the Neologisms scenario it was the thematic features which played a more important role. First this confirms our intuition that the thematic context is more helpful at the detection of new words than at the detection of plausible words: plausible words may appear in any context whereas this outcome suggests that thematic context is to some extent linked with word creation. This finding is in line with an important line of work in (Textual) Linguistics where word creation is found to correlate with certain discourse types and textual genres (see for example [START_REF] Cabré | L'observatoire de néologie: conception, méthodologie, résultats et nouveaux travaux[END_REF][START_REF] Elsen | Neologismen: Formen und Funktionen neuer Wörter in verschiedenen Varietäten des Deutschen[END_REF][START_REF] Elsen | Neologismen in der Zeitungssprache[END_REF][START_REF] Ollinger | La créativité lexicale : des pratiques sociales aux textes[END_REF]).

Second, this highlights the benefit of using topic modeling for a more compact representation of thematic content insofar as this representation gives some access to the semantic context of unknown forms going beyond the more limited co-occurrence windows. This aspect, as shown in Section 2. is rarely taken into account, theoretically or practically, by recent neologism detection utilities.

Qualitative discussion. For a qualitative analysis of the effect of the various types of features on the selection of valid new words we applied the classification models based on the form, lex, theme and form-lex-theme feature groups on our data and examined the number of correctly identified neologisms and for each group the five best scoring unknown words and the five best scoring validated neologisms. Table 5 shows the results of these experiments.

First we observe that the form features help identify particularly long neologisms, and those containing a hyphen (first line). The second line shows that the words scoring best with the lex features are mainly compositions (with or without hyphen) or contain a prefix (anti, non). With respect to the contextual features (theme) we observe on the positive side that they permit the detection of neologisms with no prominent property (agnélise, retricoté), but on the negative side these thematic features (theme) seem to favour the selection of words which are not plausible considering traditional formation rules for French word forms. A closer look at the neologisms detected through the theme features but not via lex and form features confirmed their ability to select neologisms with less characteristic forms. Some neologisms identified by the theme classifier, but not by the lex and form classifier are: accrobranches, caricatureurs, conflicté, frenemies, instinctivores . . . .

Conclusion and Future Work

In this paper we presented a supervised statistical machine learning method which helps at the identification of new words in online newspaper publications. First we identified words in online newspaper articles which were not present in an exclusion list. Using support vector machines these unknown words were then ranked according to the probability of their being valid neologism candidates, based on different features extracted from the newspaper articles. Despite the relatively small amount of data, our experiments showed that this way the unknown words could be re-arranged in a more meaningful way (than randomly or by frequencies) thus facilitating an analysis by a linguistic expert or lexicographer. We examined the impact on the classification outcome of three groups of features: form features, related to the construction of the word and language-independent, morpholexical features based on lexical characteristics and therefore language dependent and finally theme features which are meant to reflect the larger textual context of the unknown word and have not yet been used to this end (to our knowledge). tion with the best overall F-measure produced the less validated neologisms. 12 Most neologisms were identified using attribute sets involving lexical and thematic features. This highlights the importance of these features and suggests that the classification technique could be further improved by their better integration. Since we found "thematic" features to be of great importance for the neologism detection and documentation we plan to expand our work on detecting and documenting general purpose, journalistic themes, using the topic modeling techniques described in this paper. However, as mentioned in Section 3.2., for a thorough thematic analysis and documentation based on general journalistic themes we need to apply topic modeling on a much larger and more "representative" corpus of newspaper articles. In addition further investigation is needed to determine the influence of other parameters as for example the vocabulary -which words are most meaningful in our setting and therefore are most relevant in the topic selection process, or what number of topics to choose. Further, for documenting the unknown words an interpretation (or labeling) of the topics would be important.

In future work we also plan to exploit other "textual" features which have been found in linguistic studies to play an important role in word creation. Some of these features are:

• The position of the unknown word in the text [START_REF] Loiseau | Un observable pour décrire les changements sémantiques dans les traditions discursives : la tactique sémantique[END_REF].

• The journalistic genre -our hypothesis is that some journalistic genres are more favourable to word creations than others. For this however first a (systematic) categorisation of genres and second a method is needed to better identify the journalistic genre of a newspaper text.

A further interesting research direction is to explore more fine-grained measures in order to better assess the influence of the different features on the classification result.

12 While the number of identified validated neologisms corresponds to the recall in the case of the Neologism experiments, this is not the case for the Plausible words experiments.

In [START_REF] Lamirel | A new feature selection and feature contrasting approach based on quality metric: application to efficient classification of complex textual data[END_REF] the authors propose versatile feature analysis and selection methods allowing to improve the classification results independent of the classification method and to accurately investigate the influence of each feature on the classification process.

Classification

  Figure 1). In one set of experiments the positive examples used to train the classifier are the plausible words (the negative examples being the remaining unknown words). This setting is called Plausible words in the following. In the second set of experiments (called Neologisms) the positive examples used in training are the validated neologisms and the negative examples the remaining unknown words.

  (b) Morpho-Lexical features. Topics 10 topics extracted from 4,755 newspaper articles: Le Monde (898), Libération (269), La Libre (1,784), Presse Europe (690), Le Journal du dimanche (206), Rue89 (212), Slate (74), L'Équipe (892) Topic features: 10 features, proportion of topic in docunewspaper(s) the form appeared in.(c) Thematic features.

  Figure 1: Classification scenarios

Table 1 :

 1 The most frequent unknown words collected on 2013-07-12. Word frequency is shown in parentheses.

Table 2 :

 2 Newspaper corpus collected for our experiments (in parentheses: the number of articles collected for each newspaper).

	Total number of articles: 2,723
	Newspapers: Le Monde (659), Libération (504), l'Équipe
	(594), Les Echos (956)
	Dates: July 12, 16, 19, 23, 25, 30, August 1 2013
	Total number of forms (tokens):	51,000
	Unknown forms (types):	692
	Valid forms (types):	265
	Invalid forms (types):	427
	True neologisms (types):	81

Table 4 :

 4 Top entries in the reordered unknown word list obtained in the Plausible word setting with the lex feature set, the configuration which resulted in the largest number of true neologisms. In parentheses the probability that the unknown form is a plausible word.

Table 5 :

 5 Top 5 predictions when applying the model.

Table 6 :

 6 Classification results

			Plausible words		Neologisms
					form, lex, theme
	class	Prec	Rec	F	corr. neos	Prec	Rec	F	corr. neos
	pos	0.848 0.618 0.715		0.181 0.827 0.297
	neg	0.800 0.932 0.861		0.958 0.512 0.667
	both	0.818 0.813 0.806	24 0.868 0.548 0.625	67
					form, lex
	class	Prec	Rec	F	corr. neos	Prec	Rec	F	corr. neos
	pos	0.822 0.565 0.670		0.192 0.778 0.308
	neg	0.776 0.925 0.844		0.952 0.573 0.716
	both	0.794 0.788 0.778	30 0.864 0.597 0.669	63
					form, theme
	class	Prec	Rec	F	corr. neos	Prec	Rec	F	corr. neos
	pos	0.814 0.687 0.745		0.160 0.531 0.346
	neg	0.825 0.904 0.863		0.912 0.638 0.751
	both	0.821 0.822 0.818	22 0.826 0.625 0.693	43
					form
	class	Prec	Rec	F	corr. neos	Prec	Rec	F	corr. neos
	pos	0.635 0.405 0.494		0.190 0.481 0.273
	neg	0.702 0.857 0.772		0.915 0.733 0.814
	both	0.676 0.686 0.666	20 0.832 0.704 0.752	39
					lex
	class	Prec	Rec	F	corr. neos	Prec	Rec	F	corr. neos
	pos	0.777 0.466 0.582		0.132 0.827 0.227
	neg	0.737 0.918 0.818		0.927 0.288 0.440
	both	0.752 0.746 0.728	34 0.836 0.350 0.415	67
					theme
	class	Prec	Rec	F	corr. neos	Prec	Rec	F	corr. neos
	pos	0.850 0.389 0.534		0.129 0.889 0.225
	neg	0.719 0.958 0.822		0.938 0.217 0.353
	both	0.769 0.742 0.712	22 0.844 0.295 0.338	72
					lex, theme
	class	Prec	Rec	F	corr. neos	Prec	Rec	F	corr. neos
	pos	0.844 0.557 0.671		0.136 0.877 0.236
	neg	0.776 0.937 0.849		0.945 0.275 0.426
	both	0.802 0.793 0.781	29 0.851 0.345 0.404	71

http://www.wortwarte.de

http://wortschatz.uni-leipzig.de/ ~cbiemann/software/TinyCC2.html

However, since it is not always clear whether a word is a neologism, arguably valid unknown words are worth keeping and observing.

 4 We used the Lingua::Identify perl script to this end: http://search.cpan.org/~ambs/ Lingua-Identify-0.56/lib/Lingua/Identify.

pm. 5 http://aspell.net/

We used the Perl implementation available at the url http://search.cpan.org/~vbar/ Algorithm-AhoCorasick-0.03/lib/Algorithm/ AhoCorasick.pm

While the overall F-measure in the Plausible words classification scenario is acceptable, it is lower in the case of the Neologism classification scenario. These results could possibly be improved by also learning the kernel parameters for the oversampled training data. However the absolute F-measure is less important in our setting since we are more interested in the impact of the attribute sets.

Acknowledgements

We thank Romain Potier-Ferry for his contributions. This work was financed by an IDEX 2012 grant from the Université de Strasbourg.