Frédéric Havet
email: frederic.havet@inria.fr

Xuding Zhu
email: xudingzhu@gmail.com

The game Grundy number of graphs

Keywords: Colouring game, game Grundy number, trees, partial 2-trees

Given a graph G = (V, E), two players, Alice and Bob, alternate their turns in choosing uncoloured vertices to be coloured. Whenever an uncoloured vertex is chosen, it is coloured by the least positive integer not used by any of its coloured neighbours. Alice's goal is to minimize the total number of colours used in the game, and Bob's goal is to maximize it. The game Grundy number of G is the number of colours used in the game when both players use optimal strategies. It is proved in this paper that the maximum game Grundy number of forests is 3, and the game Grundy number of any partial 2-tree is at most 7.

Introduction

Suppose G = (V, E) is a graph. The game chromatic numbers of G are defined through a two-person game: the colouring game. Let X be a set of colours. Alice and Bob take turns in playing the game. Each play by either player consists of colouring an uncoloured vertex of G with a colour from X. Adjacent vertices must be coloured by distinct colours. The game ends if no more vertices can be coloured: either because all the vertices are coloured or because the uncoloured vertices have no legal colour, i.e., for each uncoloured vertex x, each colour from X is used by a neighbour of x. Alice wins the game if all the vertices of G are successfully coloured. Otherwise, Bob wins the game. The Alice-first colouring game is the colouring game when Alice has the first move and Bob-first colouring game is the colouring game when Bob has the first move. The Alice-first game chromatic number χ A g (G) (resp. Bob-first game chromatic number χ B g (G)) of G is the least number of colours in a colour set X for which Alice has a winning strategy in the Alice-first (resp. Bob-first) colouring game on G.

For classes H of graphs, the Alice-first game chromatic number and Bob-first game chromatic number of H are defined as respectively χ A g (H) = max{χ A g (G) : G ∈ H} and χ B g (H) = max{χ B g (G) : G ∈ H}. Although for a single graph G, there can be a big difference between χ A g (G) and χ B g (G), for natural classes of graphs, we usually have χ A g (H) = χ B g (H). For a graph G, let 2G denote the union of two disjoint copies of G, and G + denote the graph obtained from G by adding an isolated vertex. The following proposition was proved in [START_REF] Zhu | Game colouring Cartesian product of graphs[END_REF]. Proposition 1. Suppose H is a class of graphs such that if G ∈ H, then 2G ∈ H and G + ∈ H. Then χ A g (H) = χ B g (H).

Therefore when studying such graph classes it is sufficient to consider Alice-first game chromatic number. For simplicity reasons and as very often in the literature, we shall abbreviate Alice-first game chromatic in game chromatic number and write χg instead of χ A g . The colouring game on planar maps was invented by Brams, and was published by Gardner [START_REF] Gardner | Mathematical games[END_REF] in his column "Mathematical Games" in Scientific American in 1981. It remained unnoticed by the graph-theoretic community until ten years later, when it was reinvented by Bodlaender [START_REF] Bodlaender | On the complexity of some coloring games[END_REF]. Bodlaender defined the game chromatic number of graphs, and conjectured that the game chromatic number of planar graphs is bounded by a constant. Since then the problem has attracted considerable attention and the game chromatic numbers of various classes of graphs have been studied (see [START_REF] Bartnicki | The map colouring game[END_REF] for a recent survey).

We denote by F the family of forests, by I k the family of interval graphs with clique number k, by P the family of planar graphs, by Q the family of outerplanar graphs, by PT k the family of partial k-trees. It is proved by Faigle, Kern, Kierstead and Trotter [START_REF] Faigle | On the game chromatic number of some classes of graphs[END_REF] that χg(F) = 4, proved by Faigle, Kern, Kierstead and Trotter [START_REF] Faigle | On the game chromatic number of some classes of graphs[END_REF] that χg(I k ) ≤ 3k -2, proved by Guan and Zhu [START_REF] Guan | Game chromatic number of outerplanar graphs[END_REF] and Kierstead and Trotter [10] that 6 ≤ χg(Q) ≤ 7, and proved by Zhu [START_REF] Zhu | The game coloring number of pseudo partial k-trees[END_REF] that χg(PT k ) ≤ 3k + 2 for k ≥ 2, proved by Zhu [START_REF] Zhu | Refined activation strategy for the marking game[END_REF] and Kierstead and Trotter [10] that 8 ≤ χg(P) ≤ 17.

To obtain upper bounds for the game chromatic number of graphs, one usually study another game: the marking game. Suppose G = (V, E) is a graph. In the marking game on G, two players, Alice and Bob, take turns (with Alice having the first move) marking an unmarked vertex of G. The game ends when all vertices are marked. For a vertex x of G, let b(x) be the number of neighbours of x that are marked before x is marked. The score of the game is

s = 1 + max x∈V (G) b(x).
Alice's goal is to minimize the score, while Bob's goal is to maximize it. The game colouring number colg(G) of G is the least s such that Alice has a strategy that results in a score at most s in the marking game on G. For a family H of graphs, colg(H) = max{colg(G) : G ∈ H}.

The game colouring number of a graph was first formally introduced in [START_REF] Zhu | The game coloring number of planar graphs[END_REF] as a tool in the study of the game chromatic number of graphs. However, it is of independent interest. The concept itself and some of its variations have been studied extensively in the literature [START_REF] Bartnicki | The map colouring game[END_REF][START_REF] Dunn | A simple competitive graph coloring algorithm[END_REF][START_REF] Dunn | A simple competitive graph coloring algorithm[END_REF][START_REF] Guan | Game chromatic number of outerplanar graphs[END_REF][START_REF] He | Edge-partitions of planar graphs and their game coloring numbers[END_REF][START_REF] Kierstead | A simple competitive graph coloring algorithm[END_REF][START_REF] Kierstead | Competitive colorings of oriented graphs[END_REF][START_REF] Kierstead | Marking games and the oriented game chromatic number of partial k-trees[END_REF][START_REF] Kierstead | Orderings on graphs and game coloring number[END_REF][START_REF] Kierstead | Very asymmetric marking games[END_REF][START_REF] Nešetřil | On the oriented game chromatic number[END_REF][START_REF] Wu | Lower bounds for the game colouring number of partial k-trees and planar graphs[END_REF][START_REF] Zhu | The game coloring number of pseudo partial k-trees[END_REF][START_REF] Zhu | Refined activation strategy for the marking game[END_REF].

The exact value of the game colouring numbers of F, I k , Q and PT k are known. It is proved by Faigle, Kern, Kierstead and Trotter [START_REF] Faigle | On the game chromatic number of some classes of graphs[END_REF] that colg(F) = 4, proved by Faigle, Kern, Kierstead and Trotter [START_REF] Faigle | On the game chromatic number of some classes of graphs[END_REF] and Kierstead and Yang [START_REF] Kierstead | Very asymmetric marking games[END_REF] that colg(I k ) = 3k -2, proved by Guan and Zhu [START_REF] Guan | Game chromatic number of outerplanar graphs[END_REF] and Kierstead and Yang [START_REF] Kierstead | Very asymmetric marking games[END_REF] that colg(Q) = 7, and proved by Zhu [START_REF] Zhu | The game coloring number of pseudo partial k-trees[END_REF] and Wu and Zhu [START_REF] Wu | Lower bounds for the game colouring number of partial k-trees and planar graphs[END_REF] that colg(PT k ) = 3k + 2 for k ≥ 2. It is also known [START_REF] Zhu | Refined activation strategy for the marking game[END_REF][START_REF] Wu | Lower bounds for the game colouring number of partial k-trees and planar graphs[END_REF] that 11 ≤ colg(P) ≤ 17.

It is easy to see that for any graph G, χg(G) ≤ colg(G) and for many natural classes of graphs, the best known upper bounds for their game chromatic numbers are obtained by finding upper bounds for their game colouring numbers.

In this paper, we introduce a game, the greedy colouring game. In some sense, this new game is a mixture of the colouring game and the marking game. Suppose G = (V, E) is a graph. Two players, Alice and Bob, alternate their turns in choosing an uncoloured vertex and colour it greedily, that is with the minimum positive integer not already assigned to one of its coloured neighbours. The aim of Alice is to minimize the number of used colours and the aim of Bob is to maximize it. Again, there are two greedy colouring games depending wether Alice or Bob has the first move. Assume both players use their optimal strategies, the number of colours used at the end of the game is called the Alice-first game Grundy number of the graph if Alice plays first, and the Bob-first game Grundy number if Bob plays first. It is denoted by Γ A g (G) and Γ B g (G) respectively. At the end, the obtained colouring is a greedy colouring so the two game Grundy numbers are greater than or equal to the chromatic number and less or equal to the Grundy number.

For classes H of graphs, the Alice-first game Grundy number and Bob-first game Grundy number of H are defined as respectively

Γ A g (H) = max{Γ A g (G) : G ∈ H} and Γ B g (H) = max{Γ B g (G) : G ∈ H}.
Similarly to game chromatic numbers, the two numbers Γ A g (G) and Γ B g (G) may differ a lot, for example for the graph K * n,n obtained from the complete bipartite graph Kn,n by removing a perfect matching.

Proposition 2. If n ≥ 2, then Γ A g (K * n,n ) = n and Γ B g (K * n,n ) = 2.
Proof. Suppose that Alice starts, then Bob will always play on the vertex joined to the one Alice played by an edge of the removed matching. It is then easy to see that n colours are used, one per edge of the removed matching. Hence

Γ A g (K * n,n ) ≥ n. It is well known that Γ(K * n,n ) = n, so Γ A g (K * n,n ) = n.
Suppose now that Bob starts. Let us denote by (V1, V2) the bipartition of K * n,n . Bob first colour one vertex v with 1. Without loss of generality, v ∈ V1. Then Alice can play on another vertex w of V1. This vertex will be coloured 1. Now every vertex of V2 is adjacent to either v or w, so no vertex of V2 will be coloured 1. Thus each time a player will choose a vertex of V1, he will colour it with 1, since it has no neighbour coloured 1. Hence at the end all the vertices of V1 will be coloured 1. Therefore, each time a player chooses a vertex of V2, he will colour it with 2, since it is only adjacent to vertices coloured 1. So all the vertices of V2 will be coloured 2.

So Γ B g (K * n,n ) ≥ 2. Since χ(K * n,n ) = 2, we have Γ B g (K * n,n ) = 2.
In the above proposition Alice-first game Grundy number is larger than Bob-first game Grundy number, but it can be the converse. Consider the graph H = (K * n,n ) + . Then the first player could play on the isolated vertex and then apply the strategy of Proposition 2 as second player. Hence

Γ A g (H) = 2 and Γ B g (H) = n. Suppose H is a class of graphs. Let Γ A g (H) = max{Γ A g (G) : G ∈ H}, and Γ B g (H) = max{Γ B g (G) : G ∈ H}.
Similarly to Proposition 1, for natural classes of graphs, we usually have

Γ A g (H) = Γ B g (H). Proposition 3. Suppose H is a class of graphs such that if G ∈ H, then 2G ∈ H and G + ∈ H. Then Γ A g (H) = Γ B g (H). Proof. Assume Γ B g (H) = k. Then there is a graph G ∈ H such that Γ B g (G) > k -1, i.e.
, Bob has a strategy, called BWIN-Strategy, to ensure that the maximum colour used in the greedy colouring game is at least k.

Assume first that G has an odd number of vertices. We shall show that Γ A g (2G) > k -1. Let the two copies of G in 2G be G1 and G2. Assume Alice colours a vertex of G1 in her first move. Then Bob colours a vertex of G2 in his first move, according to BWIN-Strategy. From then on, whenever Alice colours a vertex of G2, Bob also colours a vertex of G2, using BWIN-Strategy. If Alice colours a vertex of G1, then Bob colours an arbitrary vertex of G1. Because G1 has an odd number of vertices, whenever Alice colours a vertex of G1, Bob can find an uncoloured vertex in G1 and colours it. Thus Γ A g (2G) > k-1. If G has an even number of vertices, the same argument as above shows that Bob has a winning strategy for the A-colouring game on (2G) + . This proves that

Γ A g (H) ≥ k. Assume Γ A g (H) = k. Then there is a graph G ∈ H such that Γ A g (G) > k -1.
Then for the greedy colouirng game on G + , Bob can simply colour the added isolated vertex in his first move, and then use his winning strategy for the A-colouring game afterward. This proves that Γ B g (H) ≥ k, and hence completes the proof of Proposition 3.

In this paper, we study the game Grundy number of F and PT 2 which satisfies the hypothesis of Proposition 3. Hence, we will consider Alice-first game Grundy number, so we abbreviate it in game Grundy number. We also write Γg instead of Γ A g . Clearly, Γg ≤ colg. Hence, since colg(F) = 4 and colg(PT 2) = 8, we have Γg(F) ≤ 4 and Γg(PT 2) ≤ 8. In this paper, we improve these two bounds. We shall prove that Γg(F) = 3 and Γg(PT 2) ≤ 7. We first prove in Theorem 6 that the game Grundy number of a forest is at most 3 and then show in Remark 7 trees whose game Grundy number is 3. Finally we prove and the game Grundy number of a partial 2-tree is at most 7. We do not know if there are partial 2-trees with game Grundy number 7.

By definition, χ(G) ≤ Γ(G). But the similar inequality does not hold for game numbers, because χg(G) may be bigger than Γg(G). Indeed χg(F) = 4 and Γg(F) = 3. Hence a natural question is to ask if the game chromatic number can be very large compared to the game Grundy number. In Section 4, we answer by the affirmative by showing graphs

G k , k ≥ 2, such that Γg(G k ) = k and χg(G k ) = 2 k-1 + 1.
However we do no not know whether the the game chromatic number can be bounded by a function of the game Grundy number. On the opposite, we do not know if the Grundy game number can be bigger than the game chromatic number or not.

Problem 5. Is it true that Γg(G) ≤ χg(G) for all graph G? And, if not, can Γg be arbitrarily large compared to χg?

2 Game Grundy number of a forest Theorem 6. If F is a forest, then Γg(F ) ≤ 3.

Proof. Let us first start with few definitions. A vertex of a forest is called a leaf if it has degree at most 1 and a node if it has degree at least 3. A vertex which is not a leaf is an inner vertex.

Given a partial colouring c of a forest F , the c-components, or simply components, are the inclusion-wise maximal subtrees such that no inner vertex is coloured, i.e. such that every coloured vertex is a leaf. A component is empty if it is an edge and its two vertices are coloured. If C is a component, then its core is its minimum subtree containing all its coloured leaves.

A component C is good if it is of one of the following types.

Type I: Exactly two leaves are coloured in {2, 3}, these leaves are at distance different from 2 and no other leaves are coloured.

Type II: Exactly one leaf is coloured in {2, 3} and the core of C has at most one node. Moreover, if one leaf is coloured 3 and C has a node, then the leaf of colour 3 is not adjacent to the node.

Type III: No leaves are coloured in {2, 3} and the core of C has at most two nodes.

Type IV: No leaf is coloured 3, at least two leaves are coloured 2 and the core of C has a unique node which is adjacent to all leaves coloured 2.

A component which is not good is said to be bad.

It is simple matter to see that if a player chooses a vertex in a good component then it is coloured in {1, 2, 3}. Indeed to be coloured at least 4, it must be adjacent to three coloured vertices, two of which are coloured in {2, 3}.

Let us show that Alice can play so that after each of her turns, all the components are good. Trivially at the beginning all the components are of Type III.

Suppose first that after Bob plays, all the components are good. We will show that Alice can play on a component so that no bad component is created.

• Suppose that there exists a nonempty component of Type I. Then the distance between the two coloured leaves is at least 3. Alice plays on the neighbour of one of these leaves. This vertex will be coloured 1, because its only coloured neighbour is coloured in {2, 3}. Hence all the new components are good.

• Suppose now that there exists a nonempty component C of Type II. Let v be the leaf coloured in {2, 3}. Alice colours the neigbour w of v in the core (or any neighbour of v if the core is restricted to v). If vertex w gets colour 1, all the nontrivial new components are of Type III. If not, then w is coloured in {2, 3} and must be adjacent to a leaf of C coloured 1. In particular, if the core of C has a node, it is w. Hence, all the nonempty new components are of Type II.

• Suppose that there exists a nonempty component C of Type III. Alice plays on a node of a core if one exists or on any neighbour of a leaf if there is no. The chosen vertex w will be coloured either 1 or 2 and the cores of the new components will have at most one node each. Hence all the new components are of type II or III.

• Suppose finally that there exists a component C of Type IV. Alice plays on the node of its core. This vertex is then coloured 1 or 3 and all the nonempty new components are of type II or III.

Suppose now that after Bob's play, a bad component was created. We distinguish four cases according to the type of the component onto which Bob has played. 1) Assume that Bob played on a component C of Type I. Let u and v be the two coloured leaves of C. The core of C is the path P from u to v. Observe that Bob has not played on a vertex of P , otherwise all the created components would be good. Hence, Bob played on a vertex w outside P . Then w is coloured 1. All the created components not containing u and v are trivially of Type III, as their unique coloured leaf is w. Let us now consider the component C containing u, v and w. Since P has length at least 3, then one vertex of {u, v}, say u, is not adjacent to the node of the core of C . Alice colours its neighbour z. It will be coloured 1, and thus C is cut into an empty component, a component of Type II, (the one containing z, v and w) and all the others are of Type III, since their unique coloured leaf is z.

2) Assume that Bob played on a component C of Type II.

Let u be the vertex of C coloured in {2, 3}.

-Assume Bob played on a vertex w outside the core of C. -Assume Bob played on a vertex w in the core of C. Then w cannot be coloured 1, because a bad component must be created. It cannot be coloured 3 neither. Indeed it were, it would be adjacent to u and another leaf coloured 1 of C. So w would be node of the core of C, and all the nonempty new components would be of type II. Hence w is coloured 2. Then it must on the path between the node t of the core of C and a leaf distinct from u.

In this case, the unique bad component C is the one that contains u and w. If one of u and w has a neighbour z which is not the node of C then Alice colours z. The vertex z is coloured 1, so all the new components are of Type II or I. If not, then u and w are both adjacent to t. In particular, u is coloured 2, by definition of Type II component. Alice plays on t, which must be coloured 1 or 3, because it is adjacent to no vertex coloured 3. Hence, all the nonempty new components are of type II or III.

3) Assume that Bob played on a component C of Type III.

-Assume Bob played on a vertex w outside the core of C. Then w is coloured 1. The created bad component C must have three nodes in its core. Alice plays on the node t which is in the middle, i.e. on the path joining the two others. The vertex t can only be adjacent to vertices coloured 1, so it is coloured in {1, 2}, and all the new components have at most one node. So they are of type II or III.

-Assume Bob played on a vertex w in the core of C. Then w cannot be coloured 1 otherwise all the components are of type III. So w is coloured 2, because it is adjacent to no vertex coloured 2. Thus, the bad component C obtained after Bob's play must contain w and have two nodes t1 and t2 in its core. If w is adjacent to none of these nodes, then Alice plays in the neighbour z of w in the core of C . Then z must be coloured 1 and all the new components are of type III. Assume now that w is adjacent to one of the nodes say t1. If t1 is not adjacent to t2, then Alice plays on t1. The vertex t1 is coloured 3 or 1 and all the new components are of type II or III. If t1 and t2 are adjacent, then Alice plays on t2. The vertex t2 is then coloured 1 or 2, because it is adjacent to no vertex coloured 2. Hence all the new components are of type II, III and possibly one is of type IV.

4) Assume that Bob played on a component C of Type IV.

-Assume Bob played on a vertex w outside the core of C. Then w is coloured 1. If one bad component C has been created, then it must have two nodes in its core. One of them t1 is the one of the core of C and thus is adjacent to all the leaves coloured 2. Let t2 be the second node of the core of C . If t1 is not adjacent to t2, then Alice plays on it. So t1 gets either colour 1 or 3, because it is adjacent to no vertex coloured 3 and to vertices coloured 2.. Hence all the nonempty new components are of type III or II. If t1 is adjacent to t2, then Alice plays on t2. This vertex gets colour 1 or 2, because it is adjacent to no vertex coloured 3. Hence the new component containing t1 is still of type IV, and all the other new ones are of type II or III.

-Assume Bob played on a vertex w in the core of C. Then w is not coloured 1 because a bad component must be created. It cannot be coloured 3 neither, for otherwise it must be the node of the core of C, and so all the nonempty created components are of type II. Hence w is coloured 2. Thus it is not adjacent to the node t of the core of C, because a bad component must be created. Alice plays on t, which gets coloured 1 or 3. Then all the nonempty new components are of type II or III.

Remark 7. The bound 3 in Theorem 6 is best possible, because there are trees T for which Γ A g (T ) = 3 and Γ B g (T ) = 3. Consider for example the path on seven vertices P7 = (v1, . . . , v7).

Suppose that Alice plays first. Without loss of generality she played on some vi with i ≤ 4. Then Bob plays on vi+3. In the remainder of the game, the first chosen vertex among {vi+1, vi+2} will be coloured 2 and the second one will be coloured 3. Hence Γ A g (P7) = 3. Suppose now that Bob plays first. Then he plays on v4. Without loss of generality, we may assume that Alice played on vi for 1 ≤ i ≤ 3. Bob plays on v7. Similarly, the two vertices {v5, v6} will be coloured 2 and 3.

Game Grundy number of a partial 2-tree

A k-tree is defined inductively as follows: K k+1 is a k-tree and if G is a k-tree then every graph obtained from G by adding a vertex and linking it to the k vertices of a clique of G is a k-tree. Obviously, the class of 1-trees is the one of trees. To every k-tree, one can associate the ordering of the vertices (v1, . . . , vn) corresponding to the order in which the vertices are added in the inductive construction. Hence {v1, . . . , v k+1 } is the original clique and for every i ≥ k + 1, vertex vi has exactly k left neighbours which form a clique (we think of the vertices as line up from left to right).

A partial k-tree is a subgraph of a k-tree.

Theorem 8. If G is a partial 2-tree, then Γg(G) ≤ 7.
Proof. Let G be a partial 2-tree and let H be a 2-tree containing G and (v1, . . . , vn) be the ordering associated to H. We consider an ordering as a placement on a line from left to right. Hence a vertex is left (resp. right) to another it is has smaller (resp. larger) index. The strategy used by Alice is the one described in [START_REF] Zhu | The game coloring number of pseudo partial k-trees[END_REF] to prove that colg(G) ≤ 8. Alice will record a set of active vertices. A coloured vertex is necessarily activated, but some activated vertices are not coloured. An uncoloured vertex will become active only if it is activated by Alice as described below. In particular, no vertex is active at the beginning. Suppose that Bob plays on a vertex v. Then Alice plays according to the following algorithm. All the considered adjacencies are in H.

0. If all its left neighbours are coloured, then Alice plays on the leftmost vertex with smallest index, otherwise let u := v.

1. Let w be the uncoloured left neighbour of u with smallest index.

2. If w is activated or its two left neighbours are already coloured, then Alice colours u. Otherwise, activate u and let u := w and Go to Step 1.

When we do the operation u := w in Step 2, we say that Alice jumps from u to w. Hence the above algorithm may be seen as follows: Alice jumps from a vertex to its leftmost uncoloured left neighbour until she cannot jump anymore. She activates all the vertices onto which she jumps, and colour the one on which she stops. When Alice jumps from vertex u to vertex w, we orient the edge uw from u to w. At the end of each move of Alice, a set F of edges of H is oriented (oriented edges remain oriented afterwards). Set D = (V (G), F ).

Observe that Alice jumps at most once from a vertex and at most twice onto a vertex and that she colours the vertex the second time she jumps onto it. In particular, every vertex of D has outdegree at most 1 and indegree at most 2. In addition, if a vertex has indegree 2, then its outdegree is 1.

For every vertex x, let P (x) be the set of neighbours of x that are coloured previously to x, and let R(x) be the set of vertices in P (x) right to x.

(x) = R (x) ∪ R (x) with R (x) = R(x) ∩ N -(x) and R (x) = R(x) ∩ (N -(x1) ∪ N -(x2)).
Proof. Let z be a vertex in R(x). If Alice coloured z, then she did it when jumping a second time on it, because one of its left neighbour, namely x, is uncoloured. Then the first time Alice jumped onto z, she has jumped again from z onto another vertex. If Bob coloured z, then Alice has jumped to one of its left neighbour. So, in both cases, Alice has jumped from z. If Alice did not jump from z to x, then she jumped to a vertex left to x. That vertex must be adjacent to x since the left neighbourhood of every vertex is a clique in H. Hence Alice jumped from z to either x1 or x2. Let q be the vertex of R (v) which is coloured last and let p be the other vertex of R (v) if it exists. For convenience and with a slight abuse of notation, S \ {p} will denote the set S if p does not exists. Claim 8.3. Bob coloured q right before Alice coloured v and R (q) = ∅.

Proof. We claim that Alice coloured v right after jumping from q. Indeed if |R (v)| = 2, then Alice have jumped twice on v and thus Alice has coloured v jumping from q. If |R (v)| = 1, then, as |R(v)| = 5, Claim 8.2 yields |R (v)| = 4. Thus Alice has not jumped from v to x1 or x2, and so she coloured v the first time she jumped onto it. But to v, she only jumped from q. Now observe that Alice never jumps from a coloured vertex unless Bob just coloured it. So Bob coloured q and Alice did not. Since Alice jump at most once from a vertex, she has not jumped from q before colouring it. Therefore she has not jumped onto q before colouring it, otherwise she would have jumped, because v was still available. Hence R (q) = ∅. Assume that no vertex of {v1, v2} is coloured in {1, 2, 3}. For each w ∈ R (v), a colour of {1, 2, 3} is not assigned to any of its coloured neighbour. Hence w is coloured at most 3. Therefore, when Alice coloured v, this vertex had at most three neighbours (v1, v2 and q) coloured in {4, 5, 6, 7}. So she coloured it with a colour smaller than 8, a contradiction.

Assume now that at least one vertex v of {v1, v2} is coloured in {1, 2, 3}. Every vertex w of R (v) is coloured at most 4, since |P (w)| ≤ 3. Therefore, when Alice coloured v, this vertex had at most two neighbours (q and the one of {v1, v2} \ {v }) coloured in {5, 6, 7}. So she coloured it with a colour smaller than 8, a contradiction. Claim 8.6. |P (q) \ {p}| ≤ 3.

Proof. Let r be the left neighbour of q distinct from v. By Claim 8.3, R (q) = ∅. Hence a vertex in P (q) \ {p} is either r or one of the at most two inneighbours of r. Moreover, if there is equality, then t3 and the two vertices of N -(v1) are in P (v1). Thus v is not in N -(v1), because it is not in P (v1) for it is coloured after v1. As v is in N -(v1) ∪ N -(v2), it is an inneighbour of v2. Claim 8.9. v2 is coloured 7, p is coloured 6, v1 is coloured 5, q is coloured 4 and the vertices of R (v) are coloured in {1, 2, 3}.

Proof. By Claims 8.4, 8.6, 8.7 and 8.8, every vertex x of P (v) \ {v2} satisfies |P (x)| ≤ 5 and thus is coloured at most 6. Hence v2 is coloured 7. Now every vertex x of P (v) \ {p, v2} satisfies |P (x) \ {v2}| ≤ 4 and thus is coloured at most 5. Hence p is coloured 6. Furthermore, every vertex x of P (v) \ {p, v1, v2} satisfies |P (x) \ {p, v2}| ≤ 3 and thus is coloured at most 4. Hence v1 is coloured 5. Finally, every vertex w of R (v) satisfies |P (w) \ {p, v1, v2}| ≤ 2 and thus is coloured at most 3. Hence q is coloured 4.

Let y1 and y2 be the two left neighbours of v2. Since N -(v2) = 2, one of these vertices, say y1 is an outneighbour of v2. P (v2) ⊂ {y1, y2} ∪ N -(y1) ∪ N -(y2) ∪ N -(v2). By Claim 8.9, v1 is coloured 5, so |P (v1)| ≥ 4. Thus, by Claim 8.8, v is an inneighbour of v2. Let w be the inneighbour of v2 distinct from v. Then w ∈ R (v) and thus w is coloured at most 3. Now P (v2) ⊂ {y1, y2, w} ∪ N -(y1) ∪ N -(y2), because v is coloured after v2. Moreover since v2 ∈ N -(y1) ∪ N -(y2), this yields |P (v2)| ≤ 6. But v2 is coloured 7 by Claim 8.9, so |P (v2)| = 6. In addition, the three inneighbours of y1 and y2 different from v2 are in R (v2). This implies that v3 / ∈ {y1, y2} because by Claim 8.8, t3 is not in R (v2) since its two left neighbours are v1 and v3.

Set

Z = (N -(y1) ∪ N -(y2)) \ {v2}. Claim 8.10. If z is a vertex of Z, then R (z) = ∅.
Proof. Assume for a contradiction that there exists a vertex t ∈ R (z). Then it must be an inneighbour of v2 or yi for some i ∈ {1, 2}. But an inneighbour of yi (distinct from v2) has v2 and yi as left neighbours and thus is not a right neighbour of z.

And an inneighbour of v2 is either v which is coloured after z, or a vertex of R (v) which is not a right neighbour of z since its left neighbours are in {v1, v2, v}.

We now get a contradiction in a similar way as the proof of Claim 8.5. Assume first that no vertex of {y1, y2} is coloured in {1, 2, 3}. For each z ∈ Z, a colour of {1, 2, 3} is not assigned to any of its coloured neighbour. Hence z is coloured at most 3. Therefore, when Alice coloured v2, this vertex had at most two neighbours coloured in {4, 5, 6}. So she coloured it with a coloured smaller than 7, a contradiction.

Assume finally that at least one vertex y of {y1, y2} is coloured in {1, 2, 3}. Every vertex z of Z is coloured at most 4, since |P (z)| ≤ 3. Therefore, when Alice coloured v2, this vertex had at most one neighbour (the one of {y1, y2} \ {y }) coloured in {5, 6}, namely y1 and y2. So she coloured v2 with a colour smaller than 7, a contradiction.

Graphs with game chromatic number larger than game Grundy number

For two graphs the disjoint union of two copies of G1 and G2 is denoted G1 + G2. The join of G1 and G2 is the graph G1 ⊕ G2 obtained from G1 + G2 by joining all the vertices of the copy of G1 to all the vertices of the copy of G2. For a positive integer p, we denote by pG the disjoint union of p copies of G.

A cograph is a graph without induced subgraph isomorphic to P4, the path on four vertices. The family of cographs may also be defined inductively as follows:

• K1 is a cograph;

• if G1 and G2 are cographs, then G1 + G2 and G1 ⊕ G2 are cographs.

It is well known that if G is a cograph, then χ(G) = Γ(G). Since χ(G) ≤ Γg(G) ≤ Γ(G), we have the following. Proof. We will construct by induction a sequence (G k ) of cographs satisfying Γg(G k ) = k and χg(G k ) ≥ 2 k-1 + 1.

Let p k = 2 k-1 + 1. Observe that p2 = 3 and p k = 2p k-1 -1. For any integer q, we denote by Sq the graph with q vertices and no edges.

G2 is the cycle of length 4. It is a cograph and Γg(G2) = χ(G2) = 2 and χg(G2) = 3.

For every k ≥ 2, let G k+1 = p k G k ⊕ S2p k -2.
A simple induction implies that every G k has an even number of vertices because G2 does.

Moreover every G k is a cograph since it obtained from cographs by a series of disjoint union and joins. Hence Γg(G k ) = χ(G k ) by Proposition 9. In addition, since for any graphs G and H and integer p, χ(pG) = χ(G) and χ(G ⊕ H) = χ(G) + χ(H), it follows that χ(G k+1 ) = χ(G k ) + 1. Hence by induction, Γg(G k ) = χ(G k ) = k for all k ≥ 2.

Let us now prove by induction that χg(G k ) ≥ p k for all k ≥ 2, the result holding for k = 2. Let k ≥ 2. Since χg(G k ) > p k -1, Bob has a strategy, called BWIN, to win the colouring game on G k with colour set {1, . . . , p k -1}. Let us describe a strategy so that Bob wins on G k+1 with {1, . . . , p k+1 -1}. In the first p k -1 of its moves, Bob assign p k -1 different colours, say those of {p k , . . . , p k+1 -1}, to different vertices of the copy of S2p k -2. This is always possible because at most 2p k -3 vertices are played on before Bob plays its (p k -1) th move. After these first moves all the colours in {p k , . . . , p k+1 -1} are used on the copy Sp k -2, so only colours in {1, . . . , p k -1} may be used when playing on vertices of p k G. Note moreover that before Bob's (p k -1) th move, Alice has played at most p k -1 times, so one of the copies of G k in p k G, say G * , as not been played on. The strategy of Bob from its p th move on will then be the following: if Alice does not play on G * , then Bob plays also on a vertex not in G * (This is possible because G k+1 -G * has an even number of vertices.); if Alice plays on G * , then Bob plays also on G * according to the strategy BWIN. Thus all the vertices of G * will not be coloured and Bob wins. Hence χg(G k+1 ) > p k+1 -1.

Problem 4 .

 4 Does there exists a function f such that, χg(G) ≤ f (Γg(G)) for all graph G?

Claim 8 . 1 .

 81 Let x be a vertex with left neighbours x1 and x2. Then R

Claim 8 . 2 .

 82 For every vertex x, we have |R (x)| ≤ 2, |R (x)| ≤ 4 and |R(x)| ≤ 5. Proof. Alice jumps at most twice on each vertex, so |R (x)| ≤ 2 and |R (x)| ≤ 4. Furthermore, if |R (x)| = 2, then |R (x)| ≤ 3, because the first time Alice jumped onto x, she did not colour it. So she must have jumped onto one of its left neighbours. Hence at most three of the vertices from which Alice jumped onto {x1, x2} are distinct from x. It follows that |R(x)| ≤ 5. Suppose by way of contradiction that there exists a vertex v coloured 8. Let v1 and v2 be its two left neighbours with v2 left to v1. Necessarily, |P (v)| ≥ 7. Hence, since R(v) = P (v) \ {v1, v2}, Claim 8.2 yields |R(v)| = 5 and {v1, v2} ⊂ P (v).

Claim 8 . 4 .

 84 If w ∈ R (v), then |R(w) \ {p}| ≤ 2. Proof. Let w ∈ R (v). Then its left neighbours are v and the outneighbour v ∈ {v1, v2} of w. Let z be in R (w). Alice must have jumped from z to a left neighbour of z left from w. Since the left neighbourhoods are cliques, it must be onto v or v . Let x1, x2 be the two inneighbours of v . Since |R(v)| = 5, we conclude that v and v are the two left neighbours of x1, x2. Hence w is not a left neighbour of x1 or x2. Moreover q was not coloured when w is coloured by Claim 8.3. Hence R (w) ⊂ {p}. By Claim 8.2, we get |R(w) \ {p}| ≤ 2. Claim 8.5. |R (v)| = 3. Proof. Suppose for a contradiction that |R (v)| = 4. Then by Claim 8.4, |R(w)| ≤ 2 for all w ∈ R (v). The left neighbourhood of every vertex w of R (v) is {v, v w } with v w ∈ {v1, v2} and so P (w) ⊂ R(w) ∪ {v w }.

Claim 8 . 7 .

 87 |P (p)| ≤ 5.Proof. Let r be left neighbour of p distinct from v. The vertices q and v are coloured after p, thusP (p) ⊂ {r} ∪ N -(r) ∪ N -(p). So |P (p)| ≤ 5.Let v3 be the left neighbour of v1 distinct from v2. Claim 8.8. |P (v1) \ {v2}| ≤ 4. Moreover if |P (v1) \ {v2}| = 4, then v2 is an outneighbour of v and the inneighbour t3 of v3 distinct from v1 is in R(v1). Proof. By Claim 8.5, |R (v)| = 2, so N -(v) = 2 and thus N + (v) = 1. So Alice has jumped from v to one of its left neighbours. Hence |N -(v1) ∪ N -(v2)| = |R (v) ∪ {v}| = 4 and so |N -(v1)| = |N -(v2)| = 2. Therefore |N + (v1)| = |N + (v2)| = 1. The outneighbour of v1 is necessarily v3 because the inneighbours of v2 are in R (v) ∪ {v}. Now P (v1) ⊂ {v2, v3} ∪ N -(v1) ∪ N -(v2) ∪ N -(v3). But every vertex in N -(v2) is either v or has v and v2 as left neighbours. In both cases it is not a right neighbour of v1. Therefore P (v1) ⊂ {v2, v3} ∪ N -(v1) ∪ N -(v3) and so P (v1) ⊂ {v2, v3, t3} ∪ N -(v1) because N -(v3) = {v1, t3}. Hence, |P (v1) \ {v2}| ≤ 4.

Proposition 9 .

 9 If G is a cograph, then χ(G) = Γg(G) = Γ(G).Theorem 10. For integer k ≥ 2, there exists a graph G k such that Γg(G k ) = k and χg(G k ) ≥ 2 k-1 + 1.

  Then w is coloured 1. Moreover, C is cut into components of type III and one component C containing w and all the coloured leaves of C. Let t be the neighbour of u in the core of C . If t has no neighbour coloured 1, then Alice plays on t. Then t is coloured 1, so all the new nonempty components are of type III. Assume now that t has a neighbour coloured 1, then t is one of the two nodes of the core of C . If u is coloured 3 (resp. u is coloured 2 and t is not adjacent to the second node of the core of C ), then Alice plays on t. Then t is coloured 2 (resp. 3), so all the new nonempty components are of type II. Finally if u is coloured 2 and t is adjacent to the second node s of the core of C , then Alice plays on s. It will be coloured either 1 or 2 since it can only be adjacent to vertices of colour 1. Hence all the new components are of type IV, III or II.

Partly supported by the French Agence Nationale de la Recherche under Grant GRATEL ANR-09-blan-0373-01.


Frédéric Havet
email: fhavet@inria.sophia.fr

Leonardo Sampaio
email: leonardo.sampaio_rocha@inria.sophia.fr

On the Grundy and b-chromatic numbers of a graph

Keywords: Colouring, Online Colouring, Greedy Colouring, NP-completeness, Fixed Parameter Complexity

The Grundy number of a graph G, denoted by Γ (G), is the largest k such that G has a greedy k-colouring, that is a colouring with k colours obtained by applying the greedy algorithm according to some ordering of the vertices of G. Trivially Γ (G) ≤ ∆(G) + 1. In this paper, we show that deciding if Γ (G) ≤ ∆(G) is NP-complete. We then show that deciding if Γ (G) ≥ |V (G)|k is fixed parameter tractable with respect to the parameter k.

Introduction

A k-colouring of a graph G = (V, E) is a surjective mapping c : V → {1, 2, . . . , k} such that c(u) = c(v) for any edge uv ∈ E. A k-colouring may also be seen as a partition of the vertex set of G into k disjoint stable sets S i = {v | c(v) = i}, 1 ≤ i ≤ k. For convenience (and with a slight abuse of terminology), by colouring we mean either the mapping c or the partition (S 1 , . . . , S k ). The elements of {1, . . . , k} are called colours. We may sometimes refer to S i by its colour i. A graph is k-colourable if it admits a k-colouring. The chromatic number is

χ(G) = min{k | G is k-colourable}.
The most basic and most widespread on-line algorithm producing colourings is the greedy algorithm or first-fit algorithm. A greedy colouring relative to a vertex ordering σ = v 1 < v 2 < • • • < v n of V (G) is obtained by colouring the vertices in the order v 1 , . . . , v n , assigning to v i the smallest positive integer not already used on its lowered-indexed neighbours. A greedy colouring has the following property: For every j < i, every vertex v in S i has a neighbour in S j .

(P ) Otherwise v would have been coloured by an integer not greater than j. Conversely, a colouring satisfying Property (P ) is a greedy colouring relative to any vertex ordering in which the vertices of S i precede those of S j when i < j. The Grundy number Γ (G) is the largest k such that G has a greedy k-colouring. Hence the Grundy number and its ratio with the chromatic number measure how bad the greedy algorithm may perform on a graph. Easily, χ(G) ≤ Γ (G) ≤ ∆(G)+ 1.

Determining the chromatic number of a graph is well-known to be an NP-hard problem. Similarly, determining the Grundy number of a graph is NP-hard [START_REF] Zaker | Results on the Grundy chromatic number of graphs[END_REF]. But deciding if the chromatic number of a graph is at most k is NP-complete [START_REF] Garey | Some simplified NP-complete graph problems[END_REF] for k ≥ 3, whereas Zaker [START_REF] Zaker | Results on the Grundy chromatic number of graphs[END_REF] showed that for any fixed k, it is decidable in polynomial time if a given graph has Grundy number at most k. To show this, he proved that there is a finite number of graphs called k-atoms such that if Γ (G) ≥ k then G contains a k-atom as an induced subgraph.

A colouring of G is a b-colouring if every colour class has a b-vertex, that is a vertex with at least one neighbour in each other colour class. The b-chromatic number of a graph G, denoted χ b (G), is the largest integer k such that G admits a b-colouring with k colours. Since an optimal proper colouring of G is trivially a b-colouring, and that every b-vertex has at most ∆(G) neighbours, we have χ(G) ≤ χ b (G) ≤ ∆(G) + 1. Note that the Grundy and b-chromatic number may not be bounded one in function of the other. For example, the disjoint union of k stars of degree at least k -1 has b-chromatic number k, while its Grundy number is 2.

Deciding whether a graph admits a b-colouring with a given number of colours is an NP-complete problem, even for connected bipartite graphs [START_REF] Kratochvil | On the b-chromatic number of graphs[END_REF] or chordal graphs [START_REF] Havet | b-coloring of tight graphs[END_REF].

Brooks [START_REF] Brooks | On colouring the nodes of a network[END_REF] proved that, for any connected graph G, χ(G) ≤ ∆(G) unless G is a complete graph or an odd cycle. This implies that it can be checked in polynomial time if χ(G) ≤ ∆(G). Extensions of Brooks' Theorem have also been considered. A well-known conjecture of Borodin and Kostochka [START_REF] Borodin | On an upper bound of a graph's chromatic number, depending on the graph's degree and density[END_REF] states that every graph of maximal degree ∆ ≥ 9 and chromatic number at least ∆ has a ∆-clique. Reed [START_REF] Reed | A strengthening of Brooks' theorem[END_REF] proved that this is true when ∆ is sufficiently large, thus settling a conjecture of Beutelspacher and Herring [START_REF] Beutelspacher | Minimal graphs for which the chromatic number equals the maximal degree[END_REF]. Further information about this problem can be found in the monograph of Jensen and Toft [START_REF] Jensen | Graph coloring problems[END_REF]Problem 4.8]. Generalisation of this problem has also been studied by Farzad, Molloy and Reed [START_REF] Farzad | ∆k)-critical graphs[END_REF] and Molloy and Reed [START_REF] Molloy | Colouring graphs when the number of colours is nearly the maximum degree[END_REF]. In particular, it is proved [START_REF] Molloy | Colouring graphs when the number of colours is nearly the maximum degree[END_REF] that determining whether a graph with large constant maximum degree ∆ is (∆q)colourable can be done in linear time if (q + 1)(q + 2) ≤ ∆. This threshold is optimal by a result of Emden-Weinert, Hougardy and Kreuter [START_REF] Emden-Weinert | Uniquely colourable graphs and the hardness of colouring graphs of large girth[END_REF], since they proved that for any two constants ∆ and q ≤ ∆ -3 such that (q + 1)(q + 2) > ∆, determining whether a graph of maximum degree ∆ is (∆q)-colourable is NP-complete.

On the opposite, Theorem 3 of [START_REF] Havet | b-coloring of tight graphs[END_REF] imply that it is NP-complete to decide if a given graph G satisfies χ b (G) = ∆(G). Thus there is no analog of Brooks' Theorem for b-colouring.

A natural question is then to ask if an analog of Brooks' Theorem exists for the Grundy number. One may ask if it is decidable in polynomial time whether a graph G satisfies Γ (G) = ∆(G) + 1. In Section 2, we answer this question in the negative by showing that this problem is NP-complete even when restricted to bipartite graphs. In particular, it implies that it is NP-hard to compute the Grundy number of a bipartite graph.

We then investigate some parameterized versions of the Grundy number problem and the b-chromatic number problem. For an introduction to parameterized algorithms and complexity, we refer the reader to [START_REF] Downey | Parameterized Complexity[END_REF] or [START_REF] Niedermeier | Invitation to Fixed-Parameter Algorithms[END_REF]. Telle (See [START_REF] Downey | Parameterized Complexity[END_REF], Exercise 3.2.7) proved that the following problem is Fixed Parameter Tractable (FPT).

Dual of Colouring

Instance: A graph G and an integer k.

Parameter: k. Question: χ(G) ≤ |V (G)| -k?
In Section 3, we show that the analog for greedy colouring is also FPT.

Dual of Greedy Colouring

Instance: A graph G and an integer k.

Parameter: k. Question: Γ (G) ≥ |V (G)| -k ?
In Section 4, we show that the analog for b-colouring is also FPT.

Dual of b-colouring

Instance: A graph G and an integer k.

Parameter: k. Question: χ b (G) ≥ |V (G)| -k ?
In fact, Telle showed Dual of Colouring is FPT by showing that it has a quadratic kernel. Being FPT is equivalent to having a kernel but not necessarily polynomial. Then, natural questions are the following.

NP-hardness results

Before proving some complexity results, we need a preliminary lemma.

Lemma 1. Let G be a graph and x a vertex of G. If there is a greedy colouring c such that x is coloured p, then, for any 1 ≤ i ≤ p, there is a greedy colouring such that x is coloured i. Proof. For 1 ≤ i ≤ p, let S i be the set of vertices coloured i by c. Then for any 1 ≤ i ≤ p, (S p-i+1 , . . . , S p ) is a greedy i-colouring of G[ p j=p-i+1 S j ] in which x is coloured i. This partial greedy colouring of G may be extended into a greedy colouring of G in which x is coloured i. ⊓ ⊔ We now show that no Brooks type theorem exists for the Grundy number.

Theorem 1. It is NP-complete to decide if a bipartite graph G satisfies Γ (G) = ∆(G) + 1.
Proof. The problem is trivially in NP. To show that it is also NP-complete, we present a reduction from 3-edge-colourability of 3-regular graphs, which is known to be NP-complete [START_REF] Holyer | The NP-completeness of edge-colouring[END_REF].

Let G be a 3-regular graph with t -3 vertices. Set V (G) = {v 4 , v 5 , . . . , v t } and E(G) = {e 1 , . . . , e p }. Let I be the vertex-edge incidence graph of G, that is the bipartite graph with vertex set V (I) = V (G) ∪ E(G) in which an edge of G is adjacent to its two endvertices. Also, let M p,p denote the graph obtained from the complete bipartite graph K p,p by removing a perfect matching. It can be easily checked that Γ (M p,p ) = p. We construct from I a new bipartite graph H as follows. For each vertex e i ∈ E(G), we add a copy M 3,3 (e i ) of M 3,3 and identify one of its vertices with e i . We add a new vertex r adjacent to all the vertices of V (G). We add copies M r 1,1 , M r 2,2 , M r 3,3 , M r t+1,t+1 of K 1 , K 2 , M 3,3 , M t+1,t+1 and we choose arbitrary vertices v 1 , v 2 , v 3 , v t+1 respectively from each copy and add the edges v 1 r, v 2 r, v 3 r, v t+1 r. Finally, for every 4 ≤ i ≤ t, we do the following: for every 4 ≤ j ≤ i -1, we add a copy M i j,j of M j,j , choose an arbitrary vertex v i j of it and add the edge v i v i j . See Figure 1. Observe that:

(i) d H (r) = t + 1, (ii) d H (v i ) = 1 + (i -1) = i , for 4 ≤ i ≤ t + 1.
(iii) d H (e j ) = 4, for 1 ≤ j ≤ p, since e i has two neighbours in I and two in M 3,3 (e i ). (iv) d H (v i j ) = j, for 5 ≤ i ≤ t and 4 ≤ j < i, since a vertex in M i j,j has degree j -1 and v i j is adjacent to v i . (v) ∆(H) = t + 1 and the only vertices with degree t + 1 are r and v t+1 .

Let us show that Γ (H) = ∆(H) + 1 = t + 2 if and only if G is 3-edgecolourable.

Assume first G has a 3-edge-colouring φ. By Lemma 1, for every 1 ≤ i ≤ p, there is a greedy colouring of the copy of M 3,3 (e i ) associated with e i where e i is coloured φ(e i ). Then in I every vertex in V (G) has one neighbour of each colour in {1, 2, 3}. There is a greedy colouring of M i j,j , 4 ≤ j < i ≤ t so that v i j is coloured j.

Then we greedily extend the union of these colourings to

v i , 4 ≤ i ≤ t, so that v i is coloured i. We also greedily colour M r 1,1 , M r 2,2 , M r 3,3 , M r t+1,t+1
in such a way that r has one neighbour coloured i, i ∈ {1, 2, 3, t + 1}. Finally, r has one neighbour of each colour j, 1 ≤ j ≤ t + 1. So we colour it with t + 2.

Hence Γ (H) ≥ t + 2 and so

Γ (H) = t + 2 because ∆(H) = t + 1. Let us now show that if Γ (H) = t + 2 then G is 3-edge-colourable. Assume that c is a greedy (t + 2)-colouring of H. r M 1,1 M 3,3 M 2,2 M t+1,t+1 M 3,3 (e 3 ) M 3,3 (e 2 ) M 3,3 (e 1 ) M 3,3 (ep) v 5 M 5 4,4 M 6 4,4 M 6 5,5 v 4 vt M t 4,4 M t 5,5 M t t-2,t-2 M t t-1,t-1 v 6 V (G) E(G)
Fig. 1. The graph H of the reduction in Theorem 1

Claim 1 {c(r), c(v t+1 )} ⊆{t + 1, t + 2}
Proof. Let u be a vertex such that c(u) = t+2. Then, u must have one neighbour coloured with each of the other t + 1 colours and then d(u) ≥ t + 1. Hence, by Observation (v), u is either r or v t+1 . Case 1: u = r. Then, c(v t+1 ) = t + 1, since the only neigbours of r with degree at least t are v t and v t+1 , d(v t ) = t, and v t is adjacent to r which is already coloured t + 2. Case 2: u = v t+1 . The only neighbour of v t+1 that could be coloured t + 1 is r, since all its neighbours in M r t+1,t+1 have degree t and are adjacent to

v t+1 which is coloured t + 2. ⊓ ⊔ Claim 2 For 1 ≤ i ≤ t, c(v i ) = i. Proof. By Claim 1, {c(r), c(v t+1 )} ⊆ {t + 1, t + 2}. Since d H (r) = t + 1, r has one neighbour coloured i, for each 1 ≤ i ≤ t.
A neighbour of r which is coloured t must have degree at least t. So, by Observation (ii), it must be v t . And so on, by induction, we show that c(v i ) = i, for 1 ≤ i ≤ t. ⊓ ⊔ We now prove that c induces a proper 3-edge-colouring of G. Consider vertex v i , 4 ≤ i ≤ t. By Claim 2, it is coloured i, and by Observation(ii) it has degree equal to i + 1. Since it is adjacent to r, which by Claim 1 has a colour greater than i, there are only i -1 vertices remaining for the other i -1 colours. So, v i has exactly one neighbour coloured j, for each 1 ≤ j ≤ i -1. Hence the three edges incident to v i in G, which are adjacent to v i in I, have different colours. ⊓ ⊔ As a corollary to Theorem 1, it is NP-hard to compute the Grundy number of a bipartite graph.

Corollary 1. Given a bipartite graph G and an integer

k, it is NP-complete to decide if Γ (G) ≥ k.
Theorem 1 also implies the following.

Corollary 2. Let k ≥ 0 be a fixed integer. It is NP-complete to decide if a bipartite graph G satisfies Γ (G) ≥ ∆(G) + 1 -k.
Proof. We present a reduction from the problem of deciding if Γ (G) = ∆(G) + 1 for a bipartite graph G, that we just proved to be NP-complete. Let G be a graph of maximum degree ∆ and H the disjoint union of G and the star S ∆+k+1 on

∆ + k + 1 vertices (S ∆+k+1 has ∆ + k edges incident to a vertex). Then ∆(H) = ∆ + k and Γ (G) = Γ (H) because Γ (S ∆+k+1 ) = 2. Hence Γ (H) ≥ ∆(H) + 1 -k if and only if Γ (G) = ∆(G) + 1. ⊓ ⊔

Dual of Greedy Colouring

The aim of this section is to prove the following theorem which shows that Dual of Greedy Colouring is FPT.

Theorem 2. Dual of Greedy Colouring can be solved in time

O (2k) 2k • |E| + 2 2k k 3k+5/2 .
A vertex cover in a graph G is a set C ⊆ V (G) such that for every e ∈ E(G), at least one of the endvertices of e is in C. A vertex cover is said to be minimal if there is no vertex cover C ′ ⊂ C. The complement of a graph G is the graph G with the same vertex set and such that uv ∈ E(G) if and only if uv / ∈ E(G). The proof of Theorem 2 may be outlined as follows. We first show that a graph G = (V, E) has Grundy number at least |V |k if and only if its complement has a vertex cover with certain properties and in particular size at most 2k. We then give an algorithm in O k 2k • |E| + k 3k+5/2 that decides if a given minimal vertex cover of G is contained in a vertex cover having such properties.

There are at most 2 2k minimal vertex covers of size at most 2k and we can enumerate them in time O 2 2k • |V | using a search tree (see for example Section 8.2 of [START_REF] Niedermeier | Invitation to Fixed-Parameter Algorithms[END_REF]). Hence applying the above-mentioned algorithm for each minimal vertex cover yields an algorithm in time O (2k) 2k • |E| + 2 2k k 3k+5/2 for Dual of Greedy Colouring.

P1: |C| -k ≤ k ′ ≤ k; P2: |C i | ≥ 2, for every 1 ≤ i ≤ k ′ ; P3: For each v ∈ V \C and for every 1 ≤ i ≤ k ′ , there is u ∈ C i such that uv ∈ E. Proof. (⇒) Assume that Γ (G) ≥ |V | -k and consider a greedy Γ (G)-colouring c.
Let C be the set of vertices that are in a colour class with more than one vertex. Then V \C is the set of vertices that are alone in their colour classes. Let u and v be two vertices in V \ C. Without loss of generality we may assume that c(u) > c(v). Then, as c is a greedy colouring, u has a neighbour coloured c(v), which must be v. So uv ∈ E. Hence V \C is clique in G and so an independent set in G. Consequently, C is a vertex cover in G.

Let c ′ be the greedy colouring

(C 1 , C 2 , . . . , C k ′ ) of G[C] induced by c. Then, |C i | ≥ 2, for every 1 ≤ i ≤ k ′ , so |C| ≥ 2k ′ . By definition of C, we have Γ (G) = |V |-|C|+k ′ ≤ |V |-k ′ . Since Γ (G) ≥ |V |-k, we obtain k ≥ k ′ ≥ |C|-k.
Finally, let v ∈ V \C and 1 ≤ i ≤ k ′ . If the colour of the vertices of C i in c is smaller than c(v), then v is adjacent to at least one vertex of C i because c is greedy. If not then every vertex of C i is adjacent to v because it is the sole vertex coloured c(v). In both cases, v is adjacent to at least one vertex in C i , so c ′ also has Property P3.

(⇐) Let C be a vertex cover of G such that there is a greedy colouring

c ′ = C 1 , C 2 , . . . , C k ′ of G[C]
having Properties P1, P2 and P3. One can extend c ′ to the entire graph G by assigning |V | -|C| distinct colours to the vertices of V \C. As a consequence of P3 and the fact that V \C is an independent set in G and therefore a clique in G, the obtained colouring is greedy. Because of P1, it uses

k ′ + |V | -|C| ≥ (|C| -k) + |V | -|C| = |V | -k colours. ⊓ ⊔ Let C be a vertex cover of G. A greedy colouring (C 1 , C 2 , . . . , C k ′ ) of G[C]
having the Properties P1, P2 and P3 of Lemma 2 is said to be good. C is suitable if G[C] has a good greedy colouring. Observe that Property P1 implies that a suitable vertex cover has cardinality at most 2k. If c is a good colouring of C min then we are done. So we may assume that it is not. We say that a colour class S i is defective with respect to a colouring s = (S 1 , . . . , S l ) of S ⊆ V if at least one of the following holds:

Proposition 1. Let C be a suitable vertex cover of G, (C 1 , C 2 , . . . , C k ′ ) a good greedy colouring of G[C] and C min ⊆ C a minimal vertex cover. Then for all 1 ≤ i ≤ k ′ , |C i \ C min | ≤ 1. Proof. Each colour class C i , 1 ≤ i ≤ k ′ , is an independent set of size at least 2 in G. So it is a clique of size at least 2 in G. Since C min is a vertex cover in G, |C i ∩ C min | ≥ |C i | -1, so |C i \ C min | ≤ 1. ⊓ ⊔ Lemma 3. Let k be an integer, G = (V,
(i) |S i | < 2;
(ii) For some j > i, there is v ∈ S j with no neighbour in S i ; (iii) There is v ∈ V \ S such that v has no neighbours in S i .

Let S i be a defective colour class with respect to s. An i-candidate with respect to s is a vertex v ∈ V \ l j=1 S j such that S i ∪ {v} is an independent set which is not defective with respect to the colouring (S 1 , . . . , S i-1 , S i ∪ {v}, S i+1 , . . . , S l ). We denote by X s (j) the set of j-candidates with respect to s and D s the set of defective colour classes with respect to s. If |X s (j)| ≥ k, we say that j is a colour class of type 1. Otherwise, we say that it is of type 2. It is easy to see that the set of defective colour classes of c and their candidates can be computed in time O(|E|).

Clearly, if c can be extended into a good colouring, it means that we can place candidates to some of its colour classes and obtain a colouring without defective colour classes. Because of Proposition 1, we are only allowed to place at most one vertex in each colour class. As we will show later, the only defective colour classes that may not receive a candidate in the extension of c to a good colouring are those of type 2.

Claim 3 Let C ⊇ C min , s be a k ′ -colouring of C, i one of its defective colour classes and v an i-candidate. Let s ′ be the extension of s where we place v in colour class i. Then, for every colour class j = i, X s ′ (j) = X s (j)\{v}.

Proof. First, assume that j is not defective in s. If it does become defective in s ′ it is due to condition (ii), since it cannot satisfy (i) or (iii) after the insertion of v in colour i. But then, since j does not satisfy (ii) in s, v is the only vertex in i that may have no neighbours coloured j, which implies that j satisfies condition (iii) in s, a contradiction. Now assume that j is defective in s. We first prove that X s (j)\{v}⊆ X s ′ (j). In this case, again we have that (i) and (iii) remain unchanged after the insertion of v, in the sense that if a vertex different from v is a candidate for j in s because of one of these conditions, the same will happen in s ′ . Regarding condition (iii), the only thing that may change in s ′ is that v is now one of the vertices with no neighbours in j. Since v is not in C min , it is adjacent to every j-candidate. Then, every vertex distinct from v that was a candidate for j in s remains a candidate for j in s ′ .

The converse, that is that every vertex in X s ′ (j) is also in X s (j)\{v}, is trivial. ⊓ ⊔ In particular, Claim 3 shows that the insertion of a candidate in a defective colour classes does not create a new defective colour class. Claim 4 Let s = (S 1 , . . . , S k ′ ) be a k ′ -colouring of C min and assume it can be extended into a good colouring s ′ = (S ′ 1 , . . . , S ′ k ′ ) of a suitable vertex cover. If j is a defective colour class in s and |S ′ j \S j | = 0, then j is of type 2 in s. Moreover, j is defective only because of (iii).

Proof. Let j be such that S ′ j = S j . If j satisfies (i) then there is only one vertex coloured j in s ′ , and thus s ′ cannot be a good colouring, a contradiction. If j satisfies (ii) then there is a vertex v coloured j ′ > j with no neighbours in S j . Since no vertices were added to S j in s ′ , vertex v also has no neighbours coloured j in s ′ , a contradiction. Hence j can be defective only because of condition (iii). But then, if |X s (j)| ≥ k, as we add at most one vertex to each colour class when extending s to s ′ , at least one vertex in X s (j) is not in any colour class of s ′ . Hence, there is a vertex that is not coloured in s ′ and has no neighbours with colour j, which implies that j is a defective colour class in s ′ , a contradiction. ⊓ ⊔ In order to determine if c can be properly extended, in a first step we consider all possible extensions of the type 2 colour classes. For such a colour class of type 2, we can choose to add to it either one of its candidates or none. By Claim 4 this later case is possible if the colour class satisfies only (iii). There are k 1 defective colour classes of type 2, where k 1 ≤ k. Moreover each of these colour classes has k 2 candidates with k 2 < k, and so has k 2 + 1 possible ways of extension: adding one of the k 2 candidates or adding none. Hence, we can enumerate all the possible extensions of the type 2 colour classes in time O(k k2+1 1 ) = O(k k ). In the second step, for each possible extension, we check if the type 1 colour classes could be extended in order to obtain a good greedy colouring.

Let c ′ be one possible extension of c as considered in the last paragraph. If a colour class S i of type 2 has not been extended, it may still be defective. If it is defective because it satisfies (i) or (ii), then it will remain defective after the second step in which we add some candidate to colour classes of type 1. Hence, we can stop, it will never lead to a good colouring. If it is defective because it satisfies (iii) (and only (iii)) then all the vertices v ∈ V \ l j=1 S j such that v has no neighbours in S i must be placed into some type 1 colour class in any extension to a good colouring. In particular, they need to be candidates of at least one colour class of type 1. We call such vertices v necessary candidates.

Let D 1 ⊆ D c ′ be the set of defective colour classes in c ′ that are of type 1 in c. Also let N be the set of necessary candidates in c ′ and C the vertex cover given by the vertices coloured in c ′ . Remember that a suitable vertex cover C must satisfy |C|k ≤ k ′ , and so if |C| + |D 1 |k > k ′ there is no way of properly extending c ′ , since by Claim 4 we need to place one candidate in each of the |D 1 | defective colour classes of type 1. The number of colour classes in c is at most k, and after a candidate is placed in a defective colour class, the colour class is no longer defective. So, since the type 1 colour classes have at least k candidates in c and because of Claim 3, there are at least |D c ′ | candidates for each of the |D 1 | defective colour classes of type 1 in c. As a consequence, there are enough candidates to place in each colour class in D 1 . But we also have to ensure that every necessary candidate is placed in a defective colour class. This is equivalent to finding a matching in the bipartite graph H with vertex set V (H) = D 1 ∪ N and with edge set

E(H) ={(i ∈ D 1 , v ∈ N ) | vertex v is an i-candidate} such that every vertex in N is saturated. This can be done in time O (|V (H)| + |E(H)|) |V (H)| = O(k 5/2
) by the algorithm of Hopcroft and Karp [START_REF] Hopcroft | An O(n 5/2 ) algorithm for maximum matchings in bipartite graphs[END_REF].

If such a matching does not exist, then we cannot properly extend c ′ by adding candidates to the vertices in D 1 , and so we may reject c ′ . If such a matching exists, since each type 1 colour class has more than |D 1 | candidates, we can greedily extend c ′ to a good colouring.

Hence one can check in time O(|E| + k k+5/2 ) if a proper colouring of G[C min ] can be extended into a good greedy colouring of G. ⊓ ⊔

We are now able to prove Theorem 2.

Proof (of Theorem 2).

Let G be an instance of the problem. To answer the question, we enumerate all minimal vertex covers of G, and check, for each one, if it is contained in a suitable vertex cover. To enumerate all minimal vertex covers takes time O(2 2k ). For each of these at most 2 2k minimal vertex covers, we check if it is contained in a suitable vertex cover. By Lemma 5, it can be done in

O k 2k • |E| + k 3k+5/2 . Hence the total running time is O (2k) 2k • |E| + 2 2k k 3k+5/2 . ⊓ ⊔

Dual of b-Colouring

In this section, we show that Dual of b-colouring is FPT.

Theorem 3. Dual of b-Colouring can be solved in time O 2 2k 3 k k 2k (k + 1)!|V (G)| .
The proof is very similar to the one of previous section. We first state a lemma analogous to Lemma 2. Its proof is so similar to the one of Lemma 2 that we omit it here.

P1: |C| -k ≤ k ′ ≤ k; P2: |C i | ≥ 2, for every 1 ≤ i ≤ k ′ ; P3: For every 1 ≤ i ≤ k ′ there is a b-vertex v i ∈ C i such that uv i ∈ E for all u ∈ V \C.
Let C be a vertex cover of G. We say that a b-colouring (C

≤ i ≤ k ′ , |C i \ C min | ≤ 1.
Then in order to determine if χ b (G) ≥ |V |-k one may enumerate all minimal vertex covers of G with size at most 2k and verify, for each such vertex cover, if it is suitable or if it may be extended to a suitable vertex cover.

≤ n + k ′ k ′ k ′ ≤ 1 + n k ′ k ′ . As f (x) = 1 + n x
x is an increasing function, we get that 1

+ n k ′ k ′ ≤ 1 + n k k ≤ 1 + 2k k k = 3 k .
For all i such that C i ∩ B = ∅, let F i be the set of vertices of V \C min which are not adjacent to the vertex b i of C i ∩ B. In any extension of c to a good b-colouring highlighting B, all the vertices in F i are to be moved to one of the colour classes because of (P3). The vertices of F = {i|bi =∅} F i are called forced vertices. If |F | > k ′ , c cannot be extended to a good b-colouring because at most one vertex of V \ C min may be added to each colour by Proposition 2. Hence we consider the case when |F | ≤ k ′ . We enumerate all possible ways of moving the forced vertices into different colour classes, every forced vertex v being moved to a colour class C such that {v} ∪ C is stable. There are at most k ′ ! ≤ k! such possibilities.

Let c * be one of the so obtained colourings of A colour class S i is defective with respect to a colouring s = (S 1 , . . . , S l ) of S ⊆ V and a set B ⊂ S if at least one of the following holds:

C * = C ∪ F . If a vertex v is moved to a colour class C i such that C i ∩ B = ∅,
(i) B ∩ S i = ∅; (ii) |S i | < 2;
(iii) There is a vertex b ∈ B \ S i with no neighbour in S i ; Let S i be a defective colour class with respect to (s, B). An i-candidate with respect to (s, B) is a vertex v ∈ V \ S such that S i ∪ {v} is an independent set which is not defective with respect to (S 1 , . . . , S i-1 , S i ∪ {v}, S i+1 , . . . , S l ), B i ) where B i = B if B ∩ S i = ∅ and B i = B ∪ {v} otherwise. We denote by X s,B (i) the set of i-candidates with respect to (s, B) and D s,B the set of defective colour classes with respect to (s, B).

Claim 5 Let C ⊃ C * , s be a k ′ -colouring of C, B a subset of S with at most one vertex in each colour class, i a defective colour class with respect to (s, B) and v an i-candidate. Let s ′ be the extension of s where we place v in colour class i. Then, for every colour class j = i, X s ′ ,Bi (j) = X s,B (j)\{v}.

Proof. If j is not defective with respect to (s, B), then it cannot become defective with repect to (s ′ , B i ), since the insertion of v in colour i cannot cause j to satisfy one of the conditions (i), (ii) or (iii).

Then, we assume that j is defective in s. To see that X s,B (j)\{v}⊆ X s ′ ,Bi (j), we have again that (i) (ii) and (iii) remain unchanged after the insertion of v, in the sense that if a vertex different from v is a j-candidate with respect to (s, B) because of one of these conditions, the same will happen with respect to (s ′ , B i ).

Finally, it follows directly from the definition that every vertex in X s ′ ,Bi (j) is also in X s,B (j)\{v}. ⊓ ⊔ In particular, Claim 3 shows that the insertion of a candidate in a defective colour class does not create a new defective colour class. Let G be an instance of the problem. To answer the question, we enumerate all minimal vertex covers of G, and check, for each one, if it is contained in a suitable vertex cover. To enumerate all minimal vertex covers takes time O(2 2k ). For each of these at most 2 2k minimal vertex covers, we check if it is contained in a suitable vertex cover. By Lemma 5, it can be done in time O

Problem 1 .

 1 Does Dual of Greedy Colouring have a polynomial kernel? Problem 2. Does Dual of b-Colouring have a polynomial kernel?

Lemma 2 .

 2 Let G = (V, E) be a graph and k ≥ 0 an integer. Then, Γ (G) ≥ |V |k if and only if there is a vertex cover C of G such that G[C] admits a greedy colouring (C 1 , C 2 , . . . , C k ′ ) with the following properties:

Lemma 4 .

 4 Let G = (V, E) be a graph and k ≥ 0 an integer. Then, χ b (G) ≥ |V |k if and only if there is a vertex cover C of G such that G[C] admits a b-colouring (C 1 , C 2 , . . . , C k ′ ) with the following properties:

Lemma 5 .

 5 Let k be an integer, G = (V, E) a graph and C min a minimal vertex cover of G of size at most 2k. It can be determined in timeO 3 k k 2k (k + 1)!|V (G)| if C min is contained in a suitable vertex cover C.Proof. In order to determine if C min is contained in a suitable vertex cover, we first enumerate all possible proper colourings of G[C min ] with k ′ colours, |C min |k ≤ k ′ ≤ k. For each of them, we then check in time O 3 k (k + 1)!|V (G)| if it can be extended into a good b-colouring of a suitable vertex cover. There are at most k |Cmin| ≤ k 2k proper colourings of C min with at most k colours and they can be enumerated in time O k 2k . Hence our algorithm is O 3 k k 2k (k + 1)!|V (G)| . Let us now detail an algorithm that, given a proper colouring c = (C 1 , C 2 , . . . , C k ′ ) of G[C min ], decides if it can be extended into a good b-colouring of a suitable vertex cover in FPT time. If c is a good b-colouring of C min then we are done. Otherwise, we need to check if we can extend c to vertices in V \C min and obtain a good b-colouring. By Proposition 2, for such an extension at most one vertex of V \ C min is added in each colour class. In order to check if c can be extended to a good b-colouring, we must guess for each colour which vertex will be a b-vertex in such an extension. For each colour i such a b-vertex may either already be in C i or be in V \ C min . Hence we try all possible sets B ⊂ C min such that |B ∩ C i | ≤ 1 for all 1 ≤ i ≤ k ′ and check if one can extend c into a good b-colouring highlighting B, such that all vertices of B are b-vertices. The number of possible choices of B is given by p = k ′ i=1 (|C i | + 1). Since

  k ′ i=1 |C i | = n and p is maximized when the |C i | are all equal, we have p

  then it must be the b-vertex of this class because at most one vertex can be added to each colour class. Hence we have to look for a good b-colouring extending c * and highlighting B * the set containing all the vertices of B and the forced vertices moved to colour classes not intersecting B.

Claim 6

 6 Let s = (S 1 , . . . , S k ′ ), be a k ′ -colouring of C * and assume it can be extended into a good b-colouring s ′ = (S ′ 1 , . . . ,S ′ k ′ ) highlighting B * . If j is a defective colour class in s then |S ′ j \S j | = 1. Proof. If j satisfies (i) for (s, B * ), then S ′ j contains the b-vertex of colour j which is not in S j . If j satisfies (ii), then since |S ′ j | ≥ 2 by Property P2, |S ′ j | > |S j |. If j satisfies (iii) then a vertex b ∈ B \ S j has no neighbours in S j . But S ′ j contains a neighbour of b since it highlghts B. Again |S ′ j | > |S j |. In all cases S ′ j has more vertices than S j . So by Proposition 2, |S ′ j \S j | = 1. ⊓ ⊔ Recall that if C ′ is suitable it must satisfy |C ′ |k ≤ k ′ , and so if |C * | + |D c * ,B * |k > k ′there is no way extend c * into a good b-colouring. The number of colour classes in c * is at most k ′ , and after a candidate is placed in a defective colour class, the colour class is no longer defective. As a consequence, to decide if c * can be extended to a good b-colouring highlighting B * is equivalent to find a matching in the bipartite graph H with vertex setV (H) = D c * ,B * ∪{v ∈ X c * ,B * (i), 1 ≤ i ≤ k ′ } and with edge set E(H) ={(i ∈ D c * ,B * , v ∈ V \C * ) | vertex v is an i-candidate} such that every vertex in D c * ,B * is saturated. This can be done in time O (|V (H)| + |E(H)|) |V (H)| = O (k|V (G)|), since |V (H)| = O (|V (G)|) and |E(H)| = O (k|V (H)|) = O (k|V (G)|)and because of the algorithm of Hopcroft and Karp [10]. If such a matching does not exist, then we cannot properly extend c * by adding candidates to the colour classes, and we must reject c. If such a matching exists, we can move each saturated candidate to the matched defective colour class to obtain a good b-colouring highlighting B * . Hence one can check in time O 3 k (k + 1)!|V (G)| if a proper colouring of G[C min ] can be extended into a good b-colouring of G. ⊓ ⊔ Proof (of Theorem 3).

  3 k k 2k (k + 1)!|V (G)| . Hence the total running time is O 2 2k 3 k k 2k (k + 1)!|V (G)| . ⊓ ⊔

  E) a graph and C min a minimal vertex cover of G of size at most 2k. It can be determined in time O k 2k • |E| + k 3k+5/2 if C min is contained in a suitable vertex cover C. Proof. In order to determine if C min is contained in a suitable vertex cover, we enumerate all possible proper colourings of G[C min ] with k ′ colours, |C min |-k ≤ k ′ ≤ k. For each of them, we then check in time O(|E| + k k+5/2 ) if it can be extended into a good greedy colouring of a suitable vertex cover. There are at most k |Cmin| ≤ k 2k proper colourings of C min with at most k colours and they can be enumerated in time O(k 2k ). Hence the running time of our algorithm is O k 2k • |E| + k 3k+5/2 . Let us now detail an algorithm that, given a proper colouring c = (C 1 , C 2 , . . . , C k ′ ) of G[C min ], decides if it can be extended into a good greedy colouring of a suitable vertex cover in time O(|E| + k k+5/2 ). By Proposition 1, for such an extension at most one vertex of V \ C min is added in each colour class.

  1 , C 2 , . . . , C k ′ ) of G[C] having the Properties P1, P2 and P3 of Lemma 4 is good. C is suitable if G[C] has a good b-colouring. Property P1 implies that a suitable vertex cover has cardinality at most 2k. An analog of Proposition 1 can be easily proved. Proposition 2. Let C be a suitable vertex cover of G, (C 1 , C 2 , . . . , C k ′ ) a good bcolouring of G[C] and C min ⊆ C a minimal vertex cover. Then for all 1

⋆ Partially supported by ANR Blanc AGAPE. ⋆⋆ Partially supported by CAPES/Brazil and ANR Blanc AGAPE.


Frédéric Havet
email: fhavet@sophia.inria.fr.

Cláudia Linhares Sales

Leonardo Sampaio
email: leonardo.sampaiorocha@sophia.inria.fr.

b-coloring of tight graphs *

Keywords: Graph coloring, b-coloring, precoloring extension, tight graphs

 and show its relation with the b-chromatic number of tight graphs.

Introduction

A k-coloring of a graph G = (V, E) is a function c : V → {1, 2, ..., k}, such that c(u) = c(v) for all uv ∈ E(G). The color class c i is the subset of vertices of G that are assigned to color i. The chromatic number of G, denoted χ(G), is the least integer k such that G admits a k-coloring. Given a k-coloring c, a vertex v is a b-vertex of color i, if c(v) = i and v has at least one neighbor in every color class c j , j = i. A coloring of G is a b-coloring if every color class has a b-vertex. The b-chromatic number of a graph G, denoted χ b (G), is the largest integer k such that G admits a b-coloring with k colors. These concepts were first defined in [START_REF] Irving | The b-chromatic number of a graph[END_REF]. In that paper, Irving and Manlove proved that the problem of determining the b-chromatic number of a graph is NP-Hard. In fact, it was shown in [START_REF] Kratochvil | On the b-chromatic number of graphs[END_REF] that deciding whether a graph admits a b-coloring with a given number of colors is an NP-complete problem, even for connected bipartite graphs. The following upper bound for the b-chromatic number of a graph, presented in [START_REF] Irving | The b-chromatic number of a graph[END_REF], has been proved to be very useful. If G admits a b-coloring with m colors, then G must have at least m vertices with degree at least m -1 (since each color class has one b-vertex). The m-degree of a graph G, denoted by m(G), is the largest integer m such that G has m vertices of degree at least m -1. It is easy to see that χ b (G) ≤ m(G) for every graph G. A vertex of G with degree at least m(G) is called a dense vertex. The preceding upper bound leads us to the definition of a class of graphs which are tight with respect to the number and degree of their dense vertices:

Definition 1 (tight graph) A graph G is tight if it has exactly m(G) dense vertices, each of which has degree m(G) -1.
In this paper, we mainly investigate the following decision problem:

Tight b-Chromatic Problem Instance: A tight graph G. Question: Does χ b (G) equals m(G)?
A direct consequence of the NP-completeness result shown in [START_REF] Kratochvil | On the b-chromatic number of graphs[END_REF] is the following:

Theorem 2 The Tight b-Chromatic Problem is NP-complete for connected bipartite graphs.

For any positive k, P k denotes a path with k vertices. A graph G is P 4sparse if every set of five vertices of G induces at most one P 4 . Bonomo et al. [START_REF] Bonomo | On the b-coloring of cographs and P 4 -sparse graphs[END_REF] proved that the b-chromatic number of P 4 -sparse graphs can be determined in polynomial time. They asked if this result could be extended to distancehereditary graphs, that are graphs in which every induced path is a shortest path. We answer in the negative to this question by showing the following stronger result (Theorem 3). The Tight b-Chromatic Problem is NP-complete for chordal distance-hereditary graphs. We recall that a graph is chordal if it does not contain any induced cycle of size greater than 3.

The proof of our NP-completeness result is a reduction from 3-edgecolorability. We reduce an instance of this problem to a graph which is slightly more than a split graph, i.e. a graph whose vertex set may be partitioned into a clique and an independent set. Hence a natural question is to ask about the complexity of finding the b-chromatic number of a given split graph. We show in Theorem 5 that it can be solved in polynomial time.

In Section 3, we introduce the b-closure G * of a graph G. We show that for a tight graph G, χ b (G) = m(G) if and only if χ(G * ) = m(G). Hence if one can determine the chromatic number of the closure in polynomial time, one can also solve the Tight b-Chromatic Problem in polynomial time. We show that it is the case for (tight) complement of bipartite graphs. Indeed, we prove that the closures of such graphs are also complements of bipartite graphs and the chromatic number of the complement of a bipartite graph can be determined in polynomial time. This was unknown since the characterization of complements of bipartite graphs with χ b (G) = k given by [START_REF] Kouider | Bounds for the b-chromatic number of some families of graphs[END_REF] does not lead to a polynomial algorithm for determining their b-chromatic number.

Moreover, we introduce the definition of pivoted tight graph and use this definition to give a sufficient condition for a tight graph to satisfy χ b (G) < m(G).

The method of computing the b-closure of a graph and then the chromatic number of it does not yield polynomial-time algorithms to solve the Tight b-Chromatic Problem for all classes of tight graphs. However, for some of them, we show in Section 4, that the Tight b-Chromatic Problem may be solved in polynomial time using a slight modification of the closure, the partial closure. It is the case for block graphs and P 4 -sparse graphs. It is already known that deciding if χ b (G) = m(G) is polynomial time solvable for P 4 -sparse graphs [START_REF] Bonomo | On the b-coloring of cographs and P 4 -sparse graphs[END_REF]. However, our linear-time algorithm for tight P 4 -sparse graphs is faster than the O(|V | 3 ) algorithm of [START_REF] Bonomo | On the b-coloring of cographs and P 4 -sparse graphs[END_REF]. It is also interesting to see how our general method can be used to solve these problems.

Chordal graphs

Theorem 3 The Tight b-Chromatic Problem is NP-complete for chordal distance-hereditary graphs.

Proof. The problem belongs to NP since a b-coloring with m(G) colors is a certificate. To show that it is also NP-complete, we present a reduction from 3-edge-colorability of 3-regular graphs, which is known to be NPcomplete [START_REF] Holyer | The NP-completeness of edge-coloring[END_REF]. Let G be a 3-regular graph with n vertices. Set

V (G) = {v 1 , v 2 , ..., v n } and E(G) = {e 1 , . . . , e m }. Let I be the vertex-edge incidence graph of G, that is the bipartite graph with vertex set V (I) = V (G) ∪ E(G)
in which an edge of G is adjacent to its two end-vertices. We construct from I a new graph H as follows. First, we add an edge between every pair of vertices in V (G) and then, we add three disjoint copies of K 1,n+2 . One can easily see that

d H (v) = n -1 + 3 = n + 2, for v ∈ V (G), and that d H (u) = 2, for u ∈ E(G).
Moreover, each copy of K 1,n+2 has exactly one vertex with degree equal to n+2. Consequently, m(H) = n + 3 and H is tight. In H, V (G) is a clique and E(G) is an independent set, so H[A ∪ B] is a split graph, and so it is chordal. As the disjoint copies of K 1,n+2 are themselves chordal graphs, we get that the entire graph H is chordal. One can easily check that H is also distance-hereditary. We now prove that G admits a 3-edge-coloring if and only if

χ b (H) = m(H) = n+3.
Let c be a 3-edge-coloring of E(G) that uses colors {1, 2, 3}. We shall construct a b-coloring c ′ of H with n + 2 colors. Let c ′ (u) = c(u), for u ∈ E(G), and c ′ (v i ) = i + 3, for 1 ≤ i ≤ n. Note that in this partial coloring, the vertices in V (G) are b-vertices of their respective colors. To obtain the remaining b-vertices, one just have to appropriately color the copies of K 1,n+2 , which can be easily done. Then, c ′ is a b-coloring of H with m(H) = n + 3 colors. Now, let c ′ be a b-coloring of H that uses n + 3 colors. Since V (G) is a clique, we may assume that c ′ (v i ) = i + 3, for 1 ≤ i ≤ n. Since there are only n + 3 vertices of degree n + 2 in H, each vertex in V (G) is an b-vertex. But then, since every vertex in V (G) has degree exactly n + 2 in H, all its neighbors must have distinct colors. As a consequence, since no vertex in V (G) is colored with one of the colors in {1, 2, 3}, for every vertex in V (G), its 3 neighbours in E(G) are colored with distinct colors in {1, 2, 3}. This implies that G admits a 3-edge-coloring of G, and completes the proof. [START_REF] Giakoumakis | P 4 -laden graphs: a new class of brittle graphs[END_REF] (resp. extended P 4 -laden if for every set S ⊆ V of six vertices, the subgraph induced by S contains at most one induced P 4 or is a split graph (resp. a pseudo-split graph, i.e. a {C 4 , K 2 }free graph. By definition, every P 4 -laden graph is extended P 4 -laden. One can check that the graph in the reduction of Theorem 3 is P 4 -laden, so the Tight b-Chromatic Problem is NP-complete for P 4 -laden graphs.

Remark 4 A graph G = (V, E) is P 4 -laden
The class of the extended P 4 -laden graphs contains many graph classes with few induced P 4 's. In particular, it contains the class of P 4 -tidy graphs [START_REF] Giakoumakis | On P 4 -tidy graphs[END_REF] which in turn contains the ones of P 4 -lite [START_REF] Jamison | A new class of brittle graphs[END_REF], P 4 -extendible [START_REF] Jamison | On a unique tree representation for P4extendible graphs[END_REF] and P 4 -reducible graphs [START_REF] Jamison | P 4 -reducible graphs -a class of uniquely tree representable graphs[END_REF]. A graph is P 4 -tidy if for every set A inducing a P 4 there is at most one vertex x such that the subgraph induced by A∪{x} has at most one induced P 4 . Bonomo, Koch, and Velasquez [START_REF] Bonomo | On the b-coloring of P 4 -tidy graphs[END_REF] proved that the b-chromatic number of a P 4 -tidy graph can be determined in polynomial time, thus extending the result in [START_REF] Bonomo | On the b-coloring of cographs and P 4 -sparse graphs[END_REF].

The three copies of K 1,n+2 play an important role in the reduction of the proof of Theorem 3, since one can show the following

Complement of bipartite graphs

By Lemma 7, it is interesting to consider the b-closure of a tight graph G if the chromatic number of its closure can be determined in polynomial time. Indeed if so, one can decide in polynomial time if χ b (G) = m(G). We now show that it is the case if G is the complement of a bipartite graph. Computing the chromatic number of the complement G of a bipartite graph G is equivalent to compute the maximum size of a matching in this bipartite graph. Hence it can be done in O( |V (G)|•|E(G|) by the algorithm of Hopcroft and Karp [START_REF] Hopcroft | An n 5/2 algorithm for maximum matchings in bipartite graphs[END_REF] and in O(|V (G)| 2.376 ) using an approach based on the fast matrix multiplication algorithm [START_REF] Muchaand | Maximum matchings via Gaussian elimination[END_REF].

Corollary 10 Let G be a tight complement of a bipartite graph. It can be decided in O(max{

|V (G)| • |E(G)|, |V (G)| 2.376 }) if χ b (G) = m(G).

Pivoted graphs

In the study of the b-chromatic number of trees, Irving and Manlove [START_REF] Irving | The b-chromatic number of a graph[END_REF] introduced the notion of a pivoted tree, and showed that a tree T satisfies χ b (T ) < m(T ) if and only if it is pivoted. We generalize this notion and show how our generalization is related to the b-chromatic number of tight graphs.

Definition 11 (Pivoted Graph) Let G be a tight graph. We say that G is pivoted if there is a set N of non-dense vertices, with |N | = k, and a set of dense vertices D, with |D| = m(G)k + 1, satisfying:

1. For every pair u, v ∈ N , u is adjacent to v, or there is a dense vertex w that is adjacent to both u and v.

2. For every pair u ∈ N , d ∈ D, either u is adjacent to d or u and d are both adjacent to a dense vertex w (not necessarily in D).

Theorem 12 Let G be a tight graph. Then G is a pivoted graph if and only if ω(G * ) > m(G).

Proof. First, assume that G is a pivoted graph. Then Definitions 6 and 11 immediately imply that There are graphs satisfying χ(G * ) > m(G) but not ω(G * ) > m(G). Figure 1 shows a chordal non-pivoted graph G with exactly m(G) = 7 dense vertices, each of degree 6, such that χ b (G) < m(G).

N ∪ D is a clique of size m + 1 in G * . Reciprocally, assume that ω(G * ) > m. Let S ⊆ V (G * ) be a clique of size m + 1 in G * . Let N ={v ∈ S | v is not dense in G} and D ={v ∈ S | v is dense in G}. Let u, v ∈ S. If u, v ∈ D,
In contrast to what happens with pivoted graphs, where a clique of size greater than m is formed in their b-closures, the graph of Figure 1 Proof. The proof is similar to the one of Lemma 7. In this case, since we do not add edges between all the pairs of dense vertices in G * p , we need the requirement that the m(G)-coloring of G * p is such that all dense vertices have distinct colors.

By Lemma 15, one can decide in polynomial time if χ b (G) = m wherever it can be decided in polynomial time if the constrained coloring of its partial closure G * p exists. In particular, it is the case if the precoloring extension problem can be decided in polynomial time for G. We show that this is the case for block graphs and P 4 -sparse graphs.

Block graphs

The result in this subsection was obtained in cooperation with Ana Silva.

A graph G = (V, E) is a block graph if every of its blocks (maximal 2connected subgraphs) is a complete graph. For an example, see Figure 2.

Lemma 16

The partial b-closure of a block graph is chordal.

Proof. By contradiction, assume that the partial

b-closure G * p of a block graph G is not chordal. Then it has an induced cycle C = (v 1 , v 2 , ..., v k ) of length k ≥ 4. For every edge v i v i+1 of C (indices must be taken modulo k) either v i v i+1 ∈ E(G) or there is a dense vertex w i ∈ V (G) such that v i w i , w i v i+1 ∈ E(G).
In the latter case, the vertex w i is adjacent to no v j for j / ∈ {i, i + 1} in G, otherwise both v j v i and v j v i+1 would be edges of G * p and C would not be induced. Furthermore, this implies that all the existing w i 's are distinct. Let C ′ be the cycle obtained from C by replacing each edge v i v i+1 by v i w i v i+1 whenever v i v i+1 / ∈ E(G). Observe that C ′ is a cycle of G. But, since G is a block graph, the vertices of any cycle (in particular, C ′ ) form a clique in G and thus also in G * p . Hence the vertices of C form a clique in G * p , a contradiction.

Marx [START_REF] Marx | Precoloring extension on chordal graphs[END_REF] showed that the precoloring extension problem when all the C colors are used at most once is Proof. Let G be a P 4 -sparse graph. Suppose, by way of contradiction, that G * p is not P 4 -sparse. Then there is at least one induced P 4 in G * p that is not in G. Let P = (v 1 , v 2 , v 3 , v 4 ) be such a P 4 in G * p . We will show that there are 5 vertices that induces two P 4 's in G, thus getting a contradiction. By symmetry, it is enough to consider the following five cases.

Theorem 5

 5 If G is a split graph then χ b (G) = m(G). Hence, the b-chromatic number of a split graph can be determined in polynomial time.Proof. Let G be a split graph and (K, S) a partition of V (G) with K a clique and S an independent set such that |K| is maximum. Every vertex in K has degree at least |K| -1 and every vertex s in S has degree at most |K| -1 otherwise (K ∪ {s}, S \ {s}) would contradict the maximality of |K|. Hence m(G) = |K|.Coloring the vertices in K with |K| distinct colors and then extend it greedily to the vertices of S (This is possible since every vertex in S has degree smaller than |K|.) gives a b-coloring of G with m(G) = |K| colors. 3 b-closure Definition 6 (b-closure) Let G be a tight graph. The b-closure of G, denoted by G * , is the graph with vertex set V (G * ) = V (G) and edge set E(G * ) = E(G) ∪ {uv | u and v are non-adjacent dense vertices} ∪ {uv | u and v are vertices with a common dense neighbour}. The next theorem proves the relation, for a tight graph G, between the parameters χ b (G) and χ(G * ): Lemma 7 Let G be a tight graph. Then χ b (G) = m(G) if and only if χ(G * ) = m(G). Proof. Set m = m(G). Suppose that χ b (G) = m, and let c be a b-coloring of G with m colors. It is easy to see that the m dense vertices form a clique in G * and so χ(G * ) ≥ m. Let us show that c is a proper coloring for G * . Let uv / ∈ G be such that uv ∈ E(G * ). If both u and v are dense, as there are exactly m dense vertices in G, they must have distinct colors in c. Now, suppose that u or v is not a dense vertex. By the definition of G * , u and v have a common dense neighbor, say d, in G. Since all dense vertices of G have degree m -1 and c is a b-coloring, u and v must have been assigned distinct colors in c. Hence, χ(G * ) = m. Conversely, let c ′ be a proper coloring of G * with m colors. In this case, since E(G) ⊆ E(G * ), c ′ is also a proper coloring of G. It only remains to show that every color of c ′ has a b-vertex. As the dense vertices of G form a clique in G * , they have distinct colors in c ′ . Moreover, for a dense vertex d of G, we have that N G * (d) is a clique. As a consequence, d is a b-vertex. Therefore, χ b (G) = m. Since ω(G * ) > m implies that χ(G * ) > m, it follows: Corollary 8 Let G be a tight graph. If χ b (G) = m(G), then ω(G * ) = χ(G * ) = m(G).

Lemma 9

 9 The b-closure of the complement of a bipartite graph is a complement of a bipartite graph. Proof. Let G a tight complement of a bipartite graph. Let V (G) = X ∪ Y where X and Y are two disjoint cliques in G. As V (G * ) = V (G), and since E(G) ⊆ E(G * ), the sets X and Y are cliques in G * . So they also form a partition of V (G * ) into two cliques.

  there is nothing to show, since Definition 11 imposes no restrictions between dense vertices in G. If u ∈ N, v ∈ D ∪ N , we have that either uv ∈ E(G), or ud, vd ∈ E(G), for a dense vertex d ∈ V (G). So, it is easy to see that the sets N and D satisfy the requirements of Definition 11. Lemma 7 and Theorem 12 have the following corollary.Corollary 13 Let G be a tight graph. If G is a pivoted graph, then χ b (G) < m(G).Proof. As G is pivoted, Theorem 12 implies that ω(G * ) > m(G), and therefore χ(G * ) > m(G). Then, by Lemma 7, χ b (G) < m(G).

Figure 1 :

 1 Figure 1: A non-pivoted chordal graph, satisfying χ b (G) < m(G), and its bclosure G * , satisfying χ(G * ) > ω(G * ) = m(G) (the new edges between the dense vertices are dashed).

  has clique number 7, but its b-closure produces an odd hole (by the five non-dense vertices in the bigger component) which causes χ(G * ) > 7. 4 Partial b-closure Definition 14 (partial b-closure) Let G be a tight graph. The partial bclosure of G, denoted G * p , is the graph with vertex set V (G * ) = V (G) and edge set E(G * ) = E(G) ∪ {uv | u and v are vertices with a common dense neighbour}. Lemma 15 Let G * p be the partial b-closure of a graph G, and let D be the set of m(G) dense vertices of G. Then χ b (G) = m(G) if and only if G * p admits a m(G)-coloring where all the vertices in D have distinct colors.

Figure 2 :

 2 Figure 2: A block graph.

  solvable in time O(C • |V (G)| 3 ) for a chordal graph G. Hence, Corollary 17 the Tight b-Chromatic Problem can be decided in time O(m(G)|V (G)| 3 ) for tight block graphs. Remark 18 A tree is a block graph, so using the partial closure method the Tight b-Chromatic Problem for tight trees can be solved in time O(m(G)|V (G)| 3 ). However, Irving and Manlove [12] gave a linear time algorithm to compute the b-chromatic number of any tree. Hence the Tight b-Chromatic Problem can be solved in linear time for trees.

4. 2

 2 P 4 -sparse graphs Lemma 19 The partial b-closure of a P 4 -sparse graph is P 4 -sparse.

Case 1 :

 1 v 1 v 2 ∈ E(G), v 2 v 3 ∈ E(G) and v 3 v 4 / ∈ E(G).Then, v 3 and v 4 are both adjacent to a dense vertex w ∈ V (G) (by the

supported by the INRIA Equipe Associée EWIN. Partially supported by CNPq/Brazil. Partially supported by CAPES/Brazil and ANR Blanc AGAPE.

definition of the partial b-closure). Note that v 1 w / ∈ E(G) (resp. v 2 w / ∈ E(G)) otherwise v 1 v 4 ∈ E(G * p ) (resp. v 2 v 4 ∈ E(G * p )) and P would not be an induced P 4 in G * p . Hence, {v 1 , v 2 , v 3 , w, v 4 } induces a P 5 which contains two induced P 4 .

In this case, v 2 and v 3 are both adjacent to a dense vertex w ∈ V (G) (again, by the definition of the b-closure). Note that v 1 w, v 4 w / ∈ E(G), for otherwise, this would imply that

∈ E(G), the vertices v 1 and v 2 are both adjacent to a dense vertex

) and P would not be an induced P 4 in G * p . By a similar argument, v 3 and v 4 are both adjacent to a dense vertex w 2 ∈ V (G), which is not adjacent to v 1 and w 2 . Note that w 1 and w 2 are distinct since

Using arguments similar to the ones in the previous cases, we obtain that there are distinct dense vertices

Again, by similar arguments to the ones used in the previous cases, there are distinct dense vertices

, then the set {v 1 , w 1 , w 2 , w 3 , v 4 } induces a P 5 in G. Hence by symmetry, we may assume that

Babel et al. [START_REF] Babel | Efficient algorithms for graphs with few P4's[END_REF] showed that the precoloring extension problem is linear-time solvable for (q, q -4)-graphs, which are graphs where no set of at most q vertices induces more than q -4 different P 4 's. Hence, Corollary 20 The Tight b-Chromatic Problem can be decided in linear time for tight P 4 -sparse graphs.

Consequently, for tight P 4 -sparse graphs, this algorithm is faster than the O(|V | 3 ) algorithm given in [START_REF] Bonomo | On the b-coloring of cographs and P 4 -sparse graphs[END_REF], that solves the more general case where the input graph is not necessarily tight.