Evangelia Adamou

Reference in Ixcatec (Otomanguean)

Introduction

This paper presents the functional domain of reference in Ixcatec, that is the formal means that Ixcatec uses to identify the participants in the discourse using a non-aprioristic approach (see [START_REF] Frajzyngier | The role of functions in syntax[END_REF]. The coding means may consist of demonstratives, articles, and agreement, among others. The functional subdomains are presented by the name of their function in order to achieve better cross-linguistic comparability, but are introduced by a language-specific definition. Under "constructions", I present the formal means used for this function and under "contrasts" the other, most-closely related functions with which a contrast can be established. Up to four examples are presented in order to illustrate each function, some of them being the prototypical examples, in accordance with the definition, and others more peripheral or problematic. The examples are extracted from the spontaneous conversations and the data elicited through the Pear Stories films [START_REF] Chafe | The Pear Story film[END_REF]. All the data were annotated using the International Phonetic Alphabet (IPA). Glosses follow the standardized glossing rules elaborated within this project under the direction of Bernard Comrie, building on the Leipzig glossing rules.

In the following sections, I present first some background information on Ixcatec. Then I introduce the functional subdomains of reference in detail, followed by a summary and a short conclusion.

Language information

IXCATEC

Name and ISO code : ʃ h wa 2 ni 3 , better known in the literature under the name Ixcatec (IXC), ixcateco (in Spanish), based on Nahuatl ichcatl 'cotton' + -teca/tecatl 'inhabitant of a place (whose name ends in -tlan or -lan)'.

Speakers : Ten identified speakers, of whom only four are fluent. Most of them -with one exception-are in their late 80s. All are bilingual in Spanish. They have had little formal education in Spanish and no formal education in Ixcatec.

Region : Ixcatec is spoken in the municipality of Santa María Ixcatlán in the state of Oaxaca, in Mexico. Today, Santa María Ixcatlán has some 400 inhabitants but at the time of the arrival of the Spaniards in 1522 it was an important centre for the Mixteca zone with an estimated population of 10,000 to 30,000 people.

Classification : Ixcatec belongs to the Popolocan branch of the Otomanguean stock together with Ngiba/Ngigua (also known as Chocho), Popoloc, and Mazatec.

Dialectology : There are no known dialects.

Status :

Ixcatec is a critically endangered language, with less than ten speakers. An orthography was developed in the 1950s by a native Ixcatec speaker, Doroteo Jiménez, in collaboration with linguists of the Instituto Lingüístico de Verano, the Mexican branch of the Summer Institute of Linguistics. Doroteo Jiménez's orthography uses the Latin script and relies on the graphic correspondences with Spanish with some additions when necessary.

20/12/2019

Reference in Ixcatec (Otomanguean) cortypo.huma-num.fr/Archives/exportPredications_N.php 2/6

Main typological features : Ixcatec is a tone language, with three lexically contrastive tones: a high tone, transcribed with a superscripted¹, a mid tone, transcribed with², and a low tone, transcribed with³. Its phonology is complex and not yet well understood. The existence of stress is under discussion. Consonant inventory ranges from 24 to 52 depending on whether glottalized and aspirated consonants are analyzed as clusters of two segments, complex single segments or simple onsets followed by simple nuclei. It has five vowels which may be oral, /a e i o u/, or nasal /ã ẽ ĩ õ ũ/. Ixcatec makes a clear distinction between verbs and nouns; some adjectives may also function as predicates. It is a head-marking language, i.e., grammatical relations are marked on the verb. It has accusative alignment in indexing (A = S ≠ P), i.e., only the single argument of intransitive verbs (S) and the agent-like argument of transitive verbs (A) are indexed on the verb through suffixes. A dozen experience predicates take a different coding, namely through possessive suffixes. Ixcatec is a pro-drop language, i.e., free pronouns are optionally used for all functions, and NPs are generally omitted. It has a VS/SVO unmarked order. When an S argument is moved to the preverbal position, a cross-reference morpheme is suffixed on the verb. The Ixcatec cross-reference morphemes (-da² 'male', -k w a² 'female', and -βa³ 'animal') corefer to nouns formed with the noun classifiers, di²-'man', k w a²-'woman', ʔu²-'animal', to some animate nouns even though they have no classifier, and to the masculine and feminine third singular pronouns which bear the same suffixes as those used for the cross-reference morphemes, i.e., su¹wa¹-da² 'he' and su¹wa¹-kwa² 'she'. Noun classifiers are distinct from so-called class terms which partake in word formation for inanimates but are not associated with any crossreference morphemes.

Functions in the domain of Reference for the language Ixcatec (Otomanguean) Construction Cross-reference morphemes are suffixed on verbs, possessives, and predicate adjectives.

Constraints

The Ixcatec cross-reference morphemes corefer to nouns formed with the noun classifiers di²-'man', kwa²-'woman', ʔu²-'animal', to some animate nouns even though they have no classifier, and to the masculine and feminine third singular pronouns which bear the same suffixes as those used for the cross-reference morphemes, i.e., su¹wa¹-da² ´he´ and su¹wa¹-kwa² ´she´. They are used for S/A arguments only, and only when the N is in marked positions (preverbal and sometimes the head of relative clauses). Because he is scared. The animal didn't bite.

definite Definition

The Ixcatec definite article is used as a definite anaphoric, with a referent which was previously mentioned or a referent which is pragmatically identifiable. The definite article is not used with a referent with generic meaning when it is new (first mentioned) in discourse, but it can be used with a generic referent when it is given (previously mentioned) in discourse. It is regularly used with human proper nouns.

Construction

The definite article sa¹ is used with human, animate, and inanimate nouns and does not inflect for gender or number. It precedes the N (DEF N) and generally attaches phonologically to the postposed noun it modifies. Very frequently though, in natural speech, when there is a pause between the determiner and the noun, it attaches to the preceding prosodic word, regardless of its syntactic function (and this with no obligatory vowel lengthening). Finally, examples where it does not attach to a host have been encountered in the corpus and this led us to abandon the analysis of the definite article as a clitic.

indefinite Definition

The indefinite article, deriving from the numeral ´one´, is not fully grammaticalized in Ixcatec. It introduces a discourse-new participant either in the beginning of a story or in the middle, independent of whether it will become the topic of discussion.

Construction

The numeral hŋgu² 'one' precedes the N.

Constraints

The indefinite article is not used with non-referential and generic nouns.

Contrasts 1) DEF+N 2) bare nouns (used for generic nouns only when they are given in the discourse, for groups of objects, and substances).

proximal reference Definition

The proximal demonstrative indicates that an entity is located close to the speaker and the addressee.

Construction

The proximal demonstrative -ri² is suffixed on the NP. As soon as it ends they go to this party.

distal reference Definition

The distal demonstrative indicates that a referent is located far from the speaker and the addressee. It can also be used to refer to the discourse (endophoric) whether as anaphoric, i.e. referring to the preceding discourse; or recognitional, i.e. referring to entities which are considered to be known by the hearer although they have not been mentioned in the preceding discourse.

Construction

The distal demonstrative -ra² is suffixed on the NP.

Constraints

The demonstratives combine with the definite article sa¹ in 50% of the cases. reportedly they go by day to pour water. She is weaving her hat.

possessive reference Definition

Possession within an NP indicates that an entity X (the possessed) belongs/is related to an entity Y (the possessor).

Construction

Ixcatec expresses nominal possession using the structure 'N1-POSS N2' where N1 is the possessed, N2 the possessor, and the suffix codes the person and number of the possessor. The posssessed can also appear on its own bearing the possessive suffixes. Ixcatec has inalienable possession, e.g. kinship terms are always possessed. Moreover, body part terms bear a specific set of possessive suffixes. He goes for our flowers.

restrictive quantifier Definition

The restrictive quantifier restricts the scope of X (e.g. referent, location, temporal span) in relation to a set of alternatives.

Construction

The restrictive -o² ´just, only´ attaches to nouns, adverbs (locative, manner), demonstratives and locative predicates. They are having it picked up, just that.

universal quantifier Definition

Universal quantifiers indicate that the predicate refers to all the members of a set.

Construction ka² ´all´, ka²na¹ko³ ´everything´

Synthesis & Discussion

In sum, in this study I identified the following reference subdomains in Ixcatec: animate cross-reference, definite indefinite reference, proximal reference, distal reference, reference not identified, possessive reference, restrictive quantifier, and universal quantifier.

The existence of articles in the Popolocan languages in general is not treated in detail. In [START_REF] Adamou | A Corpus-driven Approach to Language Contact[END_REF], I present some preliminary results from Ixcatec in order to evaluate the degree of grammaticalization. The Ixcatec morpheme sa¹ is described as an optional demonstrative by Fernandez de Miranda (1961: 93). Analysis of the contemporary data, however, indicates that sa¹ has been grammaticalized as a definite article. Qualitative analysis of the data shows that the Ixcatec definite article is used as a definite anaphoric, with a referent which was previously mentioned or a referent which is pragmatically identifiable. The Ixcatec definite article is not used with a referent with generic meaning when it is new in discourse, but it can be used with a generic referent when it is given in discourse. Moreover, despite not being very advanced along the grammaticalization path, the Ixcatec definite article is regularly used with human proper nouns, provided they have a lexical classifier, a topic that clearly needs to be further investigated.

Similarly, the existence of a grammaticalized indefinite article is of interest. Ixcatec h ŋgu² 'one' is used as a numeral, but it can also be used to introduce a new participant either in a presentative construction, or with a specific referent independent of whether it will become the topic of discussion. The Ixcatec indefinite is not used with non-specific referents.

Similar to other Mesoamerican languages, Ixcatec expresses nominal possession using the structure 'his-noun 1 noun 2 ' where noun 1 is the possessed and noun 2 the possessor (Campbell, Kaufman and Smith-Stark 1986: 545). Again like other Mesoamerican languages, Ixcatec has inalienable possession, also known as intimate possession (Campbell, Kaufman and Smith-Stark 1986: 549).

Finally, we note that unlike in other Popolocan languages, Ixcatec has a reltively small number of lexical classifiers (Veerman-Leichsenring 2004). For the sake of clarity, the analysis adopted here is to consider the morphemes that have no syntactic effect as part of a lexical derivation process, glossed CLS for "class terms", and the morphemes that have a syntactic component, namely when they trigger cross-reference morphemes on the verb, as lexical classifiers [START_REF] Grinevald | A morphosyntactic typology of classifiers[END_REF].

Most lexical classifiers and class terms are derived from nouns with a generic meaning, such as 'person', 'animal', 'tree', 'flower'.

Conclusion

To conclude, this is a tentative analysis of the Ixcatec functional domain of reference. The description is expected to evolve as more data get analyzed in more detail.

  morphemes indicate identity of reference with some animate S or A-like arguments, only when the NPs occur in the preverbal position or are heads of subject relative clauses (see constraints).

  as they say, my son arrives, Veto, he will go there, ka² me¹ndra² ki¹i² kwa² la² ʔa²ku² ndi¹ʔe¹kwa² /

Contrasts 1 )

 1 INDF (numeral ´one´) 2) bare nouns (used for generic nouns only when they are given in the discourse, for groups of objects, and substances).

  night she is there, sitting there, weaving her hat.

  listener not to search for the referent. It is namely used for generic nouns (only when they are given in the discourse), for groups of objects, and substances. comes out at night, just here she goes. tsi¹ɸi² tjhĩ²na² tsi¹βa²tsi²tʃe²ngi² ʔi²nda² ki¹ ki¹βa²ha² tʃi²tʃʔe¹ /

  Ixcatec language but she can't hear, can't see.ɸu²i¹ʔa²na²ma² o²di²to²ri²o² ʔi¹a²na² lo² tu¹hu² /

  the people are going to inhale, that's why.kwa²ɸi² βi²ka²hu²ku¹ ka²na¹ko³ βi²ka¹ // (IXC_LEA_CONV_02_JSB-RRM_234)


Marthe Bonamy
email: marthe.bonamy@lirmm.fr

Nicolas Bousquet
email: nicolas.bousquet@lirmm.fr

Brooks' theorem on powers of graphs *

We prove that for k ≥ 3, the bound given by Brooks' theorem on the chromatic number of k-th powers of graphs of maximum degree ∆ ≥ 3 can be lowered by 1, even in the case of online list coloring.

Introduction

A graph G = (V, E) is k-colorable if there is a way to color each vertex with an element of {1, • • • , k} so that no two adjacent vertices receive distinct colors. A generalization of kcolorability is list k-colorability (or k-choosability), introduced independently by Vizing [START_REF] Vizing | Colouring the vertices of a graph with prescribed colours (in russian)[END_REF] and Erdős et al. [START_REF] Erdős | Choosability in graphs[END_REF]. The graph G is k-choosable if for every assignment of k colors to each vertex in V , there is a way to color each vertex with an element of its assigned k colors so that no two adjacent vertices have the same color.

Let ∆ ≥ 3. Unless specified otherwise, the graphs considered here are simple, connected and their maximum degree is ∆. Jointly with the assumption that ∆ ≥ 3, this means for example that none of the graphs we consider is a cycle. We recall the following seminal Brooks-like theorem on choosability. Theorem 1. [START_REF] Erdős | Choosability in graphs[END_REF] Except for cliques, every graph is ∆-choosable.

The square G 2 of a graph G = (V, E) is the graph obtained from G by adding all edges between vertices that have a common neighbor. Note that ∆(G 2 ) ≤ ∆ 2 , so Theorem 1 implies that if G 2 is not a clique on ∆ 2 + 1 vertices, then G 2 is ∆ 2 -choosable. In the case ∆ = 3, Theorem 1 ensures that the square of any graph is 9-colorable unless it is a clique. Cranston and Kim [START_REF] Cranston | List-coloring the Square of a Subcubic Graph[END_REF] improved this result and conjectured that it is also true for every ∆. Theorem 2. [START_REF] Cranston | List-coloring the Square of a Subcubic Graph[END_REF] Except for the Petersen graph, the square of any subcubic graph is 8-choosable.

Moore graphs are graphs on ∆ 2 + 1 vertices whose square is a clique [START_REF] Miller | Moore graphs and beyond: A survey of the degree/diameter problem[END_REF]. The Petersen graph is the unique Moore graph with ∆ = 3.

Conjecture 3. [2]

Except for Moore graphs, the square of any graph is (∆ 2 -1)-choosable.

The distance between two vertices u and v in G is the length of a shortest path between them. A generalization of the square of a graph is the k th -power of a graph, for k ∈ N * . The k th -power of G is obtained from G by adding all edges between vertices at distance at most k. We denote D(k, ∆) the greatest maximum degree of a k th -power of a graph of maximum degree ∆. It basically corresponds to the maximum degree of the k th -power of a deep enough ∆-regular tree, and more precisely:

D(k, ∆) = ∆ × k i=1 (∆ -1) i-1 = ∆ × (∆ -1) k -1 ∆ -2
Note that D(2, ∆) = ∆ 2 , hence the following generalizes Conjecture 3:

Conjecture 4. [START_REF] Miao | The Distance Coloring of Graphs[END_REF] For any k ∈ N * , except for Moore graphs when k = 2, the k th power of any graph is (D(k, ∆) -1)-choosable.

In other words, the conjecture states that Theorem 1, which would only yield the result for D(k, ∆), can be strengthened in the case of powers of graphs. The reason why k = 2 is a special case is that there is no such thing as Moore graphs for higher powers (see Lemma 14 in Section 2.1). We prove Conjecture 4 for k ≥ 3.

Theorem 5. For k ≥ 3, the k th power of any graph is (D(k, ∆) -1)-choosable. Independently, Conjecture 4 when k = 2 (i.e. Conjecture 3) has been proved recently by Cranston and Rabern [3].

A generalization of list coloring, namely online list coloring, was recently introduced independently by Schauz [8] and Zhu [START_REF] Zhu | On-line list colouring of graphs[END_REF]. The graph G is k-paintable if, for every assignment of k colors to each vertex, and for every order on the colors, there is an algorithm to color the graph by concealing until step i which vertices contain the i th color in their lists, and deciding on the spot which vertices are colored in i and which not (once colored a vertex cannot be uncolored). Clearly, online list coloring is stronger than list coloring. There exist graphs which are k-choosable but not k-paintable [8], though we do not know any k-choosable graph which is not (k + 1)-paintable [START_REF] Carraher | Three Topics in Online List Coloring[END_REF]. Brooks' theorem is also true in the case of online list coloring [START_REF] Hladký | Brooks Theorem via the AlonTarsi Theorem[END_REF].

We actually prove a stronger version of Theorem 5, as follows.

Theorem 6. For k ≥ 3, the k th power of any graph is (D(k, ∆) -1)-paintable.

Similarly, Cranston and Rabern proved the case k = 2 in the more general setting of list online coloring [3].

We wonder whether the following stronger generalization of Conjecture 3 could be true:

Conjecture 7. For any k ∈ N * , except for a finite number of graphs, the k th power of any graph is

(D(k, ∆) + 1 -k)-choosable.
2 Proof of Theorem 5

Let k ≥ 3. Let G be a graph. Let M = D(k, ∆). Note that M ≥ 21 as ∆ ≥ 3.
We will need the following lemma, which is essentially an easy adaptation of existing results (see Section 2.1 for a proof).

Lemma 8. If G satisfies any of the following:

1. G contains a vertex of degree smaller than ∆.

G contains a cycle shorter than 2k.

3. G contains two intersecting cycles of length 2k.

diam(G) ≤ k.

Then G k is (M -1)-paintable.

Thus we can assume from now on that G is ∆-regular, with g(G) ≥ 2k, diam(G) ≥ k + 1 and that the cycles of length 2k in G are disjoint. Lemma 9. The graph G contains two vertices x 1 and y 1 at distance k + 1 from each other, with two neighbors x 2 , y 2 (respectively) at distance at least k + 1 from each other.

Proof. Since diam(G) ≥ k + 1, G contains two vertices x 1 and y 1 at distance k + 1 from each other. Let us prove that x 1 has a neighbor x 2 and y 1 a neighbor y 2 such that x 2 and y 2 are at distance at least k + 1 from each other. Assume for contradiction that each of the ∆ neighbors of x 1 are at distance at most k from each of the ∆ neighbors of y 1 . Let z be a neighbor of x 1 . Only ∆ -1 neighbors of z can be part of a path of length at most k containing a neighbor of y 1 , as x 1 is itself at distance at least k from all the neighbors of y 1 . Therefore there is a neighbor z ′ of z that belongs to two paths of length at most k -1 to two different neighbors of y 1 . This yields a cycle C of length at most 2k containing y 1 . The cycle C is actually of length 2k and contains z ′ , as z ′ is the endpoint of two different paths of length at most k to y 1 and there is no cycle of length less than 2k by Lemma 8. Consequently, y 1 and z ′ are diametrically opposite on C. Let w be another neighbor of x 1 . By the same argument, a neighbor w ′ of w belongs to a cycle C ′ of length 2k that contains y 1 , and w ′ is diametrically opposite to y 1 in C ′ . Then C and C ′ intersect on y 1 , which by Lemma 8 implies that C and C ′ are actually the same cycle. Thus w ′ and z ′ are actually the same vertex. Now, (w ′ , w, x 1 , z) is a cycle of length 4, a contradiction to Lemma 8 and the fact that k ≥ 3.

We will describe an algorithm to online list color G. Let L be a list assignment of M -1 colors to each vertex. Since we are in the case of online list coloring, the colors will be revealed one after another (at step 1, we learn which vertices contain color 1 in their list, and have to decide on the spot which will be colored in it, and so on).

At any step of the algorithm, the number of constraints of a vertex v is the number of colors in L(v) that appear on vertices at distance at most k from v. Similarly, the number of constraints implied on a vertex v by a set S is the number of colors in L(v) that appear on vertices of S. Note that the number of constraints on a vertex v is bounded by its degree in G k , and that this upper bound is lowered by 1 if two neighbors of v in G k have the same color or if a neighbor of v in G k either is not colored or its color does not belong to L(v).

We consider four vertices x 1 , x 2 , y 1 and y 2 obtained from Lemma 9. Let P be a path of length k + 1 between x 1 and y 1 . Note that by definition of x 2 , y 2 , at most one of them is on P . Let v be a vertex at distance least two on P from both x 1 and y 1 (such a vertex exists since P has length at least 4), and let w be a neighbor of v on P distinct from x 2 and y 2 . Observe that v is at distance at most k from all of x 1 , x 2 , y 1 , y 2 and w is at distance at most k from x 1 , y 1 . Our goal is to set an order on the vertices of G such that by appropriately deciding at each step whether to color or not each vertex in that order, every vertex that is considered for coloring has at most M -2 constraints. The order we choose is x 1 , x 2 , y 1 , y 2 , followed by all other vertices by decreasing distance to {v, w} (the distance to a set is the minimum of the distance to each element of the set). Ties are broken arbitrarily. The order ends with w and then v. Let us now describe more precisely the coloring algorithm. For each new color i:

• Treat the vertices x 1 , x 2 , y 1 and y 2 (in a way described a little bit further).

• Consider all the remaining vertices, one after the other according to the chosen order.

When considering a vertex u, color it with i if i ∈ L(u) and no neighbor of u in G k is colored with i.

(i) If c belongs to L(x 1 ) ∩ L(y 1 ), then color both x 1 and y 1 in c.

(ii) If c belongs to L(x 1 ) or L(y 1 ) but not to L(v), and N O(v) = 0, then color x 1 or y 1 in c.

(iii) If c belongs to L(x 1 ) or L(y 1 ) but not to L(w), and N O(w) = 0, then color x 1 or y 1 in c.

(iv) If c belongs to L(x 1 ) or L(y 1 ), when M -2 colors for the corresponding vertex have already been revealed, then color it in c.

(v) If c belongs to L(x 2 ) ∩ L(y 2 ), then color both x 2 and y 2 in c.

(vi) If c belongs to L(x 2 ) or L(y 2 ) but not to L(v), then color x 2 or y 2 in c.

(vii) If c belongs to L(x 2 ) or L(y 2 ), when at least M -4 colors for the corresponding vertex have already been revealed, then color it in c.

It remains to prove that this yields a coloring of {x 1 , x 2 , y 1 , y 2 } such that v and w can be colored.

Let us first justify that x 1 and y 1 are colored in the desired way (i.e. for both v and w, the set {x 1 , y 1 } implies at most one constraint). If x 1 and y 1 are colored the same, the goal is reached. If the lists L(x 1 ) and L(y 1 ) have no color in common, since |L(x 1 ) ∪ L(y 1 )| > |L(v)|, at least one of them can be colored by (ii) or (iii). Then at least one of x 1 and y 1 is colored in c ∈ L(v) ∩ L(w), assume w.l.o.g. that x 1 is colored that way (and is the first if x 1 and y

1 both are). If c ∈ L(v) ∪ L(w), the vertex y 1 is never colored at (ii) nor (iii) (N O(v) = N O(w) = 1), but it is colored at (iv). If c ∈ L(v) ∪ L(w), assume w.l.o.g. that c ∈ L(v) \ L(w).
Then, since y 1 was not colored before, (ii) did not apply, which means that every color that belonged to L(y 1 ) belonged to L(v). But c ∈ L(v) \ L(y 1 ) (otherwise x 1 and y 1 would be colored the same by (i)). Thus there remain more colors available for y 1 than for v, and (ii) will eventually apply (remember that (iv) does not apply before there is exactly one color left available for y 1 ). Now, let us justify that x 2 and y 2 are colored in the desired way, i.e. if the two are colored then the set {x 2 , y 2 } implies at most one constraint on v. If (v) or (vi) applies, the goal is reached. Let us now prove two things: that one of (v) and (vi) always applies, and that both x 2 and y 2 are colored. Assume that neither (v) nor (vi) apply on x 2 or y 2 . Then (vii) eventually applies as only at most two colors (the colors of x 1 and y 1 ) may not reach (v)-(vii) and we color x 2 (resp. y 2 ) as soon as it has at most 2 colors yet to be revealed (ie, if x 2 was not colored then it had at least 3 colors yet to be revealed). Thus x 2 and y 2 are both colored at the end. Assume that both x 2 and y 2 are colored at (vii). Then (v) never applied, which implies |L(x 2 ) ∩ L(y 2 )| ≤ 2. Consequently, |L(x 2 ) ∪ L(y 2 )| ≥ 2 × (M -1) -2. Since M ≥ 21 and |L(v)| = M -1, it follows that L(x 2 ) ∪ L(y 2 ) contains at least 18 colors that do not belong to L(v). This is a contradiction to the fact that (vi) never applied.

Proof of Lemma 8

In the following section, we prove that the different items of Lemma 8 holds. All the proofs are based on coloring algorithms based on distance, just like the proof of Theorem 5. However, here we do not have to treat vertices differently: it suffices to choose an appropriate order. The resulting proofs are thus much simpler.

Lemma 11. If G contains a vertex of degree ≤ ∆ -1, then G k is (M -1)-paintable.

The authors are supported by the ANR Grant EGOS (2012-2015) 12 JS02 002 01.

The heart of the algorithm consists in making the right decision for {x 1 , x 2 , y 1 , y 2 } at each step, so that v and w each have at most M -2 constraints when it comes to coloring them (note that x 1 , x 2 , y 1 and y 2 are all at distance at most k from v and w). Let us first prove that all the other vertices are colored at the end of the algorithm.

Observation 10. Let u be an uncolored vertex (distinct from x 1 , x 2 , y 1 , y 2 ). Let r(u) be the number of neighbors of u in G k which appear after u in the order. The number of constraints for u is at most Mr(u).

Proof. Let y be a neighbor of u in G k which appears after u. If y is not colored, then y does not imply a constraint on u. Assume that y is colored with color i. Since u is uncolored, it means that when we tried to color u with i, we did not succeed. So either color i does not appear in L(u), and then i does not imply a constraint on u. Or another neighbor y ′ of u, which appears before u in the order, was colored with i and then {y, y ′ } implies only one constraint on u.

Let us first prove that every vertex u / ∈ {x 1 , x 2 , y 1 , y 2 , v, w} is colored at the end of the coloring algorithm (whatever the choices we did for x 1 , x 2 , y 1 , y 2 ). Let us prove that u has at most M -2 constraints i.e. u can be colored since |L(u)| = M -1:

• If u is at distance at most k from both v and w, then both v and w are adjacent to u in G k . Since they are after u in the order, the result holds by Observation 10.

• If u is at distance at least k + 1 from v or w, let P be a shortest path from u to {v, w}. Assume w.l.o.g. that P is a shortest path from u to v. Let z 1 , z 2 and z 3 be the three vertices consecutive to u in P . These vertices exist since Now, let us argue that there is a coloring of {x 1 , x 2 , y 1 , y 2 } that ensures that v and w will be colored.

In standard vertex coloring, we set x 1 and y 1 to color 1, and x 2 and y 2 to color 2: then vertices v and w each have at most M -2 colors appearing on their neighborhood in G k . So they each have at most M -2 constraints and then both v and w are colored at some step of the algorithm.

Since we are considering online list coloring, the procedure is slightly more complicated, though the idea remains the same. We want to make sure that the coloring of {x 1 , y 1 } ensures that v and w both have one less constraint, and the coloring of {x 2 , y 2 } ensures that v has one less constraint. Thus when we consider w, it has one less constraint by {x 1 , y 1 } and one less by v (since w is before v in the order), and then v has two less constraints by {x 1 , y 1 , x 2 , y 2 }.

We proceed as follows. We denote by N O(v) (resp. N O(w)) the number of elements of {x 1 , y 1 } that are colored, minus the number of constraints implied on v (resp. w) by elements of this set. For example, if x 1 and y 1 are colored the same, then N O(v) = 1. The value N O roughly denotes the number of colored vertices in {x 1 , y 1 } which do not create a constraint. For simplicity, we consider L(u) to be empty once u is colored. At the beginning of each step c, we check the following:

Since G is connected, the distance to v is well-defined. Order the vertices by decreasing order to v. At each step of the algorithm, color the vertices by decreasing distance to v. Every vertex x at distance at least two from v has at least two neighbors which are not constraints (indeed the vertices on a shortest path from x to v are considered after the vertex x in the order). For every vertex w which is a neighbor of v, since k ≥ 2, the degree of w in G k is at most M -1. Moreover, the vertex v is considered after the vertex w in the order, so the vertex w can be colored. Since k ≥ 2, ∆ ≥ 3 and d(v) ≤ ∆ -1, the degree of v in G k is at most M -∆ < M -1, so v can be colored.

Thus we assume from now on that G is ∆-regular.

Proof. Assume G contains a cycle C of length at most 2k -1. Let v and w be two adjacent vertices on C. Since C is of length at most 2k -1, the degree of v and w in G k is less than M -1. Then, at each color step, we color as many vertices as possible, by decreasing distance to {v, w} and ending with v and w.

Thus we assume from now on that g(G) ≥ 2k.

Lemma 13. If G contains two intersecting cycles of length 2k, then G k is (M -1)-paintable.

Proof. Assume G contains a vertex v belonging to two cycles of length 2k. Let w be a neighbor of v on one cycle of length 2k. Vertex v has degree at most M -2 in G k , and w at most M -1. Then, at each color step, we color as many vertices as possible, by decreasing distance to {v, w} and ending with w and then v.

Thus we assume from now on that the cycles of length 2k in G are disjoint. Lemma 14. If diam(G) ≤ k then G k is (M -1)-paintable.

Proof. Assume diam(G) ≤ k. Then G contains at most M (k, ∆)+ 1 vertices, and G k is a clique. By [START_REF] Miller | Moore graphs and beyond: A survey of the degree/diameter problem[END_REF], the graph G contains at most M (k, ∆) -1 vertices, hence the result.

Acknowledgements

The authors would like to thank Daniel Cranston for suggesting the generalization to paintability.