Arnaud Pêcher

Xuding Zhu

Claw-free circular-perfect graphs

Keywords:

The circular chromatic number of a graph is a well-studied refinement of the chromatic number. Circular-perfect graphs is a superclass of perfect graphs defined by means of this more general coloring concept. This paper studies claw-free circular-perfect graphs. A consequence of the strong perfect graph theorem is that minimal circular-imperfect graphs G have min{α(G), ω(G)} = 2. In contrast to this result, it is shown in [9] that minimal circular-imperfect graphs G can have arbitrarily large independence number and arbitrarily large clique number. We prove that claw-free minimal circular-imperfect graphs G have min{α(G), ω(G)} ≤ 3.

Let G = (V, E) be a graph with vertex set V and edge set E, then a k-coloring of G is a mapping f : V → {1, . . . , k} with f (u) = f (v) if uv ∈ E, i.e., adjacent vertices receive different colors. The minimum k for which G admits a k-coloring is called the chromatic number χ(G). The clique number ω(G) (resp. independence number α(G)) of G is the order of a largest clique (resp. independent set) of G, i.e., the maximum number of pairwise adjacent (resp. non-adjacent) vertices of G.

The circular chromatic number and circular clique number of graphs are refinements of the chromatic number and the clique number. Suppose G = (V, E) is a graph with at least one edge, and

k ≥ 2d are positive integers. A (k, d)-circular coloring of G is a mapping f : V → {0, . . . , k -1} with d ≤ |f (u)-f (v)| ≤ k -d if uv ∈ E. The circular chromatic number χ c (G) is the minimum k d taken over all (k, d)-circular colorings of G. Since every (k, 1)-circular coloring is a usual k- coloring of G, we have χ c (G) ≤ χ(G).
On the other hand, it is known [START_REF] Vince | Star chromatic number[END_REF] and easy to see that for any graph G, χ c (G) > χ(G) -1, and hence

χ(G) = ⌈χ c (G)⌉. So χ c (G) is a refinement of χ(G).
Let K k/d with k ≥ 2d denote the graph with the k vertices 0, . . . , k -1 and edges ij such that d ≤ |i -j| ≤ kd. The graphs K k/d are called circular cliques. Circular cliques include all cliques K t = K t/1 , all odd antiholes C 2t+1 = K (2t+1)/2 , and all odd holes C 2t+1 = K (2t+1)/t . The circular clique number is defined as

ω c (G) = max{ k d : K k/d ⊆ G, gcd(k, d) = 1}.
It follows from the definition that ω(G) ≤ ω c (G). It is also known [START_REF] Zhu | Circular perfect graphs[END_REF] that for any graph G, ω c (G) < ω(G) + 1, and hence ω(G) = ⌊ω c (G)⌋. Therefore ω c (G) is a refinement of ω(G).

Obviously ω(G) is a lower bound for χ(G).

A graph G is perfect if each in- duced subgraph G ′ ⊆ G has ω(G ′ ) = χ(G ′ ). Similarly, ω c (G) is a lower bound for χ c (G). A graph G is called circular-perfect [17] if each induced subgraph G ′ ⊆ G has χ c (G ′ ) = ω c (G ′ ).
Perfect graphs have been studied extensively since the concept and two conjectures (the weak and the strong perfect graph conjectures) were proposed by Berge [START_REF] Berge | Farbung von graphen deren sietliche bzw. deren ungerade kreise starr sind[END_REF] in 1961. The weak perfect graph conjecture was settled by Lovász [START_REF] Lovász | A characterization of perfect graphs[END_REF] in 1972. Recently, the strong perfect graph conjecture has been settled by Chudnovsky, Robertson, Seymour and Thomas in [START_REF] Chudnovsky | The strong perfect graph theorem[END_REF], which gives a characterization of perfect graphs by means of forbidden induced subgraphs: a graph G is perfect if and only if G contains neither chordless odd cycles C 2k+1 with k ≥ 2, nor their complements C 2k+1 .

It follows from the definitions that for any graph

G, ω(G) ≤ ω c (G) ≤ χ c (G) ≤ χ(G).
Therefore every perfect graph is circular-perfect. However, odd cycles and their complements are circular-perfect graphs but not perfect graphs. So the class of circular-perfect graphs is a proper superclass of the class of perfect graphs. Is there a simple characterization of circular-perfect graphs by means of forbidden induced subgraphs? It is shown in [START_REF] Xu | On minimally circular-imperfect graphs[END_REF] that the line graph L(G) of a cubic graph G is circular-perfect if and only if G is 3-edge colourable. Thus such a characterization of circular-perfect graphs implies a characterization of critically non-3-edge colourable cubic graphs, which is known to be a difficult problem. So it is unlikely that there is a simple forbidden induced subgraph characterization of circular-perfect graphs. Some sufficient conditions for a graph to be circular-perfect were obtained in [START_REF] Zhu | Perfect graphs for generalized colouring-circular perfect graphs[END_REF][START_REF] Zhu | Circular perfect graphs[END_REF]. Classes of (minimal) circular-imperfect graphs were constructed in [START_REF] Pan | Minimal circular-imperfect graphs of large clique number and large independence number[END_REF][START_REF] Pêcher | Three classes of minimal circular imperfect graphs[END_REF][START_REF] Pêcher | On the circular chromatic number of circular partitionable graphs[END_REF][START_REF] Xu | Some results on circular perfect graphs and perfect graphs[END_REF]. Minimal circular-imperfect line graphs were studied in [START_REF] Xu | On minimally circular-imperfect graphs[END_REF]. In this paper, we study claw-free circular-perfect graphs.

A graph G is claw-free if K 1,3 is not an induced subgraph of G. Claw-free graphs is a superclass of line graphs and has been studied extensively in the litterature. Recently, Chudnovsky and Seymour [START_REF] Chudnovsky | The structure of claw-free graphs[END_REF][START_REF] Chudnovsky | Claw-free graphs vi. the structure of quasi-line graphs[END_REF] presented a structural characterization of claw-free graphs. A graph G for which the neighbourhood of each vertex can be covered by two cliques is called a quasi-line graph. We use their characterization, restricted to quasi-line graphs, to prove a structural property of minimal circular-imperfect graphs. One consequence of the strong perfect graph theorem is that minimal imperfect graphs G have min{ω(G), α(G)} = 2. It was asked in [START_REF] Pêcher | Three classes of minimal circular imperfect graphs[END_REF] whether min{ω(G), α(G)} is bounded for minimal circular-imperfect graphs G. This question was answered in the negative in [START_REF] Pan | Minimal circular-imperfect graphs of large clique number and large independence number[END_REF], where it is proved that for any positive integer k, there is a minimal circular-imperfect graph G with min{ω(G), α(G)} ≥ k.

We show that if restricted to claw-free graphs, the question above has a positive answer: if G is a claw-free minimal circular-imperfect graph, then min{ω(G), α(G)} ≤ 3.

Before the strong perfect graph conjecture becomes a theorem, the conjecture was confirmed for claw-free graphs in [START_REF] Giles | The strong perfect graph theorem for a class of partitionable graphs[END_REF][10]. Our result above implies an alternative proof of this result, of course without making use of the strong perfect graph theorem [START_REF] Chudnovsky | The strong perfect graph theorem[END_REF].

Sketch of the proof

Suppose G is a claw-free graph with independence number at least 3. It was proved by Fouquet [6] that for any vertex x of G, the neighborhood N G (x) of x either contains an induced C 5 , or can be covered with two cliques. If G is circular-perfect, then N G (x) does not contain an induced C 5 , for otherwise G contains the odd wheel W 5 , which is circular-imperfect. Thus we have the following observation: if G is a claw-free circular-perfect graph with independence number at least 3, then G is a quasi-line graph.

It turns out that claw-free circular-perfect graphs with an induced odd antihole of size at least 7 have a basic structure: Theorem 1. If G is a connected claw-free circular-perfect graph with an induced odd antihole H of size at least 7 then G \ H is a clique. Furthermore α(G) = 2.

Since every minimal circular-imperfect graph is 2-connected, we have the following corollary: Corollary 1. If G is a claw-free minimal circular-imperfect graph and contains an induced odd antihole H of size at least 7, then α(G) ≤ 3.

It remains to study claw-free circular perfect graphs G that do not contain an odd antihole of order at least 7. Due to Theorem 1, G has independence number at least 3, and is therefore, as mentioned above, quasi-line. We establish that if G has clique number at least 4 then G has an independent set I that intersects each maximum clique.

We prove a stronger statement: Theorem 2. If G is a quasi-line graph, ω(G) = k ≥ 4 and for every vertex x, Gx has a k-colouring, then either G is the complement of a circular clique or G has a stable set which intersects every maximum clique of G.

As a consequence, a claw-free graph G with ω(G) = k ≥ 4 and α(G) ≥ 4 can not be minimal circular-imperfect. Because otherwise, G is not the complement of a circular-clique [START_REF] Coulonges | On strongly circular-perfectness[END_REF], is quasi-line since it does not contain the odd wheel W 5 (which is already minimal circular-imperfect). Hence there is an independent set I intersecting each maximum clique. Since G -I is circular-perfect, we have

  ω c (G -I) = χ c (G -I). Due to Corollary 1, G, and thus G -I, does not containK (2p+1)/2 for p ≥ 3. It follows that ω c (G -I) = ω(G -I) = k -1 and hence χ(G -I) = χ c (G -I) = k -1. But then χ(G) = ω(G) = k,and hence G is circular-perfect.

Email:Arnaud.Pecher@labri.fr

Email:zhu@math.nsysu.edu.tw

Supported by the french-taiwanese partnership CNRS/NSC number 1872

Supported in part by the National Science Council of ROC under grant NSC96-2115-M-110-001


Causeret François1

Cezera Stéphane2

Rousselle Jean-Marc3

Stéphane Cezera
email: stephane.cezera@inrae.fr

The steps of an experiment in experimental economics

Keywords: Experimental economics, experience, methodology

François Causeret is a computer science engineer in the ASTRO Unit in Guadeloupe. He is responsible for socio-economic data and their processing. The research projects in which he participates have the final objective of designing innovative cropping systems with low input levels. Systemic and analytical analyzes are implemented. Multi-scale (from the plot to the territory), multidisciplinary research is based on agroecological and economic approaches.

Jean-Marc Rousselle is a research engineer at the CEE-M

Definition

The use of experiments has long been presented as impracticable by schools of thought presenting economics as a discipline where, like other social sciences, the validation of economic theories was based on uncontrolled observations, essentially though investigation.

However, building on the previous practices of psychometricians, experimental economics gradually came into being from the second half of the twentieth century as a scientific discipline. Experimental economics makes it possible to test economic theories by confronting them with the reality observed according to specific configurations integrating the behavior of economic agents, their social practices, and the institutional rules to which they are subject. It can also be used to test hypotheses for which there are no underlying theories.

Experimental economics was largely inspired by experimental methods developed in psychology.

Is there an experimental approach specific to economics? Experimental economics is a scientific approach making it possible to reconstitute decision contexts by working in a controlled environment (most often, in the laboratory, but sometimes also in a natural environment) in order to artificially reproduce a situation reflecting economic theory or yet to get closer to economic reality.

We speak of an experimental protocol because an experiment requires following a rigorous process articulating research objectives prioritized according to precise rules of experimentation. These codified steps also extend to the selection of subjects who are recruited under some conditions set in advance by the experimenter.

Principle of an experimental session in economics

The principle is to invite subjects (students, consumers, producers, etc.) to act within the framework of a game defined by the experimenter. The rules of the game take the structure of the reconstructed real economic situation.

Each subjects has the role of aneconomic agent (e.g, a buyer, a seller, etc) whose characteristics are defined by the experimenter by preferences, technologies, monetary and information endowments. Each subject's decision in the game gives them a gain (or loss) expressed in monetary form. The basic principle is that each subject should bear the financial consequences of the choices he/she made during the experiment. As the subjects are nevertheless individuals a priori all different, the 1 UR1321 ASTRO, Domaine Duclos, 97170 Petit Bourg 2 Université Toulouse 1 Capitole -Manufacture des Tabacs 21 allée de Brienne 31000 TOULOUSE INRAE, UR 1415 Toulouse School of Economics, F-31000 Toulouse, France ; stephane.cezera@inrae.fr 3 UMR 1135 CEE-M, Campus Supagro Montpellier, 2 place Viala, 34060 Montpellier cedex 2 relevance of the economic experiment rests on the theory of induced value [START_REF] Smith | Experimental Economics: Induced Value Theory[END_REF], which makes it possible to ensure control of the parameters tested.

Five principles must be observed in the design of an economic experiment:

Insatiability: A subject always prefers to have more compensation than he/she already has, which means that each subject's utility is a monotonously increasing function of their earnings.

Prominence (or Saliency): a subject's gains are a function, which he/she knows perfectly well, of his/her possible actions and the possible actions of the other subjects. Prominence distinguishes experimental economics from traditional investigations and simulation insofar, as it provides an incentive for subjects to act in the laboratory as they would act in the real world. The incentive amounts to saying that the subject must bear all the financial consequences of their choices. Dominance: Monetary gains from experimentation explain subjects' actions better than any other factor, which means that any influence other than earnings on the subject is negligible for his/her in-game decision making.

Secret: the subject is the only one to know his/her own endowments and winnings during the game, even if he/she may need to know the aggregated results during the game. This guarantees his/her autonomy of choice.

Parallelism: this is the measurement of the difference between reality and the laboratory, in other words, the external validity of data produced in the laboratory. This condition leaves the possibility of inferring from the laboratory to the real, in other words, it makes it possible to claim that the behavioral regularities observed in the laboratory must persist in a real situation as long as the underlying conditions remain unchanged. It is arguably on this point that experimental economics meets the strongest skepticism. The argument is that large-scale economic behavior can never be reproduced on a small scale by students. One answer [START_REF] Plott | Industrial Organization Theory and Experimental Economics[END_REF] is to retort that a robust theory is made to work in all cases, even in the lab, as long as the ceteris paribus clause (all other things being equal) is followed. If it fails in the lab, then the theory needs to be revised.

Why carry out an experiment?

An experiment meets three main objectives:

-compare the data collected with theoretical predictions, -help decision-making by evaluating the impact of different factors or parameters (for example public policies public (taxes, new industrial strategies, etc), without the need to expose the population concerned to incur the costs of an effective implementation, -produce new knowledge, when the theory is incomplete or non-existent.

An experiment

Scientific aspect -Preparation of the protocol

The experimental approach is particularly suitable for testing certain economic hypotheses.

In practice, the research team is involved in an experimental economics project and submits the protocol it has developed to a working group responsible for discussing and validating the experimental protocols upstream of the experiments. Once the protocol has been validated, the team relies on the framework thus defined to write the instructions that will frame the actions of all the subjects who will participate in the experiment. It is the statement of these "rules of the game" which guarantees the "controlled" framework.

Course of the experiment: Development and / or use of specific tools

The development of experiences is based on:

-classic programming languages (Python C languages, Php, Java, VB languages).

-tools dedicated to experiments such as Z-tree or Otree. These tools are used to manage the part experience, database and payment.

-internal tools developed in the laboratories of the EcoSocio department such as "LE2M" in Montpellier or even "Gael experience" in Grenoble. The place Most of the time, experimental economics sessions take place in the laboratory, but it can happen that they are held outside these structures.

Outside of a laboratory:

This scenario corresponds to experiences in the field. These sessions are implemented, depending on the conditions, either from paper supports or with laptops as well.

In laboratory :

A room is generally specifically dedicated to experimental economics sessions. It iis organized around several computer stations, partitioned or not, so that each subject has an individual computer. The ideal is to use a room with twenty-four machines because this allows experiments to be carried out in groups of two, three, four, six or eight subjects (example of a room in the appendix). The subjects are usually installed in individual boxes (with instructions to follow), but in some situations (notably in field experiments), we will favor the use of a mobile laboratory, more flexible.

Another possibility is to use pencil and paper, but this technique is more complicated to manage for the retrieval, storage and chain of data processing.

Finally, still little used, new techniques are emerging, such as: i)

"eye tracking" which makes it possible to study the reactions of gaze movements which are unconscious and precisely reflect the cognitive processes engaged in a real context of use. ii) sensory sensors that record heartbeats, physical reactions during decision making to know the chronology (timing) of decision making.

Recruitment

It is carried out according to the specificity of the experience.

Initially, the experimentalists mainly recruit students through emails, advertisements in the Training and Research Units of universities or via social networks.

Recruitment can also be refined according to the profile of the subjects, their habits (consumption for example), their level of study, etc.

If you want to involve subjects that are not students, it is possible to call on specialized companies or place announcements on online sites (vivastreet).

Note: Leboncoin does not accept to post recruitment advertisements for experiments.

You can also use flyers, newspaper advertising, media advertising, local radio or television announcements, telephone recruitment ... Over the course of the experimental sessions, the experimentalists can build up a directory of participants allowing them to operate from a pool of subjects available according to the specificities of the experiments.

To collect the online registrations of subjects, the experimentalists use tools specially configured for the management of the experiments and the distribution of the candidates between the different sessions on the basis of criteria defined in advance by the experimenter. ORSEE (www.orsee.org) is the best known of these and the most frequently used. It has the advantage of being easy to configure to generate a website backed by a database that allows simultaneous management of the experience calendars and the recruitment database. It allows to keep the history of player participation. The articulation of these different aspects is based on the principle of "client / server" via php, SQL and MySQL.

It is important to specify that students who register in the database must first adhere to the ethical rules of laboratories.

The organized sessions -In the experimental economy room:

Each experiment is described in an experimental protocol which details its progress and the organization of the different sessions. For each of them, subjects receive an individual invitation. The subjects are welcomed in 3 stages: on their arrival, the subjects are received in a friendly space in order to put them at ease, then, they are invited to join the experimental room to participate in the experiment, finally, they are received individually by a member of the team of experimenters to receive their earnings at the end of the session.

Note: when developing the experience, a first session (called a "pilot session") is generally organized internally. It makes it possible to test and validate the experience at both organizational and technical levels. It is in particular an opportunity to test the computer program and the understanding of the interfaces, but also to discuss/possibly re-specify the scientific objective with the researchers. Depending on the case, the pilot sessions can take place with recruited subjects or simply with members of the research project.

-In the Conviviality Room:

First, the subjects are received in a convivial room, in order to offer them a snack to place them in the best conditions, time to make the call and discuss with them, in particular about the experimental economics room and its organization.

Some experimenters allow the subjects to visit the room to prove that all the machines are identical and that all the subjects will be placed under the same conditions. Then the subjects are invited to draw a random number. This number corresponds to the box number in which each participant will settle and therefore to the machine to which he will be assigned. This moment is important because it makes it possible to confirm again to the subjects that the experimental design is anonymous and the result of chance.

-In the Experimental Economics Room:

Each subject takes place in the box which has been allocated to him/her by drawing lots. In addition to the post he can uses heet of paper, pencil and a calculator.

Once inside the room, the subjects no longer have the right to communicate with each other or with the outside (phone, tablets off). They are therefore in a controlled environment.

At the start of each session the experimenter reads the instructions to clearly explain the course of the experiment. It is important that the experimenter read the instructions aloud to prove that all are participating in the same experiment, and are at the same level of understanding and information.

When the experiment is complicated, it is important to schedule a small, real-time startup test, with a focused question to ensure that the subjects understand the instructions.

For some experiments, one can go so far as to plan a "blank" trial so that the subjects become familiar with the screen and the interface. This is a separate test from the rest of the experiment to make sure the subjects understand the process and are familiar with the graphical environment of the experiment.

At the end of these different stages, the experience can begin.

Once the process of the experiment is complete, subjects are (almost systematically) asked to complete a questionnaire (often referred to as the "final questionnaire") which exclusively includes socio-demographic questions. The data collected then make it possible to characterize the sample and, if necessary, to qualify the interpretation of the results of the experiment by using control variables for possible selection bias.

-Outside the laboratory:

When the context of the study does not lend itself to the organization of a session in an experimental room, it is possible to do experiments outdoors by reconstituting an experimental economy room with a mobile laboratory or with surveys questionnaires.

Compensation

During an experiment in experimental economics, all subjects are compensated which is not necessarily the case in psychology:

-on the one hand, all receive fixed compensation, or not, linked to their participation as equivalent to their travel expenses.

-on the other hand, they are compensated according to the gains accumulated during the experience.

Global compensation is paid at the end of each session, but the conditions of compensation are set and defined upon registration. Students sign a receipt for participation.

The budgets allocated to the experiments come from research projects and are managed either by authorities in the universities after the establishment of agreements, or by groups of economic (GIE) or scientific (GIS) interests, created in support of the centers of research.

The fixed compensation may vary from one laboratory to another (in the order of € 2 to € 10).

Then participation evolves; the subjects are compensated on the basis of approximately € 10/hour spent for the experiment, an hourly rate charged in France. But depending on the difficulty of the experiment, the gains may be re-evaluated or devalued, or even zero if the subject has not really made the expected choices. For example in some experiments, some subjects are likely to make risky choices and lose their gain.

Whatever decisions the subjects make during an experiment, they cannot under any circumstances spend their own money (including the fixed indemnity definitively acquired).

In some laboratories, subjects are compensated in vouchers.

Note: Very often the experimenters practice overbooking during reservations in order to have as many subjects as possible. If too many people show up, those not selected by lot receive only the fixed compensation.

Subjects

The participants in the experiments are called subjects. They have no obligation to participate in an experiment and are voluntary. They sign a participation charter.

As already said, in economics any participation in an experiment is compensated unlike in other disciplines. The topics are divided into different categories:

-"Mr. Everyone": when the experience does not require any constraint or skill in the choice of subjects, which is rather rare.

-Students: they represent the majority of subjects solicited during experiments for reasons of geographical proximity to the laboratories, availability during the day, and marked interest in the experiments.

Note: Student recruitments must be modulated according to their studies and their level because this can introduce bias into the results (especially for economics students).

Taking part in an experiment does not influence the scores of students on exams.

-Groups: it is possible to target a group of people according to specific criteria (purchase of organic food for example).

-On the internet: through the Amazon Mechanical Turk site, it is possible to offer experiences to subjects connected at random anywhere in the world or targeted. This makes it possible to have a pool of subjects at a very low cost and available. On the other hand, the experimenter cannot control how the subjects respond. Its use still implies compliance with US law.

The results

During the experiments, the data is stored in a database and saved for analysis after each session.

Often initially, the experimenters consult the data obtained for a first evaluation: are the data reliable and usable?

Then, using scientific software, the data is formatted, checked, then processed and analyzed using the appropriate statistical and econometric tools (eg: Matlab, Mathematica, Statistica, Stata, R, Gauss etc).

Then, depending on the quality of the data observed and the results obtained, either the hypotheses made in the experimental protocol are not verified and possibly new experiments can be organized according to modified hypotheses or a different protocol, or the hypotheses that are tested are verified and validated by experimentation. It may happen that no results are obtained.

The results obtained at the end of the experiments and the analysis of the data thus collected will, in fine, be used in the form of an article in order to disseminate the conclusions to which the study has led to the entire scientific community.

1

  UR1321 ASTRO, Domaine Duclos, 97170 Petit Bourg 2 Université Toulouse 1 Capitole -Manufacture des Tabacs 21 allée de Brienne 31000 TOULOUSE INRAE, UR 1415 Toulouse School of Economics, F-31000 Toulouse, France ; stephane.cezera@inrae.fr 3 UMR 1135 CEE-M, Campus Supagro Montpellier, 2 place Viala, 34060 Montpellier cedex 2

1

  UR1321 ASTRO, Domaine Duclos, 97170 Petit Bourg 2 Université Toulouse 1 Capitole -Manufacture des Tabacs 21 allée de Brienne 31000 TOULOUSE INRAE, UR 1415 Toulouse School of Economics, F-31000 Toulouse, France ; stephane.cezera@inrae.fr 3 UMR 1135 CEE-M, Campus Supagro Montpellier, 2 place Viala, 34060 Montpellier cedex 2

1

  UR1321 ASTRO, Domaine Duclos, 97170 Petit Bourg 2 Université Toulouse 1 Capitole -Manufacture des Tabacs 21 allée de Brienne 31000 TOULOUSE INRAE, UR 1415 Toulouse School of Economics, F-31000 Toulouse, France ; stephane.cezera@inrae.fr 3 UMR 1135 CEE-M, Campus Supagro Montpellier, 2 place Viala, 34060 Montpellier cedex 2

UR1321 ASTRO, Domaine Duclos, 97170 Petit Bourg

Université Toulouse 1 Capitole -Manufacture des Tabacs 21 allée de Brienne

TOULOUSE INRAE, UR 1415 Toulouse School of Economics, F-31000 Toulouse, France ; stephane.cezera@inrae.fr 3 UMR 1135 CEE-M, Campus Supagro Montpellier, 2 place Viala, 34060 Montpellier cedex 2

UR1321 ASTRO, Domaine Duclos, 97170 Petit Bourg

2 Université Toulouse 1 Capitole -Manufacture des Tabacs 21 allée de Brienne 31000 TOULOUSE INRAE, UR 1415 Toulouse School of Economics, F-31000 Toulouse, France ; stephane.cezera@inrae.fr 3 UMR 1135 CEE-M, Campus Supagro Montpellier, 2 place Viala, 34060 Montpellier cedex 2

Laboratories


Guillaume Fertin
email: fertin@irin.univ-nantes.fr

André Raspaud
email: raspaud@labri.u-bordeaux.fr

Bruce Reed
email: reed@ecp6.jussieu.fr

Star Coloring of Graphs

Keywords: graphs, vertex coloring, proper coloring, star coloring

A star coloring of an undirected graph G is a proper vertex coloring of G (i.e., no two neighbors are assigned the same color) such that any path of length 3 in G is not bicolored. The star chromatic number of an undirected graph G, denoted by χs(G), is the smallest integer k for which G admits a star coloring with k colors. In this paper, we give the exact value of the star chromatic number of different families of graphs such as trees, cycles, complete bipartite graphs, outerplanar graphs and 2-dimensional grids. We also study and give bounds for the star chromatic number of other families of graphs, such as planar graphs, hypercubes, d-dimensional grids (d ≥ 3), d-dimensional tori (d ≥ 2), graphs with bounded treewidth and cubic graphs. We end this study by two asymptotic results, where we prove that, when d tends to infinity, (i) there exist graphs G of maximum degree d such that χs(G) = Ω( d 3 2 (log d) 1 2 ) and (ii) for any graph G of maximum degree d, χs(G) = O(d 3 2 ).

Introduction

All graphs considered here are undirected. In the following definitions (and in the whole paper), the term coloring will be used to define vertex coloring of graphs. A proper coloring of a graph G is a labeling of the vertices of G such that no two neighbors in G are assigned the same label. Usually, the labeling (or coloring) of vertex x is denoted by c(x). In the following, all the colorings that we will define and use are proper colorings.

Definition 1 (Star coloring) A star coloring of a graph G is a proper coloring of G such that no path of length 3 in G is bicolored.

We also introduce here the notion of acyclic coloring, that will be useful for our purpose.

Definition 2 (Acyclic coloring) An acyclic coloring of a graph G is a proper coloring of G such that no cycle in G is bicolored.

We define by star chromatic number (resp. acyclic chromatic number) of a graph G the minimum number of colors which are necessary to star color G (resp. acyclically color G). It is denoted χ s (G) for star coloring, and a(G) for acyclic coloring.

By extension, the star (resp. acyclic) chromatic number of a family F of graphs is the minimum number of colors that are necessary to star (resp. acyclically) color any graph belonging to F . It is denoted χ s (F ) for star coloring and a(F ) for acyclic coloring. The purpose of this paper is to determine and give properties on χ s (F ) for a large number of families of graphs. In Section 2, we present general properties for the star chromatic number of graphs. In the following sections (Sections 3 to 7), we determine precisely χ s (F ) for trees, cycles, complete bipartite graphs, outerplanar graphs and 2-dimensional grids and we give bounds on χ s (F ) for other families of graphs, such as planar graphs, hypercubes, d-dimensional grids, ddimensional tori, graphs with bounded treewidth and cubic graphs. We end this paper by giving asymptotic bounds for the star chromatic number of graphs of order n and maximum degree d.

Generalities

We note that for any graph G, any star coloring of G is also an acyclic coloring of G: indeed, a cycle in G can be bicolored if and only if it is of even length, that is of length greater than or equal to 4. However, by definition of a star coloring, no path of length 3 in G can be bicolored. Hence, we get the following observation.

Observation 1 For any graph G, a(G) ≤ χ s (G).

Proposition 2 [START_REF] Fertin | Acyclic and k-distance coloring of the grid[END_REF] For any graph G of order n and size m, χ s (G)

≥ 2n+1- √ γ 2
, where γ = 4n(n -1) -8m + 1.

Sketch of proof : Let us compute a lower bound for a(G), the acyclic chromatic number of a graph G, with n vertices and m edges. Suppose we have acyclically colored G with k colors 1, 2 . . . k. Take any two of those colors, say i and j, and let V i (resp. V j ) be the set of vertices of G that are assigned color i (resp. color j). G[V i ∪ V j ], the graph induced by V i ∪ V j , is by definition acyclic, i.e. it is a forest. Let e ij be the number of edges of G[V i ∪ V j ] ; thus e ij ≤ |V i | + |V j | -1 (I ij ). If we sum inequality (I ij ) for all distinct pairs i, j with 1 ≤ i = j ≤ k, we get that 1≤i =j≤k e ij ≤ n(k -1) -k(k-1)

2

. Since 1≤i =j≤k e ij = m, it now suffices to solve the inequality k 2 -(2n + 1)k + 2(m + n) ≤ 0. This gives

2n+1- √ γ 2 ≤ k ≤ 2n+1+ √ γ

2

, where γ = 4n(n-1)-8m+ 1. However, the rightmost inequality does not give us any useful information, since for any graph with at least one edge we always have γ ≥ 1 and thus k ≤ n + 1. Finally, we obtain that a(G)

≥ k ≥ 2n+1- √ γ 2
. By Observation 1, we conclude that χ s (G) also satisfies this inequality.

2

Actually, we can note that the star coloring is an acyclic coloring such that if we take two color classes then the induced subgraph is a forest composed only of stars. Star coloring was introduced in 1973 by Grünbaum [START_REF] Grünbaum | Acyclic colorings of planar graphs[END_REF]. He linked star coloring to acyclic coloring by showing that any planar graph has an acyclic chromatic number less than or equal to 9, and by suggesting that this implies that any planar graph has a star chromatic number less than or equal to 9 • 2 8 = 2304.

However, this property can be generalized for any given graph G, as mentioned in [START_REF] Borodin | Acyclic colourings of planar graphs with large girth[END_REF][START_REF] Borodin | Acyclic k-strong coloring of maps on surfaces[END_REF].

Theorem 3 (Relation acyclic/star coloring) [BKW99, BKRS00] For any graph G, if the acyclic chromatic number of G satisfies a(G) ≤ k, then the star chromatic number of G satis- fies χ s (G) ≤ k • 2 k-1 .
As a corollary of this result, we can determine an upper bound for χ s (P), where P denotes the family of planar graphs. Indeed, Borodin [START_REF] Borodin | On acyclic colorings of planar graphs[END_REF] showed that any planar graph has an acyclic coloring using at most 5 colors (we also note that there exists a graph of order 6 such that a(G) = 5). Thus we deduce that χ s (P) ≤ 80. However, a result from [START_REF] Nešetřil | Colorings and homomorphisms of minor closed classes[END_REF], applied to family P, yields χ s (P) ≤ 30, and this result has later been improved in [ACK + 02], where it is shown that χ s (P) ≤ 20. Concerning lower bounds, there exists a planar graph G 1 for which any star coloring needs 6 colors (this graph is shown in Figure 1): indeed, we can first note that we need at least 4 colors to assign to vertices v 1 , v 2 , v 3 and v 4 , since the subgraph induced by those 4 vertices is isomorphic to K 4 . Let us then use colors 1,2,3 and 4 to color respectively v 1 , v 2 , v 3 and v 4 . However, four colors are not enough to star color G 1 , because if we are only allowed 4 colors then c(v 5 ) = 3, and in that case no color can be given to v 6 . Thus χ s (G 1 ) ≥ 5. Now suppose we are allowed 5 colors. If c(v 5 ) = 3, then c(v 6 ) = 5 and c(v 7 ) = 5 ; but in that case, it is impossible to assign a color to v 9 . Thus c(v 5 ) = 5. In that case, if c(v 6 ) = 2, then c(v 7 ) = 5 and v 8 cannot be assigned a color. Finally, if c(v 6 ) = 5, then either c(v 7 ) = 1 or c(v 7 ) = 5. In the first case, it is impossible to color v 8 , while in the second this implies c(v 8 ) = 3, and thus v 9 cannot be colored. Thus, 5 colors do not suffice to star color G 1 and consequently χ s (G 1 ) ≥ 6 (we note that, on this example, it is possible to find a star coloring of G 1 with exactly 6 colors). The girth g of a graph G is the length of its shortest cycle. In [START_REF] Borodin | Acyclic colourings of planar graphs with large girth[END_REF], it is proved that if G is planar with girth g ≥ 5 (resp. g ≥ 7), then a(G) ≤ 4 (resp. a(G) ≤ 3). Together with Theorem 3, we deduce:

Corollary 4 If G is a planar graph with girth g ≥ 5, then χ s (G) ≤ 32. If G is a planar graph with girth g ≥ 7, then χ s (G) ≤ 12.

However, a result from [START_REF] Nešetřil | Colorings and homomorphisms of minor closed classes[END_REF] implies that χ s (G) ≤ 14 for any planar graph G of girth g ≥ 5. When the girth g satisfies g ≥ 7, then Theorem 1 in [START_REF] Nešetřil | Colorings and homomorphisms of minor closed classes[END_REF] implies that χ s (G) ≤ 14, which does not improve the bound of Corollary 4.

Several graphs are cartesian product of graphs (Hypercubes, Grids, Tori), so it is interesting to have an upper bound for the star chromatic number of cartesian product of graphs. We recall that the cartesian product of two graphs G = (V, E) and G ′ = (V ′ , E ′ ), denoted by G G ′ , is the graph such that the set of vertices is V × V ′ and two vertices (x, x ′ ) and (y, y ′ ) are linked by an edge if and only if x = y and x ′ y ′ is an edge of G ′ or x ′ = y ′ and xy is an edge of G.

Theorem 5 For any two graphs G and

H, χ s (G H) ≤ χ s (G) • χ s (H)
Proof : Suppose that χ s (G) = g and χ s (H) = h, and let C G (resp. C H ) be a star coloring of G (resp. H) using g (resp. h) colors. In that case, we assign to any vertex (u, v) of G H color [C g (u), C h (v)]. This coloring uses gh colors, and this defines a star coloring. Indeed, suppose that there exists a path P of length 3 that is bicolored in G H, with V (P ) = {x, y, z, t} and E(P ) = {xy, yz, zt}. Depending on the composition of the ordered pairs corresponding to the vertices of the path, we have 8 possible paths. We will only consider 4 of them, because by permuting the first and second component of each ordered pair, we obtain the others. The 4 possible paths are:

(1) x = (u, v), y = (u, v 1 ), z = (u, v 2 ), t = (u, v 3 ) (2) x = (u, v), y = (u, v 1 ), z = (u, v 2 ), t = (u 4 , v 2 ) (3) x = (u, v), y = (u, v 1 ), z = (u 2 , v 1 ), t = (u 2 , v 4 ) (4) x = (u, v), y = (u, v 1 ), z = (u 2 , v 1 ), t = (u 5 , v 1 )
Clearly, in the first case P cannot be bicolored, since the path v, v 1 , v 2 , v 3 is not bicolored in H. For the second case: y and t have different colors (v 1 v 2 is an edge of H). For the third case: x and z have different colors (vv 1 is an edge of H). The same argument works for the last case. 2 Observation 6 For any graph G and for any 1 ≤ α ≤ |V (G)|, let G 1 , . . ., G p be the p connected components obtained by removing α vertices from G. In that case, χ s (G) ≤ max i {χ s (G i )} + α.

Proof : Star color each G i , and reconnect them by adding the α vertices previously deleted, using a new color for each of the α vertices. Any path of length 3 within a G i will be star colored by construction, and if this path begins in G i and ends in G j with i = j, then it contains at least one of the α vertices, which has a unique color. Thus the path of length 3 cannot be bicolored, and we get a star coloring of G. 2

Remark 7 For any α ≥ 1, the above result is optimal for complete bipartite graphs K n,m . Wlog, suppose n ≤ m and let α = n. Remove the α = n vertices of partition V n . We then get m isolated vertices, which can be independently colored with a single color. Then, give a unique color to the α = n vertices. We then get a star coloring with n + 1 colors ; this coloring can be shown to be optimal by Proposition 12.

We recall that the independence number of a graph G, α(G), is the cardinality of a largest independent set in G.

Observation 8 For any graph G, χ s (G) ≤ 1 + |V (G)| -α(G), where α(G) is the independence number of G.
Proof : Let S be a maximum independent set of G. Color each vertex of S with color c, and give new pairwise distinct colors to all the other vertices. This coloring has the desired number of colors. It is clearly a proper coloring, and it is also a star coloring, because there is only one color which is used at least twice.

2

Remark 9 The above result is optimal for complete p-partite graphs K s1,s2,...,sp .

3 Trees, Cycles, Complete Bipartite Graphs, Hypercubes

Proposition 10 Let F r be the family of forests such that r is the maximum radius over all the trees contained in F r . In that case, χ s (F r ) = min{3, r + 1}.

Proof : Let F be a forest contained in F r . When r = 0, the result is trivial (F holds no edge). When r = 1, F is composed of isolated vertices and of stars. Hence, we color each isolated vertex, as well as the center of each star in F with color 1, and all the remaining vertices with color 2. This is obviously a proper coloring, and since in that case there is no path of length 3, it is consequently a star coloring as well. Now we assume r ≥ 2. We then arbitrarily root each tree composing F , and we color each vertex v, of depth d v in F , as follows: c(v) = d v mod 3. Clearly, this is a proper coloring of F and it is easy to see that it is a star coloring. 2

Proposition 11 Let C n be the cycle with n ≥ 3 vertices.

χ s (C n ) = 4 when n = 5 3 otherwise
Proof : It can be easily checked that χ s (C 5 ) = 4. Now let us assume n = 5. Clearly, 3 colors at least are needed to star color C n . We now distinguish 3 cases: first, if n = 3k, we color alternatively the vertices around the cycle by colors 1,2 and 3. Thus, for any vertex u, its two neighbors are assigned distinct colors, and consequently this is a valid star coloring. Hence χ s (C 3k ) ≤ 3. Suppose now n = 3k +1. In that case, let us color 3k vertices of C n consecutively, by repeating the sequence of colors 1,2 and 3. There remains 1 uncolored vertex, to which we assign color 2. One can check easily that this is also a valid star coloring, and thus χ s (C 3k+1 ) ≤ 3. Finally, let n = 3k + 2. Since the case n = 5 is excluded here, we can assume k ≥ 2. Thus n = 3(k -1) + 5, with k -1 ≥ 1.

In that case, let us color 3(k -1) consecutive vertices along the cycle, alternating colors 1,2 and 3. For the 5 remaining vertices, we give the following coloring: 2, 1, 2, 3, 2. It can be checked that this is a valid star coloring, and thus χ s (C 3k+2 ) ≤ 3 for any k ≥ 2. Globally, we have χ s (C n ) = 3 for any n = 5, and the result is proved. 2

Proposition 12 Let K n,m be the complete bipartite graph with n + m vertices. Then χ s (K n,m ) = min{m, n} + 1.

Proof : Wlog, let n ≤ m. The upper bound of n + 1 immediately follows from Observation 6 (cf.

Remark 7 for a detailed proof). Now let us prove that χ s (K n,m ) ≥ n+ 1 : if each of the partite set contains at least two vertices with the same color, then there exists a bicolored 4-cycle, and the coloring we have is not a star coloring. If not, then the number of colors used is greater than or equal to n + 1. Hence the result.

2 Theorem 13 (Star-Coloring of hypercube of dimension d, H d ) For any d-dimensional hy- percube H d , ⌈ d+3 2 ⌉ ≤ χ s (H d ) ≤ d + 1. Proof : The lower bound is a direct application of Proposition 2, where n = 2 d and m = d • 2 d-1 . Indeed, we have χ s (H d ) ≥ 2n+1- √ γ 2
, where γ = 4n(n -1) -8m + 1. Let us prove now that χ s (H d ) > d+2 2 . For this, let us show that

f (n, d) = 2n+1- √ γ 2 -d+2 2 > 0. Note that f (n, d) = (2n-1-d)- √ γ 2 = (2n-1-d)- √ γ 2 • (2n-1-d)+ √ γ (2n-1-d)+ √ γ . That is, f (n, d) = (2n-1-d) 2 -γ 2((2n-1-d)+ √ γ) . However, D(n, d) = 2((2n -1 -d) + √ γ) is positive for any d ≥ 1, since √ γ ≥ 1 in all circumstances and n = 2 d . Hence, it suffices to show that f ′ (n, d) = (2n -1 -d) 2 -γ is positive in order to prove the lower bound. f ′ (n, d) = (2n-1-d) 2 -(4n 2 -4n-8m+1), thus f ′ (n, d) = d 2 -4nd+2d-8m. Since m = nd 2 , we conclude that f ′ (n, d) = d(d + 2) > 0 for any d ≥ 1. Hence we have χ s (H d ) > d+2 2 , that is χ s (H d ) ≥ ⌈ d+3
2 ⌉. In order to prove the upper bound, we give the following coloring: suppose the vertices of H d are labeled according to their binary representation ; that is, every vertex u ∈ V (H d ) can be labeled as follows:

u = b 1 b 2 . . . b d , with every b i ∈ {0, 1}, 1 ≤ i ≤ d.
We then assign a color c(u) to u according to the following equation: [START_REF] Fertin | Acyclic and k-distance coloring of the grid[END_REF] that this coloring C is acyclic. Moreover, in [START_REF] Fertin | Acyclic and k-distance coloring of the grid[END_REF] it has been shown that any bicolored path in H d can only appear in a copy of a 2-dimensional cube H 2 . Since C is acyclic, we conclude that no bicolored path of length strictly greater than 2 can appear, and thus C is a star coloring. 2

c(u) = d i=1 i • b i mod d + 1. We know by

d-dimensional Grids

In this section, we study the star chromatic number of grids. More precisely, we give the star chromatic number of 2 dimensional grids, and we extend this result in order to get bounds on the star chromatic number of grids of dimension d.

We recall that the 2-dimensional grid G(n, m) is the cartesian product of two paths of length n -1 and m -1. Wlog, we will always consider in the following that m ≥ n. A summary of the results is given in Table 1 ; those results are detailed below. Proof : By a rather tedious case by case analysis (confirmed by the computer), it is possible to show that 5 colors at least are needed to color G(4, 4). Hence, for any n and m such that min{n, m} ≥ 4, χ s (G(n, m)) ≥ 5. The upper bound is a corollary of Theorem 16 below. 2

m = 2 m = 3 m ≥ 4 n = 2 3 4 4 n = 3 xxx 4 4 n ≥ 4 xxx xxx 5 Table 1: Star coloring of 2-dimensional grids G(n, m) (n ≤ m) Proposition 14 χ s (G(2, 2)) = 3,
We know that d-dimensional grids G d are isomorphic to the cartesian product of d paths. Hence, by Theorem 5 and Proposition 10, we get an upper bound for χ s (G d ): χ s (G d ) ≤ 3 d for any d ≥ 1. However, it is possible to do much better, and to prove that the star chromatic number of the d-dimensional grid is linear in d: this is the purpose of the following theorem.

Theorem 16 (Star-Coloring of the d-dimensional grid G d ) Let G d be any d-dimensional grid, d ≥ 1. Then 2 + d - d i=1 1 ni ≤ χ s (G d ) ≤ 2d + 1.
Proof : The lower bound is a direct application of this inequality on the lower bound of Proposition 2, and is similar to a proof of [START_REF] Fertin | Acyclic and k-distance coloring of the grid[END_REF] , with γ = 4n(n -1) -8m + 1. This can also be written as follows:

χ s (G) ≥ (2n+1) 2 -γ 2(2n+1+ √ γ) , that is χ s (G) ≥ 4(m+n) 1+2n+ √ γ , or a(G) ≥ m+n n • 4n 1+2n+ √ γ . However, γ = (2n -1) 2 -8m, hence γ < (2n -1) 2 , that is 1 + 2n + √ γ < 4n. Thus we have χ s (G) > 1 + m n . Now, if
(G d )| = n 1 × • • • × n d and |E(G d )| = n 1 × • • • × n d × (d -d i=1 1 ni ).
We also note that this means that for "sufficiently large" grids (for instance, when each n i ≥ d), we have χ s (G d ) ≥ d + 1, and that the "worst" case appears when each n i = 2, 1 ≤ i ≤ d ; in that case G d is isomorphic to the hypercube of dimension d, H d , and the lower bound of Theorem 13 applies.

Concerning the upper bound, we use here a proof that is close to the one given in [START_REF] Fertin | Acyclic and k-distance coloring of the grid[END_REF] concerning acyclic coloring. Let us represent each vertex u of G d = G(n 1 , n 2 . . . n d ) by its coordinates in each dimension, that is u = (x 1 , x 2 , . . . x d ) where each x i , 1 ≤ i ≤ d satisfies 0 ≤ x i ≤ n i -1. Now, we define a vertex coloring for G d as follows: for each u ∈ V (G d ) such that u = (x 1 , x 2 , . . . x d ), we let c(u) = d i=1 i • x i mod 2d + 1. First, we prove that this coloring is proper. Indeed, suppose that 2 vertices u and u ′ , differing on the j-th coordinate, 1 ≤ j ≤ d, are assigned the same color c(u) = c(u ′ ). Hence we have u = (x 1 , x 2 , . . . x j , . . . x d ) and

u ′ = (x 1 , x 2 , . . . x j ± 1, . . . x d ). Then, since c(u) = c(u ′ ), we have j • x j + d i=1,i =j i • x i = j • (x j ± 1) + d i=1,i =j i • x i , that is ±j = 0 mod 2d + 1. Since 1 ≤ j ≤ d,
we conclude that this cannot happen. Now let us show that this coloring is a star coloring. More precisely, we show that it is a 2 distance coloring, that is, no two vertices at distance less than or equal to 2 are assigned the same color. Consequently, no path of length 3 can be bicolored, and thus it is also a star coloring. We have seen that no two neighbors are assigned the same color. Now let us prove that for any two vertices u and u ′′ lying at distance 2, we cannot have c(u) = c(u ′′ ). Indeed, u and u ′′ being at distance exactly 2 in G d , their coordinates differ (i) either in two dimensions j 1 and j 2 (ii) or in a single dimension j. Case (ii) can be solved easily: we are in the case where u = (x 1 , x 2 , . . . x j , . . . x d ) and u ′′ = (x 1 , x 2 , . . . x j ± 2, . . . x d ), and by the same computations as above, we end up with ±2j = 0 mod 2d + 1, a contradiction since 1 ≤ j ≤ d. If we are in Case (i), the same argument applies, and by a similar computation, we end up with ±j 1 ± j 2 = 0 mod 2d + 1, a contradiction too since 1 ≤ j 1 = j 2 ≤ d. Thus our coloring is a 2 distance coloring of G d , and consequently a star coloring of G d . We then conclude that χ s (G d ) ≤ 2d + 1.

2

Remark 17 We note that for dimensions 1 and 2, the upper bound given by Theorem 16 for d-dimensional grids is tight (cf. Proposition 10 when d = 1 and Theorem 15 when d = 2).

d-dimensional Tori

In this section, we give bounds on the star chromatic number of d-dimensional tori for any d ≥ 2.

In the following, for any

n i ≥ 3, 1 ≤ i ≤ d, we denote by T G d = T G(n 1 , n 2 , . . . n d ) the toroidal d-dimensional grid having n i vertices in dimension i. We recall that T G d is the cartesian product of d cycles of length n i , 1 ≤ i ≤ d. Theorem 18 (Star coloring of d-Dimensional Tori) d + 2 ≤ χ s (T G d ) ≤ 2d + 1 when 2d + 1 divides each n i 2d 2 + d + 1 otherwise Proof :
The lower bound is obtained by Proposition 2, using arguments that are very similar to the ones developed for hypercubes in proof of Theorem 13. Indeed, we know that

χ s (T G d ) ≥ 2|V |+1- √ γ 2 , where γ = 4|V |(|V | -1) -8|E| + 1. Let N = |V | ; we know that |E| = dN where N = d i=1 n i . Now, if we prove that 2|V |+1- √ γ 2 -(d + 1) > 0, this will imply that χ s (T G d ) > d + 1. Let f (N, d) = 2N +1- √ γ 2 -(d+1). Note that f (N, d) = (2N -1-2d)- √ γ 2 = (2N -1-2d)- √ γ 2 • (2N -1-2d)+ √ γ (2N -1-2d)+ √ γ . That is, f (N, d) = (2N -1-2d) 2 -γ 2((2N -1-2d)+ √ γ) . However, D(N, d) = 2((2N -1 -2d) + √ γ) is strictly
positive for any d ≥ 1, since we always have √ γ ≥ 1 and N ≥ 3 d (in order to get a torus, the number of vertices n i in each dimension i must be at least equal to 3). Hence, it suffices to show that f ′ (N, d) = (2N -1 -2d) 2γ is positive in order to prove the lower bound.

f ′ (N, d) = (2N -1 -2d) 2 -(4N 2 -4N -8N d + 1), thus f ′ (N, d) = 4d 2 + 4d. Hence, we conclude that f ′ (N, d) > 0 for any d ≥ 1. Hence we have χ s (T G d ) > d + 1, that is χ s (T G d ) ≥ d + 2.
The upper bound in the case where 2d + 1 divides each n i comes from the study of the nontoroidal grid G d , and the coloring given in Theorem 16. It is easy to see that this coloring remains a star coloring of T G d when 2d + 1 divides each n i , 1 ≤ i ≤ d, and thus we have χ s (T G d ) ≤ 2d + 1 in that case.

When 2d + 1 does not divide each n i , then consider the subgraph of T G d that consists of a (non-toroidal) d-dimensional grid G ′ d = G(n 1 -1, n 2 -1, . . . n d -1). We can star color G ′ d with 2d + 1 colors as shown in Theorem 16. Now, in order to avoid a bicolored path of length 3 due to the wrap-around in each dimension, it suffices to use new colors to color the "borders" of T G d (that is, the vertices of T G d that do not appear in G ′ d ). These vertices form a graph G 0 , where V (G 0 ) can be partitioned in is a (d -1)-dimensional non-toroidal grid. Hence, if for any 1 ≤ i ≤ d, we use new colors to star color G i (using the coloring described in proof of Theorem 16), then we get a star coloring of T G d ; indeed, by construction any bicolored path that could occur would be either (i) between vertices of G ′ d and vertices of G i for some 1 ≤ i ≤ d, or (ii) between vertices of G i and vertices of G j for some 1 ≤ i = j ≤ d. However, any vertex u of G ′ d has only one edge leading to a vertex of G i , for any given 1 ≤ i ≤ d. Hence u cannot be connected to two vertices of G i , and thus cannot be connected to two vertices being assigned the same color c. We then conclude that case (i) cannot occur. The same argument holds for case (ii): a given vertex u of G i has at most one connection leading to G j , 1 ≤ i = j ≤ d. Overall, the suggested coloring uses 2d + 1 colors (to color G ′ d ), to which we must add d times 2(d -1) + 1 colors (to color each G i ). Thus, globally, this coloring needs (2d + 1)

d classes V 1 , . . . V d , such that the subgraph G i induced by V i , 1 ≤ i ≤ d,
+ d • (2(d -1) + 1) colors, that is 2d 2 + d + 1 colors. 2
6 Graphs with Bounded Treewidth

The notion of treewidth was introduced by Robertson and Seymour [START_REF] Robertson | Graph minors. I. excluding a forest[END_REF]. A tree decomposition of a graph G = (V, E) is a pair ({X i |i ∈ I}, T = (I, F )) where {X i |i ∈ I} is a family of subsets of V , one for each node of T , and T a tree such that:

(1) i∈I X i = V

(2) For all edges vw ∈ E, there exists an i ∈ I with v ∈ X i and w ∈ X i (3) For all i, j, k ∈ I: if j is on the path from i to k in T , then

X i ∩ X k ⊆ X j
The width of a tree decomposition ({X i |i ∈ I}, T = (I, F )) is max i∈I |X i | -1. The treewidth of a graph G is the minimum width over all possible tree decomposition of G.

We will prove the following theorem.

Theorem 19 If a graph G is of treewidth at most k, then χ s (G) ≤ k(k + 3)/2 + 1
Actually we will prove Theorem 19 for k-trees, because it is well known that the treewidth of a graph G is at most k (k > 0) if and only if G is a partial k-tree [START_REF] Bodlander | A partial k-arboretum of graphs with bounded treewidth[END_REF].

We recall the definition of a k-tree [BLS99]: (1) a clique with k-vertices is a k-tree (2) If T = (V, E) is a k-tree and C is a clique of T with k vertices and x / ∈ V , then

T ′ = (V ∪ {x}, E ∪ {cx : c ∈ C}) is a k-tree.
If a k-tree has exactly k vertices, then it is a clique by definition. If not, it contains at least a (k + 1)-clique ; moreover, it is easy to see that the greedy coloring with k + 1 colors of a k-tree gives an acyclic coloring. Hence we can deduce by Theorem 3 that for any k-tree T k with at least k + 1 vertices, k + 1 ≤ χ s (T k ) ≤ k • 2 k-1 . However, a much better upper bound can be derived. This is the purpose of Theorem 20 below.

Theorem 20 For any k ≥ 1 and any k-tree T k :

• χ s (T k ) = k if |V (T k )| = k ; • k + 1 ≤ χ s (T k ) ≤ k(k + 3)/2 + 1 otherwise.
Proof : Consider a k-tree G. We recall that a k-tree G is an intersection graph [START_REF] Mckee | Topics in intersection graph theory[END_REF] and can be represented by a tree T and a subtree S v for each v in G s.t.:

(

1) uv ∈ E(G) ⇐⇒ S u ∩ S v = ∅ (2) for any t ∈ T , |{v : t ∈ S v }| = k + 1
We can see that by considering the tree decomposition of the k-tree. The tree T is the one of the tree decomposition and the subtree S v for v ∈ V (G) is exactly the subtree of T containing the nodes of T corresponding to the subsets of the tree decomposition containing v.

We root T at some node r and, for each vertex v of G, let t(v) be the first node of S v obtained when traversing T in preorder (i.e. t(v) is the "highest" node of S v ). We choose some fixed preorder and order the nodes as v 1 , v 2 , . . . , v n so that for any i < j, t(v i ) is considered in the preorder before t(v j ). We color the nodes in this order, using k(k + 3)/2 + 1 colors.

For each i we let:

X vi = Sv j ∋t(vi) {v l = v i : S v l ∋ t(v j )} We now show that |X vi | ≤ k(k + 3)/2. Indeed let A = {a 1 , a 2 , • • • , a k , v i }
be the subset of vertices corresponding to t(v i ). We assume that t(a i ) is before t(a i+1 ) (i ∈ {1, . . . , k -1}) in the preorder. We first give an upper bound for the number of subtrees

S v l which contain t(a i ) (v l / ∈ A). The number of S v l (v l / ∈ A) for i ∈ {1, • • • , k} which contain t(a 1 ) is at most k, because the corresponding subset can intersect A only in a 1 . The number of S v l (v l /
∈ A) which contain t(a 2 ) is at most k -1, a 1 is in the subset corresponding to t(a 2 ) and we do not count S a1 . It is easy to see that the number of S v l (v l / ∈ A) which contain t(a i ) is at most k + 1i, because the subset corresponding to t(a i ) contains {a 1 , a 2 , • • • , a i }. In total we have at most

i=k i=1 i = k(k + 1)/2 subtrees S v l with v l / ∈ A containing t(a i ) i ∈ {1, • • • , k}
. Now we have to add the number of S ai , this gives |X vi | ≤ k(k + 3)/2, without counting v i . We color v i with any color not yet used on X vi . This clearly yields a proper coloring, indeed if xy is an edge of G then S x ∩ S y = ∅ and either t(x) ∈ S y or t(y) ∈ S x , hence by construction x and y have different colors. We claim it also yields a coloring with no bichromatic P 4 (a path of length 3): assume the contrary, and let {x, y, z, w} be this P 4 labeled so that (1) t(x) is the first of t(x), t(y), t(z), t(w) considered in the preorder,

(2) x and y have the same color,

(3) xz and yz are in E(G).

We have to notice that x, z, y are not in the same clique K k+1 of the graph G corresponding to a node of T , because by construction this would imply that the colors are different. Now S x ∩ S y = ∅, S z ∩ S x = ∅, S z ∩ S y = ∅, so by (1) t(y) is in S z . Further since zx ∈ E(G), by (1) we have t(z) is in S x . So x ∈ X y , contradicting the fact that x and y get the same color.

2 We can notice that for 1-trees (i.e. the usual trees), the upper bound we obtain matches the one given by Proposition 10. For 2-trees, the upper bound is optimal because of graph of Figure 3, which has been shown by computer to have a star chromatic number equal to 6.

We also note for completeness that while this paper was submitted, it has been shown independently in [ACK + 02] that for any graph G of treewidth k, χ s (G) ≤ k(k + 1)/2, and that there exist graphs of treewidth k for which this bound is reached.

In the following, we will denote by O the family of outerplanar graphs. Proof : It is well-known that any outerplanar graph is a partial 2-tree: thus, by Theorem 20, χ s (O) ≤ 6. Moreover the graph in Figure 3, which is also outerplanar, has a star chromatic number equal to 6. Thus, we conclude that χ s (O) ≥ 6, which proves the corollary. 2

Cubic Graphs

Observation 22 Let G be a graph of order n and G 2 be the square graph of G. In that case, χ s (G) ≤ χ(G 2 ), where χ(G) denotes the (proper) chromatic number of G.

Proof : For any graph G = (V, E), take its square graph

G 2 = (V, E ∪ E)
, where E is the set of edges joining any vertices at distance 2 in G. Any proper coloring C of G 2 is a star coloring of G: indeed G 2 contains all the edges of G, thus C is also proper in G. Now take any path of length 2 in G, say (u, v, w). In G 2 , u, v and w are assigned 3 distinct colors by C. Hence, no path of length 2 in G can be bicolored ; consequently, no path of length 3 is bicolored either, and C is a star coloring of G. 2

It is a well known result that any graph of maximum degree d can be properly colored with at most d + 1 colors (cf. for instance [START_REF] Vizing | On an estimate of the chromatic class of a p-graph[END_REF]). Since G 2 is of maximum degree d 2 when G is of maximum degree d, we deduce the following corollary.

Corollary 23 Let G be a graph of order n and of maximum degree d. Then χ s (G) ≤ d 2 + 1. Now we turn to the case where d = 3, that is cubic graphs. By Corollary 23 above, we deduce that for any cubic graph G, χ s (G) ≤ 10. We also note that the result given in [START_REF] Nešetřil | Colorings and homomorphisms of minor closed classes[END_REF] yields the same upper bound. However, it is possible to slightly improve this bound to 9, by using the more general proposition below (which is itself an improvement of Corollary 23).

Proposition 24 For any graph of G maximum degree d ≥ 2, χ s (G) ≤ d 2 .

Proof : Take G 2 , the square graph of G. Since G is of maximum degree d, G 2 is of maximum degree at most d 2 . If G 2 is not isomorphic to the complete graph K d 2 +1 , then, by Brooks' theorem, we have directly χ(G 2 ) ≤ d 2 . Hence, by Observation 22, we have

χ s (G) ≤ d 2 . Now, if G 2 is isomorphic to K d 2 +1
, then the independence number of G, α(G), satisfies α(G) ≥ 2 (since 2 ≤ d < d 2 ). Then, by applying Observation 8, and since

|V (G)| = d 2 + 1, we obtain χ s (G) ≤ 1 + (d 2 + 1) -2, that is χ s (G) d 2 .
2

Proposition 25 Let C denote the family of cubic graphs. We have 6 ≤ χ s (C) ≤ 9.

Proof : The upper bound is a direct consequence of Proposition 24, applied to the case d = 3. The lower bound is given by the cubic graph G s given in Figure 4 (note that this graph turns out to be a snark, that is a nontrivial cubic graph whose edges cannot be properly colored by three colors). We now show that its star chromatic number is equal to 6. Indeed, suppose that χ s (G s ) ≤ 5. Then, take 5 vertices in G s that induce a C 5 . There are now two options: either 4 or 5 colors are used to color those 5 vertices (we know by Proposition 11 that at least 4 colors are needed to color this C 5 ). Let us detail each of those two cases: • Case 1: only 4 colors are used. In that case, one of these colors (wlog, say color 1) must be used twice in this C 5 , and thus be assigned on two non-neighboring vertices x and y (hence, x and y are at distance 2) ; the three other colors are used exactly once for each of the three remaining vertices in C 5 . Wlog, let those vertices be colored as shown in Figure 4. In that case, u can be assigned either color 4 or 5. If c(u) = 4, then c(v) = 5 and no color can be given to w. If c(u) = 5, then v can be assigned either color 3 or 4. But in both cases, no color can be assigned to w. Hence this case cannot happen.

• Case 2: Since Case 1 cannot appear, this means that any C 5 in G s must be colored with 5 different colors. By a somewhat tedious but easy case by case analysis, it can be seen that it is not possible to star color G s in 5 colors satisfying this property.

We conclude that χ s (G s ) ≥ 6, and equality holds by respectively assigning to the vertices of the outer cycle the colors 1,2,3,4,5,3,1 and 6. 2

Asymptotic Results

In this section, we give asymptotic results that apply to graphs of order n and maximum degree d. They rely heavily on Lovász's local Lemma, and are shown thanks to proofs that are similar to the ones given by Alon et al. [START_REF] Alon | Acyclic coloring of graphs[END_REF] about acyclic coloring.

We first recall Lovász's local Lemma below ( [START_REF] Erdös | Infinite and finite sets[END_REF], see also [START_REF] Spencer | Ten Lectures on the Probabilistic Method[END_REF]).

Lemma 26 (Lovász's local Lemma [START_REF] Erdös | Infinite and finite sets[END_REF]) Let A 1 , A 2 , . . . A n be events in an arbitrary probability space. Let the graph H = (V, E) on the nodes {1, 2 . . . n} be a dependency graph for the events A i (that is, two events A i and A j will share an edge in H iff they are dependent). If there exist real numbers 0 ≤ y i < 1 such that for all i we have

P r(A i ) ≤ y i • {i,j}∈E (1 -y j ) then P r(∩ Āi ) ≥ n i=1 (1 -y i ) > 0
Theorem 27 Let G = (V, E) be a graph with maximum degree d. Then χ s (G) ≤ ⌈20d

Proof : Let x = ⌈20d 3 2 ⌉, and let us color V (G) with x colors, where for each vertex v of V (G), the color is independently chosen randomly according to a uniform distribution on {1, 2, . . . x}. Let C define this application. What we want to show here is that with non zero probability, C is a star coloring of G.

For this, we define a family of events on which we will apply Lovász's local Lemma. This will imply that with non zero probability, none of these events occur. If our events are chosen so that if none of them happens, then our coloring is a star coloring of G, the theorem will be proved. Let us now describe the two types of events we have chosen.

• Type I: For each pair of adjacent vertices u and v in G, let A u,v be the event that c(u) = c(v).

• Type II: For each path of length 3 uvwx in G, let B u,v,w,x be the event that c(u) = c(w) and c(v) = c(x).

By definition of star coloring, it is straightforward that if none of these two events occur, then C is a star coloring of G. Now, let us show that with strictly positive probability none of these two events occur. We will apply here the local Lemma : to this end, we construct a graph H whose nodes are all the events of the two types, and in which two nodes X S1 and Y S2 (X, Y ∈ {A, B}) are adjacent iff S 1 ∩ S 2 = ∅. Since the occurrence of each event X S1 depends only on the color of the vertices in S 1 , H is a dependency graph for these events, because even if the colors of all vertices of G but those in S 1 are known, the probability of X S1 remains unchanged. Now, a vertex of H will be said to be of type i ∈ {I, II} if it corresponds to an event of type i. We now want to estimate the degree of a vertex of type i in H. This is the purpose of the following observation. 2 Observation 28 For any vertex v in a graph G of maximum degree d, we have:

(1) v belongs to at most d edges of G ;

(2) v belongs to at most 2d 3 paths of length 3 in G.

Proof : (1) Is straightforward since the maximum degree in G is d.

(2) Suppose first that v is an end vertex of such a path. Then v belongs to at most d(d -1) 2 ≤ d 3 paths of length 3. Now suppose v is not an end vertex of such a path. Then one of its neighbors x must be an end vertex of this path. There are d ways to choose x, and the number of paths of length 3 with end vertex x going through v is at most (d -1) 2 . Thus there are d(d -1) 2 ≤ d 3 paths of length 3 for which v is an internal vertex. Globally, we have that v belongs to at most 2d 3 paths of length 3 in G.

2

Lemma 29 For i, j ∈ {I, II}, the (i, j) entry matrix M given below is an upper bound on the number of vertices of type j which are adjacent to a vertex of type i in the dependency graph H.

I II I

2d 4d 3 II 4d 8d 3 Proof : Take a vertex v I of type I in H, and let us give an upper bound on the number of vertices of type I in H that are neighbors of v I . v I corresponds to an event A u,v that implies two vertices u and v in G. Thus, by definition of the event graph H, v I is connected to all the vertices that correspond to events A u,y and A z,v for all vertices y that are neighbors of u in G and all the vertices z that are neighbors of v in G. Since by Observation 28(1), there are at most d vertices that are neighbor of u in G (resp. of v in G), the entry M (I, I) is upperly bounded by 2d. The entries M (I, II), M (II, I) and M (II, II) are computed in a similar way, using the results of Observation 28(1) and (2). 2

Now, let us come back to our coloring C. The following observation is straightforward.

Observation 30

(1) For each event A of type I, P r(A) = 1

x

(2) For each event B of type II, P r(B) = 1

x 2

Now, in order to apply Lovász's local Lemma, there remains to choose the y i , i ∈ {1, 2}, where 0 ≤ y i < 1. For this, we choose that y i = 2

x i , i ∈ {1, 2}. In order to be able to apply Lovász's local Lemma, it is necessary to prove that:

1 x ≤ 2 x (1 - 2 x ) 2d (1 - 2 x 2 ) 4d 3 and 1 x 2 ≤ 2 x 2 (1 - 2 x
) 4d (1 -2

x 2 ) 8d 3 Clearly, if the second inequality is satisfied, the first is satisfied too. In order to prove that it is satisfied, let S = (1 -2

x ) 4d (1 -2 x 2 ) 8d 3 . We have that S ≥ (1

-8d x )(1 -16d 3 x 2 ), that is S ≥ (1 -2 5 √ d )(1 -1 25
). It is easy to check that in that case 2S ≥ 1 for any d ≥ 1. Hence Lovász's local Lemma applies, which means that C is a star coloring of G with non zero probability. This proves Theorem 27.

We note that this result improves the one given by [START_REF] Nešetřil | Colorings and homomorphisms of minor closed classes[END_REF] or the easy Observation 22, that yields a star coloring with O(d 2 ) colors, while Theorem 27 yields a star coloring with O(d 3/2 ) colors.

Theorem 31 There exists a graph G of maximum degree d such that

χ s (G) ≥ ε d 3 2 (log d) 1 2
where ε is an absolute constant.

Proof : First, we note that we make no attempt to maximize the constant here. Let us show that, for a random graph G (with the "random" notion to be defined later) of order n, we have P r{χ s (G) > n 2 } → 1 as n → ∞. (P1) For this, we put

p = c log n n 1 3
where c is independent of n, to be chosen later. Now let V = {1, 2 . . . n} be a set of n labeled vertices ; for our purpose, we put n divisible by 4. Let G = (V, E) be a random graph on V , where for each pair (u, v) in V 2 we choose to put an edge with probability p. If d denotes the maximum degree of G, then it is a well-known fact that P r{d ≤ 2np} → 1 as n → ∞ [START_REF] Bollobás | Random Graphs[END_REF]. With our choice of p, this gives here:

P r{d ≤ 2cn 2 3 (log n) 1 3 } → 1 as n → ∞.

Figure 1 :

 1 Figure 1: A planar graph G 1 for which χ s (G 1 ) ≥ 6

Figure 2

 2 Figure 2: 4 star colorings of G(2, m) (left) and G(3, m) (right)

  concerning acyclic coloring in G d . Indeed, Proposition 2 yields that for any graph G = (V, E) with |V | = n and |E| = m, we have χ s (G) ≥ 2n+1-√ γ 2

  we replace respectively n and m by |V (G d )| and |E(G d )|, we end up with the result. Indeed, it is well known that |V

HFigure 3 :

 3 Figure 3: A 2-tree H that satisfies χ s (H) = 6

Figure 4 :

 4 Figure 4: A cubic graph G s such that χ s (G s ) = 6

  Now, in order to prove (P1), we show the following lemma.Lemma 32 For any fixed partition of V in k ≤ n 2 color classes, the probability that this partition is a star coloring of G is upperly bounded by (1p 3 )

⌉.

Proof of Lemma 32 Let V 1 , V 2 . . . V k be the parts of the partition of the set V of vertices of G. For any V i of odd cardinality, we omit one vertex. Thus we end up with at least nk ≥ n 2 vertices altogether, that lie in k even disjoint parts. We partition each of those even parts in sets of 2 vertices U 1 , U 2 . . . U r , where r ≥ n 4 ; in that case, the two vertices in each U i are colored with the same color. Now take any pair (U i , U j ): if 3 edges connect this pair, then there exists a path of length 3 in G that is bicolored, and our coloring is not a star coloring. However, it is easy to see that the probability for which this case happens is equal to 4p 3 -3p 4 , which is always greater than or equal to p 3 . Since there are at least n 4 2 pairs of the form (U i , U j ), the probability that our coloring is a star coloring does not exceed:

(

Since there are less than n n partitions of V , we see that the probability that there exists a star coloring of G with at most n 2 colors does not exceed

With the right choice of c, this probability is in o(1) as n → ∞. Indeed, it suffices here that c 3 > 32 (for instance, c = 4).

Thus, we end up with the following two statements: P r{d ≤ 2cn , where ε is an absolute constant. This proves the result. 2

Conclusion

In this paper, we have provided many new results concerning the star chromatic number of different families of graphs. In particular, we have provided exact results for trees, cycles, complete bipartite graphs, outerplanar graphs and 2-dimensional grids. We have also determined bounds for the chromatic number in several other families of graphs, such as planar graphs, hypercubes, d-dimensional grids (d ≥ 3), d-dimensional tori (d ≥ 2), graphs with bounded treewidth and cubic graphs. We have also determined several more general properties concerning the star chromatic number: notably, using the techniques of [START_REF] Alon | Acyclic coloring of graphs[END_REF], we have shown that the star chromatic number of a graph of maximum degree d is O(d 3 2 ) and that for every d, there exists a graph of maximum degree d whose star chromatic number exceeds ε. for some positive absolute constant ε.

A large number of problems remain open here, such as getting optimal results for other families of graphs, or refining our non optimal bounds ; getting one or several methods to provide good lower bounds for the star chromatic number is also another challenging problem.

Acknowledgments

The authors wish to thank the anonymous referees for many valuable remarks that helped to improve this paper.