Fabienne Tanon

Abdoulaye Sow

Unaccompanied Migrant Minors from Africa: The case of Mauritania

Unaccompanied foreign minors from Mauritania are almost never listed in French published statistics, although they do leave their home country as the alarmist response of local organizations can testify. To understand this apparent contradiction, a study was carried out in Mauritania, involving 395 male minors (15-18 years old) and youths (above 18 years old). The study focused on three cities: Kaédi, Nouakchott and Nouadhibou. Its aim was to shed light on the following questions in order to address this illegal youth migration:

1) What are the main reasons for the illegal migration of minors?

2) Can poverty be considered as the principal cause for this phenomenon?

3) How can the adolescents' attitude toward the risks, including the danger of death, during the crossing be explained? In other words, how can their systematic refusal of fear and denial of death be understood? 4) How can we evaluate the impact of a positive perception regarding illegal migrants as it rises from cultural arguments brought about in society?

What is the positive cultural perception that encourages illegal migration, and then how can we assess its impact on these perceptions and its result. 5) Upon which family strategies and established networks are these departures organized? 6) In what ways do migrant's temporary returns modify family matrimonial ties and pivotal caste structures?

The study focuses on the cultural dynamics involved in this process of the illegal migration of minors and proposes a new way to consider this phenomenon.

Introduction

This article investigates illegal youth migration from Mauritania. The field work conducted by A. Sow took place in three cities during the years 2007-2008 and targeted four samples of the population: adolescent boy and youth migrants; their families; adolescent girls and single young women; and NGOs and representatives of the public sector.

Among the bulk of research into the migration of non-accompanied minors to Europe, and more specifically to France, very little is said regarding adolescents and young men from Mauritania. Nonetheless, their illegal departure from their homeland is observed by local researchers and representatives of NGOs working in the field. This apparent contradiction triggered the study: the need to understand the underground dynamics involved in this whole new phenomenon in order to suggest possible remedies.

In its 2008 report, the Office français de protection des réfugiés et apatrides (OFPRA) indicated that 67% of non-accompanied minors seeking asylum came from the African continent. Among them, natives of the Democratic Republic of Congo (DRC), Angola and Guinea Conakry were the three largest groups. The report made very little mention of minors from Mauritania.

In its annual report (October 2008) the NGO Défense des enfants international -France (DEI-France) pointed to a more diverse panorama of the countries of origin of African unaccompanied minors: Tunisia, Algeria and Morocco were concerned for North Africa, Guinea and Somalia for the South. Once again, the presence of Mauritanians was barely mentioned and not taken into account. However, the report specified that these statistics only dealt with minors who arrived at the Paris-Charles De Gaulle airport. Many others preferred to reach France by land after arriving on a Southern European coast by sea. This is often the case for African immigrants. This information, added to the fact that non-accompanied minors (NAM) from Mauritania are almost invisible in statistics based on the data collected by the Central Direction of Police at Airport Borders (DCPAF), would indicate that these adolescents and young men choose to illegally enter Europe and France by sea.

However, it is significant to note that this absence of visibility regarding young Mauritanian immigrants is somehow in contradiction with data related to adult Mauritanian asylum seekers. In its section on adult immigration, the 2008 OFPRA report indicated that after Mali, the Democratic Republic of the Congo (DRC) and Guinea Conakry, 1184 Mauritanians had requested asylum in 2007-2008. Among the motives indicated on their application forms, excision practices were an important factor in women's applications but the main one related to the political violence and upheaval that took place in August 2008. The political disaster entailed in this military coup, overthrowing the democratically elected president to reinstall a military dictatorship, awakened fears linked to past dramatic discriminations against the Negro-African i part of the population, recalling the so-called "1989 events" in people's memories ii [START_REF] El Yessa | Le retour des réfugiés mauritaniens au Sénégal et au Mali, vingt ans après la crise de[END_REF]. Regarding this country, the number of adult asylum seekers noted by OFPRA underscores a long tradition of migration that has occurred for centuries. First, there has always been a tradition of mobility among its nomadic population. Second, a tradition in which young men seek temporary work to earn the dowry for their wedding often obliged them to travel to neighbouring countries for a year or two until they had collected the necessary amount of money or goods. Later, a third migration movement was oriented towards France which hired many men from its ex-colonial partners for the needs of its industrial development during the 1970's. At that time, the totalitarian regime of Colonel Ould Taya, the ethnic discrimination against Negro-African citizens as well as the rise of the Arabic population -added to the massive deportations of the former -intensified and emphasized the migration of adult men in the late 1980's. In turn, men were followed by women as wives came to join their husbands. This feminine migration began mainly during the early 1990's. The most recent migration involves adolescents and young men and this study focuses on this very recent type of migration, which first appeared in the years 2003[START_REF] Tanon | Migration des jeunes et transformation de la société en Mauritanie[END_REF][START_REF] Tanon | Migration des jeunes et transformation de la société en Mauritanie[END_REF].

The wide publicity given in the media to images of poor fishing boats overloaded with clandestine African people, desperately trying to reach the Spanish or Italian coasts, remains in everyone's memory. Suddenly, Europeans found themselves confronted by the despair of these illegal immigrants and horrified by the idea that all the misery of Africa might invade European countries.

And yet, research by [START_REF] Lessault | Ni invasion, ni exode. Regards statistiques sur les migrations d'Afrique subsaharienne[END_REF] painted another picture closer to reality. By analyzing statistical sources from different institutions and organisations, the authors could identify the movements of foreign populations in France during the past decade. One point clearly stated by the authors is the extreme difficulty of gathering accurate data on this population mobility, due to the lack of coherence among various sources of information and divergent criteria used for counting, which, for example, include or exclude certain segments of the population. And this does not even take illegal entry into French territory into consideration! However it appears that among sub-Saharan Africans, most individuals came from Cameroon and Mali (19.8% and 19.1%), the Ivory Coast (17%) and the Malagasy Republic (7.8%); yet, once again, Mauritanians were not mentioned. This last finding raises questions dealing with the specific characteristics of migration from Mauritania. How can this immigration be so "invisible" in French national statistics? Might it be possible that an immigration that was once massive and legal has now become a more clandestine mobility in reaction to the increased difficulty of obtaining visas from the French Embassy in Nouakchott?

Enhanced border control through the European Agency Frontex might have forced African immigrants to prefer illegal paths to get into Spain and France. If Nouadhibou has become a city of transit for all possible emigrants by boat, as described in previous research [START_REF] Streiff-Fenart | Nouadhibou "Ville de transit"? Le rapport d'une ville à ses étrangers dans le contexte des politiques de contrôle des frontières de l'Europe[END_REF], how can one explain that these same young Mauritanian immigrants no longer appear among refugees and survivors found by Spanish police? Do minors and young men from Mauritania have other networks that support them when they reach the Spanish borders? What are the local support and network dynamics they encounter from the initial project until its final completion? Which connections do they implement to ease their departure as well as their arrival in France? How do they prepare their departure in the country? What consequences do these migrations have on Mauritanian society?

This research is an attempt to answer this set of questions, looking primarily into the phenomenon of non-accompanied minors from the Mauritanian point of view.

Abdoulaye Sow conducted the survey in three cities during the years 2007-2008 and approached this entire study with an epic perspective. As a native anthropologist, he was able to elicit information that would have been impossible to obtain for an external researcher. Regarding this aspect, his contribution is central to this work.

The research work

The aim of the study is to elicit answers to the following questions:

1) What are the true reasons for this clandestine emigration?

2) Can poverty be considered the major cause of this emigration?

3) How can the attitude of these adolescents towards the dangers of the crossing be explained? In other words, how can the constant denial of fear in the face of death be understood? 4) How can the adolescents' positive image which develops in local society, and is expressed through "cultural arguments", be evaluated? 5) Upon which established networks and family strategies are these illegal departures organised and sustained? 6) What are the consequences of this migration on the structures of local society? Data collected for this study involved four samples of the population, and for each one, a specific instrument was developed:

1) Candidates for emigration included 395 minors and young people, between 15 and 25 years of age. This group was subdivided into two groups: the minors per se (15-18 years old) and the youths (18.6 to 25 years old).

2) Adolescent girls and young single women 3) Family members of the candidates for departure to Europe 4) NGOs acting locally and representatives of the public authorities A specific questionnaire was used for each sample of young boys and girls, separate interviews were conducted with the family members and with NGOs and public sector representatives.

This article will focus mainly on results for the first sample including some aspects regarding family practices that provide better understanding and apprehension of this phenomenon of illegal migration of Mauritanian minors to Europe.

Principal findings

The age range of this sample takes into consideration the fact that the threshold of 18 years, so crucial in our western societies due to a drastic change in the legal status of the individuals, does not exist in this African society where the notion of "majority" is linked more to social competences than simple age delineation. Therefore, since the age factor is irrelevant in this context, data will be presented for the whole sample. All the individuals comprising the sample were candidates for the crossing and some had already attempted one without success. Abdoulaye Sow supervised the interviews and was assisted by 6 of his anthropology students who had been specifically trained to distribute the questionnaires. The assistants spoke the different languages used by the young boys and men; the survey took place in three main cities: Kaedi in the South, along the bank of the river Senegal, Nouakchott the capital city and Nouadhibou, the port of departure towards the Spanish coast. Diverse strategies were used to contact the subjects: personal networks and ties in Kaedi (the second author is a native of this city), and local NGOs and social actors working with this population, such as the Red Crescent and the Association Mauritanienne de Lutte contre l'Immigration Illegale for the two other cities.

With regard to the questionnaire for the male subjects, questions were organized according to different topics: their profile description, the motives pushing them to migrate, the crossing and departure preparation, the routes taken and their awareness of the risks taken during the crossing.

Who are they?

The level of instruction and their marital status are distributed as shown in table 1:

Reasons for migration

The quest for social prestige is the primary reason for 52% of the sample, followed by the desire or the necessity to send parents to Mecca for 21% of the subjects, 17%

indicate the need to earn money for a sumptuous wedding ceremony while 11% want to build a large house. Regarding the necessity of administrative papers and procedures to obtain a visa, 51% show a total ignorance of this aspect and 41 % acknowledge the great difficulty or even the impossibility of obtaining any official papers or visas.

Finally, 8% of the subjects indicate that living close to and being familiar with the sea are incentives for undertaking the crossing by sea. Most of them are from Kaedi where fishing is a dominant activity.

One important element to bear in mind here resides in the dynamics linked to the defence of an honour code which represents the main argument provided by these very young migrants (52%) to explain their desire to leave the country, the need to do as the others have done before them in order to be well-perceived within the community. The search for greater social prestige even leads civil servants whose wages are regarded as insufficient to attempt the crossing with the idea of "trying one's luck" on European soil. This point will be discussed later in the next section.

Departure preparations

First, the survey looks at the decision-making processes, through examination of the modalities used to decide who makes a good candidate -or not -for departure.

According to the data, 65% of the sample responded that it depends on their own decision, 22% indicated that the decision is collective, within the family, and 13% mentioned a friend's invitation. However, through long discussions, once a climate of mutual confidence had been established, most of them revealed that candidates are mainly chosen by the family, and especially in Kaedi among Haalpular'en communities.

The candidate's selection is not revealed until a priest or soothsayer called "Timgal" or "Yeewde" has been consulted. This practice of visiting an oracle goes back to the superimposition of animist and religious beliefs. The Timgal belongs to a pagan practice and the Yeewngal pertains to the religious faith. Once deliberation has been made, the future migrant must undertake a mystical preparation. In Kaedi, families participate in the whole process and support the entire project, as interviews with the family members later confirmed. The families of adolescents and young males from other countries could not be interviewed. Subsequent to selection, contacts are made with smugglers, and rituals plus sacrifices are performed to ensure divine protection and luck for the minor during his crossing over the sea.

One important aspect determining the choice of the candidate is its logical path, going from the youngest to the eldest son. Being the eldest in the family assumes a high level of responsibility, which explains why he is the last one to leave. He is the guardian of authority within the clan system, replacing the father in the event of old-age or death.

Thus the young brothers will be preferred; although the eldest might have to leave one day. If he is unable to do so, his brothers living in the Western world have the obligation to finance his wedding and to build him a large house as a means of compensation. This is a real commitment, a moral as well as a material obligation towards the older sibling remaining in the home country.

Choice of countries of destination

France is the preferred destination for 63% of the sample, followed by Italy with 21%,

The Netherlands with 8%, Spain with 5% and Belgium with 3%. The answers clearly show that Spain does not represent a final destination but is merely a point of entry into Europe and a transit country before pursuing the journey. This point may be linked to the fact that in the statistics published by Spain, principally from the Canary Islands, Mauritanians are rarely mentioned iii . They do not intend to stay and prefer not to be recognized as such.

The choice of destination is mainly determined by the presence of close family ties (63%), relatives (13%) or friends (11%). Only 7% mention the presence of more personal relations and 6% of diverse opportunities or incidental relationships. These answers underscore the importance and the role played by parental links and connections in this entire migratory process.

Financing the voyage

With regard to covering the cost of travel, 61% reply that the money is sent by a relative living abroad, generally in the country of destination; 24% cite support from family in their hometown, 10% have money borrowed from friends and 5% use their own savings. Nearly all will therefore have a heavy debt to repay and the burden of this debt is likely to constrain their scope of actions and lead to certain forms of behaviour once they have arrived at their final destination. The expression "to send for one's brother", for instance, means sending the sum of €2000 to €3000 needed to finance the trip. This, in return, constitutes a source of pride for both the immigrant who can provide this amount and the family that receives it so that it can send off another young brother. This financial cycle reflects the permanency of strong family ties on both sides of the Mediterranean between those that have left and those who remain.

The following cost calculation for someone starting from Kaédi gives an idea of the sums involved: the distance to Nouakchott and then on to Nouadhibou (910km) is spent on collective taxis, with an overnight stay with family in Nouakchott. The cost of this trip varies between 7000 and 9000 iv ouguiyas depending on the vehicle used. Once in Nouadhibou the emigrant locates support from relatives or friends, originally from Kaédi and settled in Nouadhibou for a long time. The youths refused to reveal the prices charged for the crossing by boat; however, the foreign clandestine migrants rescued by the police have confessed to a price of €2000 for the crossing. In addition, a passport costs 60,000 ouguiyas and an identity card 25,600 ouguiyas v . To these expenses, the price asked by the "marabou" plus the costs of the rituals and sacrifices need to be added. Therefore, the total amount of €3000 is rather realistic and not exaggerated at all.

Awareness of the risks of the crossing

When asked, 53% of the sample stated they have no knowledge of any dangers, whereas 41% recognized a slight awareness of the risk. This clearly indicates either a refusal to recognize, or a denial of the risks undertaken during the crossing by almost all subjects, while only 6% of them declared it has no importance. This information is corroborated by the answers to the next question about knowing people who have died during the voyage: 71% refused to answer, 25% maintained they did not know anyone and only 4% dared to reveal that they knew of a very small number of cases. With regard to the knowledge of persons who have been forced back and returned to the home country, we find similar percentages: 73% gave elusive answers, 22% asserted they knew none and 5% knew just a few people.

These findings highlight that death remains a taboo topic that nobody wants to address in this context, and that it remains highly repressed. The minors and young men who are sent back to Mauritania avoid returning to their families due to an acute sense of failure, their feeling of shame or "Gacce" dictating their behaviour. Idle, they are obsessed with the idea of attempting the trip once again in the hope of getting through.

The question related to people who have succeeded gave very different results: 78% said they knew some, versus 12% who answered negatively. It is obviously more confidence-building to get close to and remember those who have succeeded than the opposite. This topic aroused real interest among adolescents who suddenly talked eagerly: "managing to leave" and "to reach the country of snow" are a great source of pride and satisfaction. This feeling of pride is largely enhanced by the belief that, once in Europe, they will easily start to work and earn a high salary. This delusion is reinforced thanks to the sums sent by emigrant parents or relatives in France who finance, in part or whole, the trip for the next brothers.

Knowledge of clandestine networks

When asked about these specific networks, 73% preferred not to answer; 18% denied any knowledge, while 9% recognized knowing some of them. This topic is too sensitive to address since relations between smugglers, families and clandestine minors are quite complex. To approach the subject provokes a deep feeling of unease since certain smugglers or members of these networks have relatives in the city of Kaédi. For the young subjects coming from neighbouring countries, this question also creates distrust because their contacts for the passage were made before coming to Mauritania as smugglers select the candidates according to their degree of discretion. Therefore they cannot betray their connections later.

Solutions proposed by adolescents.

This last question probes the opinions of adolescent migrants regarding solutions which might be envisaged to possibly reduce this plight. They are the individuals most concerned by this phenomenon; hence their opinion can provide clues to help understand what changes would allow them to remain in their home country. 41% asked for vocational training whereas 30% did not understand the question and suggested flexible visa regulations from European countries. This group is not likely to remain in the native country, whatever its conditions might be. Another 12% would like increased salaries so they would improve their living conditions within their native country; and merely 7% mentioned the fight against illiteracy. Considering that almost half of the sample is illiterate, this low percentage of answers dealing with illiteracy is surprising. At the same time, the low response is in accordance with the strong belief among the subjects in their capacity to find a job soon after they have arrived in France or Italy. To not consider illiteracy to be a major drawback for finding employment in Europe is not surprising per se, in view of the low rate of schooling in Mauritania.

Indeed, it mirrors the degree of total ignorance regarding regulations and working conditions in Europe.

Following this overall description of their characteristics, drawn from the full set of collected answers, we will now tackle the social perception, in the popular imaginary, of the candidates for departure, so as to better understand the underlying dynamics at work. Therefore let us now turn to the "cultural arguments" that pervade Mauritanian society.

-The cultural arguments

The cultural arguments referred to in this section come within the scope of the American culturalist trend and correspond more specifically to Biarnès' (1996) description:

"It is through "family constellation", and parents plus sibling's psychic reality that each child straightaway discover the values, beliefs, modes of thinking and perceiving people and the world, that is able to locate them and name the links joining them together. In other words, it is within and through his family kinship that the child learns to "decipher the reality", that is to understand the symbolic order of the world" (p.104) vi

The cultural arguments developed here are based on this apprenticeship of the world which inscribes every human being in a process of enculturation that will forge his personality and his future behaviour.

Since half of the sample involves Mauritanian adolescents and young males, some core elements defining the cultural values specific to this country are presented, and more precisely, those relating to the Haalpulaar community.

Kaédi, one of the three cities of this study, is an important centre in the South of the country, located on the North bank of the river Senegal, within a zone of wellestablished emigration towards Europe [START_REF] Adams | Le long voyage des gens du fleuve[END_REF]. Its inhabitants are for the most part Haalpulaar'en. It is also important to note that many families belonging to the Haalpulaar community have been settled in Nouadhibou for more than 30 years. They are employed as seamen on fishing boats as this activity is a traditional one for people living along the river banks, and their proximity to the river makes them the "strategists of the liquid element" who do not fear the sea. In a conceptual context of solidarity, the presence of these families proved to be a real support for the future illegal migrants, as testified by their answers.

To understand the cultural dynamics of the Haalpulaar society requires the discussion of two key-notions defining the person: Gacce and Pasiraagal.

The feeling of Gacce (shame) confirms the ontological identity of a person, interweaving it with the notion of human being. A human being is, above all, a divine creature or "tagoore" which is source and foundation of a person's dignity. This creature is constituted of different aspects such as the body and the conscience or reason.

Contrary to the classical Greek tradition, reason is not the human's defining feature: a person is not just a thinking entity, but above all an individual who feels shame.

According to a Haalpulaar saying, "a man who does not feel shame is not a man". There The sense of shame which permeates the mind of the Haalpulaar'en considers any journey more valuable than an immobile life which would lead to alienating one's freedom and losing one's social prestige. Therefore, the young men who have not emigrated are symbolically considered as "goats". Only the eldest, whose status requires him to remain for the benefit of his younger brothers, will not be regarded as a "goat" due to the social rule that prevents him from shame. A man's value is measured in the face of adversity, which, can be tested, for example, through the violence of the ocean's waves. So, to die on the battle field, as a warrior "beaten by the sword", meaning killed by fire, is now interpreted as "swallowed by the sea". No one mourns a man perceived as a warrior in modern times; in the case of his death, a speech will honour and praise him in front of his family and the public, for he has washed his family's name of shame.

The canoe replaces the horse, and the fisherman does not fear the ocean, just as the warrior did not fear his enemy.

The esteem accorded to the migrant, which is so important in Mauritanian society, instils the minor's departure with a near messianic flair: destiny has selected him to wash away the shame of the entire clan. Families praise the courage of the prospective migrant who is ready to face whatever may befall him, in a quest for moral perfection and rivalry, according to the pasiraagal code, in opposition to the timorous individuals designated as "goats". Even dead, the clandestine migrant has greater merit than the wasteful adolescent who hangs idly about. Having departed to erase shame, he is compelled upon return, to come back with his hands full. This explains why young migrants who are forced back without gaining admission to Europe, experience such a deep sense of shame. On no account can they nor would they even want to return home empty-handed. It would be such a dishonour! Therefore they prefer to wander the streets of Nouakchott or Nouadhibou, seekng only another opportunity to leave.

This study highlights families' attitudes towards young migrants, and demonstrates their complexity. The family gathers, saves resources, and perpetuates convincing cultural arguments that propel clandestine migration. The family hopes for secondary benefits which in turn reinforces its cohesion around the entire migratory project. Family involvement around the adolescent's voyage is rooted in the belief that the young generation's destiny resides in a journey. These youths who voyage are akin to the "Harraga" or "burners of borders" from Morocco, willing to do anything to cross the sea [START_REF] Raimbeau | Harraga: ces enfants qui « brûlent » les frontières[END_REF]. These young migrants' decision is triggered not only by the quest for social prestige and the refusal of becoming the proverbial "goat", but also by the sumptuous gifts and luxurious expenditure that immigrants deploy when they return home during vacations. Consequently, a process of "circularity" of this phenomenon develops in the country, rooted both in the dynamics of the cultural arguments prevailing in the society -building the myth of the migrant as a warrior -and a fascination with hte immigrants' behaviour and lavish life-styles when they come back for short periods. However, the adolescents totally ignore that this apparent wealth belies the true living conditions and life-styles of these immigrants in France or Italy.

Mauritanian immigrants purport to be well-off where in fact they have had to borrow money in France from different sources and networks in order to be able to return for a vacation with "full hands". Once back in France, they will have to pay off this new debt [START_REF] Sow | Les mécanismes du mensonge collectif chez les immigrés mauritaniens en France et les conséquences sur les jeunes au pays. Communication présentée au XIIe Congrés international de l'ARIC[END_REF]. They are thus caught in a pervading, self-perpetuating, collective lie which constitutes a pitfall for the future young migrants, who, as shown by their answers to the questionnaire, are totally ignorant of the real living conditions in Europe.

The realities of this male adolescent migration into Europe have strong consequences on today's Mauritanian society that will be presented in the next section.

-The consequences on Mauritanian society

Mauritanian society is based on a caste system divided into three main groups: the Rimbé or nobles; the Nyeenbé or artisans and the Maccubé or slaves (Tanon and Sow in press). This caste system entails a strict hierarchy not only between castes but even within the different groups within each caste. Human relationships are strictly ruled and defined, according to the Pasiraagal code, as mentioned above. The caste system frames the matrimonial rules and choices in an endogamic mode so that it is not allowed to marry someone who does not belong to the same caste or extended family. This recent migration trend of adolescents and young adults has a wide range of impacts on existing social structures, and we will present some major transformations.

First we will point out some positive effects, such as an improvement in the living conditions of families who do have emigrant members: better housing, access to drinking water, electricity and medical care: with the increasing cost of medical treatments, many people would not be able to get treated without money sent from Europe. There is also a slight increase in attendance at private schools that offer higher quality education. However there also appears, in counterpoint, a tendency to expect help from family members living in Europe and to exert pressure on them to provide for the family's needs.

On the other hand, negative consequences exceed the positive benefits, in some key areas.

In terms of age distribution within the population, a first sign is a decrease in the country's young population. Another sign is the shift in the source of authority:

traditionally, decisions are in the hands of the elders, since gerontocracy is still prevalent; however, the emigrants' influence on the decision-making process at home blurs that tradition. As such, the opinions of the younger siblings -those who have migrated -supersede the voices of their elders and this situation creates tensions and conflicts in families. The principle of authority, based on seniority, tends to be disregarded, provoking conflictual interactions between generations.

Another major influence concerns matrimonial rules. Traditionally, the choice of the The second consequence is the possible transgression of caste barriers: a migrant young adult from a lower caste, with an increased prestige due to his migration, may secure the hand of a girl belonging to the caste just above his own. Because of these changing patterns of marriage strategies, the old matrimonial framework has blurred and brought forth disruptive behaviours among the country's young population.

Moreover, another new phenomenon that has arisen is an increased number in the birth of illegitimate children. After having returned to the homeland to celebrate a sumptuous wedding, the young husband must go back to Europe for work, leaving behind him his young wife. The husband will not be able to revisit his wife for several years (3-4) in that he must re-earn the money spent on his last visit. In the meantime, his wife may give birth to children in her husband's absence. When this man does return, he feels offended by his wife's infidelity and may remarry, as men are allowed to do in polygamous society. Later, he may even divorce his first wife, leaving her subject to stigmatization and discrimination. In addition, as many young adults die during the crossing, there also appear in this society a number of young widows who are then remarried to their brother in law, as per the practice of "levirate". As these two cases indicate, polygamy which had declined in the past decades has increased during the last 5 or 6 years. And how can one oppose such complex family solidarities, institutionalized to such an extent that, from the moment of his arrival on the Spanish coast, everything is meticulously planned with nothing left to chance .None of this plan is written but all of it is anchored in the network of collective memory. We can thus understand better now the weight of cultural arguments in the migrants' denial of danger and the disdain for death during the crossing. This study also shed light on connections among young people in Senegal, Mali and Mauritania since they had cooperatively determined their date of departure as to group together a sufficient number of passengers to fill a single "pirogue" -smugglers considering it unprofitable to load a boat holding fewer than 45 people. A broader survey on this topic, designed from a more comparative perspective, has been conducted in Senegal and Cameroon, by a team of Swiss and African researchers (Bolzman, Gakuba and Guissé, in press).

Recommendations … and conclusion

Migration would never be a solution for sustainable development in African societies.

The departure of this young generation constitutes a serious handicap for the whole community. As Cherif Driss (2007) underlines: "people, who are more cultivated, educated and open to the world, are now choosing to migrate. The numbers speak for themselves: more than 20% of illegal migrants have known a post-secondary education" (p.136). One of the dangers of a "selective immigration" policy, implemented by certain Western countries, is to increase a brain drain from developing countries that will now lack the necessary competencies and skills so vital to their national economic, social and sanitary development.

Why not instead propose the implementation of a new policy negotiated between countries of the North and South of the Mediterranean that would consist in vocational training for most of the young migrants with professional apprenticeships, so they may acquire a skill-set. Only afterwards, would the migrants be asked to return to their home country. The spirit of partnership and transfer of competencies that would result would signify for Europe an affirmed and coherent political turn that would both allow for a limit to this migratory flux and give to the migrant an incentive to return home to invest in his local economy. This is similar to the conditions that India, Korea and China have developed to facilitate a real return of migrants that honoured their dignity (Driss 2007;[START_REF] Kaboret | Eviter la fuite des cerveaux en Afrique subsaharienne: Rôle des institutions sous-régionales de formatoin et de recherche, communication présentée lors de la Conférence régionale sur l'exode des compétences et le développement des capacités en Afrique[END_REF]UNESCO 2004). In order to be effective, such a policy can only be the fruit of balanced negotiations between Northern and Southern countries, just as any strategy fighting migration must take into account the cultural and social dimensions that produce it, not only from the European point of view, but also from the perspectives of the countries of origin.

  is no possible respectability for an individual who does not feel Gacce. Gacce rules the codes of honour, dignity and status. It is the regulatory principle of all social attitudes in the Haalpulaar context, where the axiological dimension of behaviour remains predominant, and where the feeling of shame is the cornerstone of a collective ethics and radically separates humans from animals.Pasiraagal or "ranks of equal births" regulates all interactions, attitudes and behaviour between two or more individuals belonging to the same social level. Pasiraagal structures the ethical code of all castes and provides a system of equivalent levels for persons who share neither the same social birth rank nor the same caste. Pasiraagal, being a pivotal element of social stratification, determines the prerogatives pertaining to each person's social rank. It rules which behaviours and attitudes are to be adopted depending on the circumstances and the social status of interacting people. It defines the marriage code and strategies; it strengthens family bonds and links of solidarity and delineates the various forms of exchange that are permitted. The quest for moral perfection is inseparable from the ideology of Pasiraagal. A certain number of expressions, used by Mauritanians when talking about adolescents and young migrants, illustrate these notions quite well. Here are some examples, regarding two topics: 1) Related to the departure When men go to the forest, Only fools and idiots remain when the goats stay to keep the village brave depart Better to leave looking for something Any travel is better than staying home than to stay behind, living in shame These canoes have replaced the horses Referring to fierce and courageous of time past warriors, in the old days It is the call of the canoes that suppresses To confront dangers by going over shame the sea redeems dignity These youths are the warriors of They are the defenders of honour modern times 2) Related to death and crossing dangers A man is worth more dead than alive At least he dared to attempt the crossing and didn't remain behind Yesterday they fell under the bullets They are the warriors of modern times, today they fall into the sea fallen on the field of honour When the sea is rough, only fishermen Only fishermen are masters can approach the shore of the waves and have no fear The sea waves cannot drown a fisherman Same meaning, a fisherman is stronger than the ocean No one mourns the deaths of those who They courageously defended the left to erase shame family's honour and erased all shame by their departure

  future spouse is made according to the degree of kinship, in the same consanguine group. Choices are usually based on oral commitment and are never written. Yet, currently, families tend to dismiss possible marriage candidates who choose not to emigrate, or are either students or simple craftsmen. Migrant cousins are the most attractive option for future spouses. Another change deals with a new behaviour appearing among young girls: the refusal of a prospective husband should he not satisfy the girl's expectations. From this phenomenon come two consequences. The first one is the emergence of a new type of young woman in Mauritanian society: the unmarried girls aged twenty and older, the equivalent of Western "spinsters". In a society where early marriages are common, girls who remain single after their twentieth birthday are stigmatized.

  Today, it is very difficult to elaborate cultural counter-arguments to discourage future clandestine migration in the mind of this population. Worse, any individual allegedly thriving in Europe, having overcome the challenge of the journey, and having cleansed his family's name of shame, is disqualified from opposing illegal migration. He embodies a new emblematic figure of success whose social visibility is undeniable. Any discourse urging adolescents to remain in the home country is de facto in contradiction with the fundamental pillars of the society, namely the gacce and the pasiraagal code.

Table 1 :

 1 Instruction and marital statusThe nationalities represented in the sample include: 199 Mauritanians, 93 Malians, 61 Guineans, 31 Senegalese and 11 Liberians. The diversity of nationalities confirms the attractiveness of Nouadhibou as a city of transit and departure for sub-Saharan Africans[START_REF] Streiff-Fenart | Nouadhibou "Ville de transit"? Le rapport d'une ville à ses étrangers dans le contexte des politiques de contrôle des frontières de l'Europe[END_REF]. Most of the minors and young Mauritanians came from Kaedi, a southern city mostly inhabited by Haalpular'en people.

	Illiterate	201	Bachelor 275
	Primary education	99	Married with no children 19
	Secondary education	82	Married with children 101
	Tertiary education	13
	Total	395	395

The picture drawn from their answers departs from the common view that young migrants are usually illiterate and jobless. Although a large majority is effectively without any vocational qualification, and illiterate, it is important to note the presence of educated subjects, employed and earning a salary as civil servants or craftsmen. A total of 93 individuals indicate that they have a regular job.


Florent Foucaud

Iiro Honkala

Tero Laihonen

Aline Parreau

Guillem Perarnau

Locally identifying colourings for graphs with given maximum degree 6

Keywords: Graph colouring, identification, maximum degree, chordal graphs

A proper vertex-colouring of a graph G is said to be locally identifying if for any pair u,v of adjacent vertices with distinct closed neighbourhoods, the sets of colours in the closed neighbourhoods of u and v are different. We show that any graph G has a locally identifying colouring with 2∆ 2 -3∆+3 colours, where ∆ is the maximum degree of G, answering in a positive way a question asked by Esperet et al. We also provide similar results for locally identifying colourings which have the property that the colours in the neighbourhood of each vertex are all different and apply our method to the class of chordal graphs.

Introduction

Let G = (V, E) be a simple undirected finite graph. Let c : V → N be a colouring of the vertices of G. For a subset S of V , we denote by c(S) the set of colours that appear in S: c(S) = {c(u) | u ∈ S} and we denote by N (u) (resp. N [u]) the open (resp. closed) neighbourhood of u: N (u) = {v ∈ V | uv ∈ E} (resp. N [u)] = N (u) ∪ {u}).

The colouring c is a locally identifying colouring (lid-colouring for short) if it is a proper colouring (no two adjacent vertices have the same colour) such that for each pair of adjacent vertices u,v with N [u] = N [v], we have c(N [u]) = c(N [v]). A colour belonging to the symmetric difference of c(N [u]) and c(N [v]) is said to separate u from v. An edge uv is said to be bad if

N [u] = N [v] and c(N [u]) = c(N [v]
). So a locally identifying colouring is a proper vertex colouring without any bad edge. The locally identifying chromatic number of G, denoted by χ lid (G), is the minimum number of colours required in any locally identifying colouring of G.

Locally identifying colourings have been introduced in [START_REF] Esperet | Locally identifying colourings of graph[END_REF] and are related to identifying codes [START_REF] Karpovsky | On a new class of codes for identifying vertices in graphs[END_REF][START_REF] Lobstein | Identifying and locating-dominating codes in graphs[END_REF], distinguishing colourings [START_REF] Balister | Vertex-distinguishing edge-colorings of graphs[END_REF][START_REF] Burris | Vertex-distinguishing proper edge-colorings[END_REF][START_REF] Cerný | Observability of a graph[END_REF] and locating-colourings [START_REF] Chartrand | The locating-chromatic number of a graph[END_REF]. An open question asked in [START_REF] Esperet | Locally identifying colourings of graph[END_REF] was to know whether one can find a locally identifying colouring of a graph G with O(∆ 2 ) colours, where ∆ is the maximum degree of G. Examples using the projective plane provide graphs G with χ lid (G) = ∆ 2 -∆ + 1 (see [START_REF] Esperet | Locally identifying colourings of graph[END_REF]). In this note, we show that we always have χ lid (G) ≤ 2∆ 2 -3∆ + 3, answering in a positive way the question asked in [START_REF] Esperet | Locally identifying colourings of graph[END_REF]. The result is effective: we give a construction for a locally identifying colouring with 2∆ 2 -3∆ + 3 colours. This construction can be slightly modified, using 2∆ 2 -∆+1 colours to provide a locally identifying colouring which has the property that the colours in the neighbourhood of each vertex are all distinct. We finally consider the class of chordal graphs, for which it is conjectured in [START_REF] Esperet | Locally identifying colourings of graph[END_REF] that χ lid (G) ≤ 2χ(G), for any chordal graph G. We give a bound for this class in terms of ∆ and χ, in the direction of the previous conjecture. For terminology and notations of graph theory, we refer to the book [START_REF] Bondy | Graph Theory[END_REF].

Upper bound in terms of the maximum degree

The following lemma shows that, given a locally identifying colouring, we can change the colour of a single vertex in a number of ways, without sacrificing the property that the colouring is locally identifying.

Lemma 1 (Recolouring Lemma). Let G be a graph with maximum degree ∆ ≥ 3. Let v be a vertex of degree d. Assume that G has a locally identifying colouring c with strictly more than 2d(∆ -1) colours. Then, there is a list L of colours of size at most 2d(∆ -1) such that if we colour v with a colour not in L, the colouring remains locally identifying.

Proof. Let v 1 , ..., v d be the neighbours of v. For each vertex v i , let u i,1 , ..., u i,si be the neighbours of v i that are not neighbours of v, see Figure 1. For 1 ≤ i ≤ d, we construct a list L i of colours with at most 2(∆ -1) colours. We first put c If there is a vertex u i,j such that c(N [u i,j ]) = c(N [v i ] \ {v}), (in other words, u i,j is separated from u i only by the colour of v), then we say that v i is of type A and we add to L i all the colours of c(N [v i ] \ {v}). We add at this point at most ∆ -1 colours because c(v i ) is already in L i . Then, for all vertices u i,j ′ such that c(N

(v i ) in L i . v v 1 v 2 . . . v i . . . v d u 1,1 . . . u 1,s1 u i,1 . . . u i,si u d,1 . . .
[u i,j ′ ]) \ c(N [v i ] \ {v}) is not empty, we add an arbitrary colour of c(N [u i,j ′ ]) \ c(N [v i ] \ {v}) to L i .
In this step, we add at most ∆ -2 colours because j ′ = j. Therefore, in the end

|L i | ≤ 2(∆ -1).
Otherwise, we say that v i is of type B and for each neighbour

u = v of v i , if c(N [u] \ {v}) \ c(N [v i ] \ {v})
is not empty, we add one colour of this set to L i . Note that u can be some other vertex v j or some vertex u i,j , but there are at most ∆ -

1 such vertices. If c(N [v i ]) \ c(N [v]
) is not empty, we add one colour of this set to L i . In the end,

|L i | ≤ ∆ + 1. Let L = ∪ i=1,...,d L i . Because ∆ ≥ 3, |L| ≤ 2d(∆ -1)
. We define a new colouring c ′ of G by just giving to v any colour not in L. We will prove that c ′ is locally identifying. First, c ′ is a proper colouring because L contains all the colours c(v 1 ),...,c(v d ). Let now x, y be a pair of adjacent vertices, with

N [x] = N [y]. We will show that c ′ (N [x]) = c ′ (N [y]). If neither x nor y are in N [v]
then the colours in their respective neighbourhoods did not change and we have

c ′ (N [x]) = c ′ (N [y]
). So we can assume, without loss of generality, that x = v 1 .

Suppose first that y = v. Let us also assume that there exists a colour

c 0 ∈ c(N [v 1 ]) \ c(N [v]), then c 0 = c(v). If v 1 is of type A, then c 0 ∈ L and c 0 ∈ c ′ (N [v 1 ]) \ c ′ (N [v]). Hence c 0 is still separating v from v 1 . If v 1 is of type B, then at least one colour of c(N [v 1 ]) \ c(N [v]) is in L (not necessarily c 0 ), and is separating v 1 from v. Now, assume that c(N [v 1 ]) \ c(N [v]) is empty. Because c(N [v 1 ]) = c(N [v]), there is a colour c 0 ∈ c(N [v]) \ c(N [v 1 ]). We have c 0 = c(v), so c 0 ∈ L and c 0 is still separating v from v 1 .
Assume now that y = v j , with j = 1 and v 1 ,v j adjacent. Then without loss of generality we can assume that there exists a colour c 0 in c(N [v 1 ]) that does not appear in c(N [v j ]). Necessarily,

c 0 = c(v) and so c 0 ∈ c(N [v 1 ] \ {v}) \ c(N [v j ] \ {v}). If v 1 is of type A, then c 0 is not the new colour c ′ (v) of v because c 0 ∈ L. Otherwise, v 1 is of type B. If c(N [v j ] \ {v}) \ c(N [v 1 ] \ {v}) is nonempty, then there is one colour in L of c(N [v j ] \ {v}) \ c(N [v 1 ] \ {v}) that is separating v j from v 1 . Otherwise, if v j is of type A, we are done using a similar argument. If v j is of type B, then one colour of c(N [v 1 ] \ {v}) \ c(N [v j ] \ {v}) is in L and is separating the two vertices.
Finally, we can assume without loss of generality that y

= u 1,1 . If c(N [u 1,1 ]) = c(N [v 1 ] \ {v}), then v 1 is of type A and so c(N [u 1,1 ]) ⊆ L. Hence, the new colour of v, c ′ (v), is not in c(N [u 1,1 ]) and is separating v 1 from u 1,1 . If there is a colour in c(N [v 1 ] \ {v}) \ c(N [u 1,1 ]), then it is still separating v 1 from u 1,1 . Otherwise c(N [u 1,1 ]) \ c(N [v 1 ] \ {v}
) is necessarily nonempty, and so there is a colour of L that is separating u 1,1 from v 1 .

Let d be an integer. A graph G is d-degenerate if each subgraph of G has a vertex of degree at most d (see [START_REF] Lick | k-degenerate graphs[END_REF] for reference).

Proposition 2. Let G be a d-degenerate connected graph with maximum degree ∆ ≥ 3 and d < ∆. Then:

χ lid (G) ≤ 2(∆ -1) 2 + d.
Proof. Let ∆ be fixed. We prove the claim by induction on the number of vertices in G. In the conditions of lemma, 2(∆ -1) 2 + d ≥ 9 so the claim is true for graphs with less than nine vertices. Assume that the claim is true for every d-degenerate graph with fewer than n vertices and maximum degree at most ∆. Let G be a d-degenerate graph with n vertices and maximum degree at most ∆. Let v be one vertex of minimum possible degree

t ≤ d in G. Let H = G \ {v}.
The graph H is also d-degenerate and by the induction hypothesis, there is a locally identifying colouring c of H with 2(∆ -1) 2 + d colours. As in the previous lemma, we denote the t neighbours of v by v 1 ,...,v t , (if v has no neighbours the claim is trivial) and for each i ∈ {1, ..., t}, we denote by u i,1 ,...,u i,si the neighbours of v i that are not neighbours of v (see Figure 1). We construct a list L ′ of size at most d containing, for each i ∈ {1, .., t}, the colour c(u i,1 ) if u i,1 exists. Each vertex v i has degree at most ∆ -1 in H. Using Lemma 1, we can choose for each vertex v i a colour that is not in L ′ : indeed, there are 2(∆ -1) 2 forbidden colours from the lemma applied to v i and d colours in L ′ , but the colours c(u i,1 ), if u i,1 exists, is counted twice, so there are at most 2(∆ -1) 2 + d -1 forbidden colours and at least one colour is free.

We can now assume that c is a locally identifying colouring of H such that no vertex v i has a colour in L ′ . We now assign to v a new colour, c(v), never used in c originally. We will prove that this colouring of G is locally identifying. It is clearly a proper colouring, and the only pair of adjacent vertices that is not clearly separated is the pair {v, v i }. If v i has a neighbour u i,1 , then c(u i,1 ) ∈ L ′ and c(N [v]) is not containing c(u i,1 ), so they are separated. Otherwise, we have

N [v i ] ⊆ N [v]. But v has minimum degree, so necessarily N [v i ] = N [v]
and the two vertices do not need to be separated.

Finally, we obtain a lid-colouring of G using 2(∆ -1) 2 + d + 1 colours. Let α be the new colour of v. Recall that α is used only once. We want to apply the recolouring lemma to v and avoid the colour α. So 2(∆ -1) 2 + d -2d(∆ -1) has to be greater than 0 (the number of colours used in the colouring minus the number of forbidden colours of the recolouring lemma applied to v minus the colour α). This is a decreasing function linear in d whose minimum is ∆ -1 (when d = ∆ -1) which is striclty greater than 0, as ∆ ≥ 3. This leads to a lid-colouring of the whole graph G using at most 2(∆ -1) 2 + d colours.

Corollary 3. Let G be a graph with maximum degree ∆ ≥ 3. Then:

χ lid (G) ≤ 2∆ 2 -3∆ + 3.
Proof. If G is not connected, we colour the components independently. So we can assume that G is connected.

If G is not ∆-regular, then G is (∆ -1)-degenerate. Indeed, if we take any proper subset V ′ of vertices, and consider the subgraph induced by V ′ , then if every vertex in this induced subgraph had degree ∆, there would be no edges between V ′ and V (G) \ V ′ , and therefore G would not be connected. So in this case we can directly apply Proposition 2 and the result is clear.

Assume now that G is ∆-regular. Let v be any vertex of G. As before, the graph G \ {v} is (∆ -1)-degenerate and so, by Proposition 2, it has a lid-colouring with 2∆ 2 -3∆ + 1 colours. As in the proof of Proposition 2, we can recolour all the neighbours of v in such a way that the colouring remains locally identifying and such that if a neighbour of v has not the same closed neighbourhood as v, it has a neighbour with a colour different from all the colours of N (v). More precisely, to recolour a neighbour of u, Lemma 1 forbidds 2(∆ -1) 2 = 2∆ 2 -4∆ + 2 colours and we forbidd also the colours of N (v) \ {v, u}, i.e. at most ∆ -1 more colours. So in total, there are 2∆ 2 -3∆ + 1 forbidden colours. To apply Lemma 1, we have to start with a lid-colouring using 2∆ 2 -3∆ + 2 colours which corresponds to the lid-colouring given by Proposition 2 plus an unused color. We finally get a lid-colouring of G \ {v} with 2∆ 2 -3∆ + 2 colours and the required properties on the neighbours of v. Then we assign a completely new colour to v and as in the proof of Proposition 2, we can show that the colouring is locally identifying, leading to a locally identifying colouring of the whole graph G with 2∆ 2 -3∆ + 3 colours .

We now study the case ∆ = 2: Proposition 4. Let n ≥ 4 be an integer. Let C n be the cycle of order n. Then:

• χ lid (C n ) = 3 if n ≡ 0 mod 4, • χ lid (C n ) = 5 if n = 5 or 7, • χ lid (C n ) = 4 otherwise.
As a consequence, any graph with maximum degree 2 has a locally identifying colouring with five colours.

Proof. Let v 0 ,..., v n-1 be the vertices of C n . We clearly have χ lid (C n ) ≥ 3.

We colour C n with four colours using the following family of sequences described by the following word:

[124341232][42](1232) *

for n ≥ 4 and n = 5, 7. A sequence in bracket, [M ], means that we can take or not take the sequence M , the sequence (M ) * means that we can repeat sequence M as many times as we need (or not use it at all). One can check that if we colour vertices of C n with one of the sequences described by the previous word, we obtain a locally identifying colouring with three colours if n ≡ 0 mod 4 and with four colours otherwise.

If n ≡ 0 mod 4, then there is no locally identifying colouring with three colours. Indeed, if we try to colour the vertices of C n with three colours there is no choice to do it and we must colour, without loss of generality: c(v i ) with colour 1 if i ≡ 0 mod 4, with colour 2 if i ≡ 1, 3 mod 4 and with colour 3 if i ≡ 2 mod 4. But v n-1 must have colour 2, and v n-2 must have colour 3. Then n -2 ≡ 2 mod 4 and so n ≡ 0 mod 4, a contradiction.

A case analysis shows that χ lid (C 5 ) = χ lid (C 7 ) = 5.

For the last part of the proposition, if G has maximum degree 2 then it is composed of connected components that are cycles or paths. One can easily check that a path has always a locally identifying colouring with four colours, and so we can colour each connected component of G independently with at most five colours.

One can notice that in the locally identifying colourings of the cycle provided in the proof, only three colours are used an unbounded number of times, whereas the other colours are used at most three times. In some sense, we can say that C n has almost a locally identifying colouring with three colours.

Strong locally identifying colourings

In this section, we consider a variation of locally identifying colourings by adding a strong constraint to the definition. Our technique can still be applied in this context in order to get a bound in the same asymptotic order. We also extend our method to the class of chordal graphs, in relation with a conjecture of [START_REF] Esperet | Locally identifying colourings of graph[END_REF].

We say that a colouring c is a strong locally identifying colouring (slid-colouring for short) if it is a locally identifying colouring and if for each vertex u, all the colours in N [u] are different (the colouring is locally injective). In other words, a slid-colouring is a proper distance-two vertexcolouring (two vertices at distance at most 2 from each other have different colours) without bad edges.

We denote by χ slid (G) the minimum number of colours required in any slid-colouring of G. Clearly, χ lid (G) ≤ χ slid (G) and χ 2 (G) ≤ χ slid (G), where χ 2 (G) denotes the minimum number of colours in a distance-two vertex-colouring of G. In a graph G with maximum degree ∆, each vertex has at most ∆ 2 vertices at distance at most 2, and so χ 2 (G) ≤ ∆ 2 + 1.

We will adapt the proof of the previous section to show that merging the locally-identifying constraint with the distance-two colouring constraint does not increase the asymptotic order of both bounds.

Lemma 5 (Recolouring lemma 2). Let v be a vertex of degree d 1 of a graph G. Assume that v has d 2 vertices at distance exactly 2 and let c be a slid-colouring c with strictly more than d 1 + 2d 2 colours. Then, there is a list L of colours of size at most d 1 + 2d 2 such that if we colour v with a colour not in L, the colouring remains a slid-colouring.

Proof. In this case we also need to put in L all the colours of vertices at distance 2 of v. We keep the same notations as before and we construct L as follows:

1. For each vertex v i , add colour c(v i ) to L (at most d 1 colours are added). 2. For each vertex u i,j , add colour c(u i,j ) to L (at most d 2 colours are added). 3. For each vertex u i,j , if there is some colour in c(N [u i,j ]), but not already in L, then add one of them to L. At this step we add at most d 2 colours.

In the end, L contains at most d 1 + 2d 2 colours. If we consider a new colouring c ′ from c where we colour v with a colour not in L, then clearly c ′ is still a distance-two colouring. Furthermore, no edge becomes bad. Indeed, the only edges that could become bad would be of the form v i u i,j . There are two cases depending on whether c(N

[u i,j ]) is included in c(N [v i ]) or not. If c(N [u i,j ]) ⊂ c(N [v i ]), then there is a colour c 0 ∈ c(N [v i ]) \ c(N [u i,j ]). If c 0 was the colour c(v), because c ′ (v) / ∈ c(N [u i,j ]) ⊂ c(N [v i ]), we have c ′ (v) ∈ c ′ (N [v i ]) \ c ′ (N [u i,j ]). Otherwise, we still have c 0 ∈ c ′ (N [v i ]) \ c ′ (N [u i,j ]). Otherwise c(N [u i,j ]) \ c(N [v i ]
) is not empty and during the construction of L, one colour of c(N [u i,j ]) \ c(N [v i ]) has been added to L, still separating v i from u i,j .

Note that Recolouring lemma 2 can also be applied in the locally identifying colouring case, leading in some cases to a better bound than the one of Recolouring lemma 1.

As before, we can use this lemma to construct a slid-colouring of a graph G by induction. We first colour G when it is d-degenerate: Proposition 6. Let G be a d-degenerate graph with maximum degree ∆ ≥ 2 and d < ∆. Then:

χ slid (G) ≤ (∆ -1)(2∆ -1) + 2d -1.
Proof. The idea of the proof is similar to the proof of Proposition 2. We construct the colouring by induction. We choose a vertex v with minimum possible degree t ≤ d. Then G \ {v} has a slid-colouring with (∆ -1)(2∆ -1) + 2d -1 colours. For each neighbour v i of v which has a neighbour u i,1 at distance 2 of v, we put the colour of u i,1 in a list L ′ . We recolour each neighbour v i of v in such a way that all the neighbours of v have different colours and none of them has a colour in L ′ . To recolour v i , there are at most (∆ -1)(2∆ -1) forbidden colours from the lemma, at most d -1 colours from the other neighbours of v and at most d -1 forbidden colours from L ′ (if v i has a neighbour u 1,1 then the colour of u 1,1 is already forbidden for v i in the lemma). Therefore, at most (∆ -1)(2∆ -1) + 2d -2 are forbidden but we have (∆ -1)(2∆ -1) + 2d -1 colours, so at least one colour is free. After that, we colour v with a completely new colour, obtaining a slid-colouring with (∆ -1)(2∆ -1) + 2d colours, and by Lemma 5, we can change the colour of v to a colour already used. We thus obtain a slid-colouring with (∆ -1)(2∆ -1) + 2d -1 colours (for this last step, at least two colours are free so one of them is not the colour of v and we can change the colour of v to a colour already used).

Corollary 7. Let G be a graph with maximum degree ∆. Then:

χ slid (G) ≤ 2∆ 2 -∆ + 1.
Proof. As before, we can assume that G is connected. If G has a vertex of degree d < ∆, then it is (∆ -1)-degenerate and we have χ slid (G) ≤ 2∆ 2 -∆ -2. Otherwise, G is ∆-regular. If we remove one vertex v, then G \ {v} is (∆ -1)-degenerate and there is a slid-colouring with 2∆ 2 -∆ -2 colours. We recolour the neighbours of v as before, but here there are ∆ neighbours so we will need (∆ -1)(2∆ -1) + 2∆ -2 + 1 = 2∆ 2 -∆ colours. We complete the colouring by giving a completely new colour to v, thus obtaining a slid-colouring with 2∆ 2 -∆ + 1 colours.

We then consider the case of the cycle: Proposition 8. Let n ≥ 4 be an integer. Let C n be the cycle of order n. Then:

• χ slid (C n ) = 4 if n ≡ 0 mod 4, • χ slid (C n ) = 6 if n = 6 or 11, • χ slid (C 7 ) = 7, • χ slid (C n ) = 5 otherwise.
As a consequence, any graph with maximum degree 2 has a slid-colouring with seven colours.

Proof. A colouring of C n is a slid-colouring if and only if every four consecutive vertices have different colours. Then it is clear that χ slid (C n ) = 4 if and only if n ≡ 0 mod 4, χ slid (C 6 ) = 6 and χ slid (C 7 ) = 7.

If n ≡ i mod 4 (i = 0), then χ slid (C n ) = 5 using the colouring described by the word (12345) i (1234) * , if n ≥ 5i (M i means that we repeat the pattern M i times). It remains to consider the case n = 11. There is no slid-colouring of C 11 with five colours, otherwise one colour would appear three times, and so two occurrences of it will be at distance less than 4. Moreover, 12345123456 is a slid-colouring of C 11 .

Clearly, a path has a slid-colouring with four colours and so any graph with maximum degree 2 has a slid-colouring with seven colours.

Finally, we consider the class of chordal graphs. Chordal graphs are graphs where each induced cycle has size at most three. They belong to the class of perfect graphs. One of their properties (see [START_REF] Brandstädt | Graph Classes: A Survey[END_REF]) is to admit a simplicial order of elimination for vertices: if G is a chordal graph, there is a vertex v whose neighbourhood is a clique (a simplicial vertex), and then G \ {v} is still a chordal graph. For chordal graphs, we have ω(G) = χ(G) where ω(G) is the clique number of G, i.e. the maximum size of a clique of G (see [START_REF] Brandstädt | Graph Classes: A Survey[END_REF]). In [START_REF] Esperet | Locally identifying colourings of graph[END_REF], it is conjectured that χ lid (G) ≤ 2ω(G), for any chordal graph G. We give the first nontrivial bound on χ slid , and so on χ lid , in terms of parameters ∆ and ω for chordal graphs, in the direction of the previous conjecture. ≤ 2ω 2 -7ω + 6. Hence it is enough to prove that χ slid (G) ≤ M (ω, ∆) + 1. We prove by induction on the number of vertices that any chordal graph with clique number at most ω and maximum degree at most ∆ has a slid-colouring with M (ω, ∆) + 1 colours. It is clearly true for small graphs. Let G be a chordal graph with clique number at most ω and maximum degree at most ∆. Let v be a simplicial vertex of G. By induction, let c be a slid-colouring of G \ {v} with M (ω, ∆) + 1 colours. Necessarily, all the vertices of N (v) have different colours, and all the vertices at distance 2 of v have colours different from colours of N (v) because they are at distance at most 2 of any vertex of N (v). Let c ′ be the colouring of G extending c and giving to v a completely new colour. Then c ′ is a slid-colouring of G with M (ω, ∆) + 2 colours. Let d ≤ ω -1 be the degree of v. Then v has at most d(∆ -d) vertices at distance 2. Observe now that d + 2d(∆ -d) = d(2∆ -2d + 1) ≤ M (ω, ∆) (by definition of M (ω, ∆)). By Lemma 5, we can recolour the vertex v with a colour already used and thus obtain a slid-colouring with M (ω, ∆) + 1 colours.

Figure 1 :

 1 Figure 1: Neighbourhood of a vertex v

Proposition 9 . 1 ≤

 91 Let G be a chordal graph and let ω = ω(G). If ω ≤ ∆ 2 + 1, then:χ slid (G) ≤ 2∆ω -2ω 2 + 5ω -2∆ -2. 2ω 2 -7ω + 7. Proof. Let ω = ω(G) and ∆ be fixed. Let M (ω, ∆) = max 1≤d≤ω-1 {d(2∆ -2d + 1)}. The function d → 2(2∆ -2d + 1) is maximized for d = ∆ 2 . Using this fact, M (ω, ∆) is equal to 2∆ω -2ω 2 + 5ω -2∆ -3 if ω -1 ≤ ∆ 2 and to ∆(∆+1) 2 otherwise. If ω -1 > ∆ 2, we clearly have∆(∆+1) 2

This research is supported by the ANR Project IDEA • ANR-08-EMER-007, 2009-2011. Email address: aline.parreau@ujf-grenoble.fr (Aline Parreau)