Mekkia Kouider
email: mekkia.kouider@lri.fr

ON QUASI-MONOTONOUS GRAPHS

A dominating coloring by k colors is a proper k coloring where every color i has a representative vertex x i adjacent to at least one vertex in each of the other classes. The b-chromatic number, b(G), of a graph G is the largest integer k such that G admits a dominating coloring by k colors.

Here we say that a graph G is quasi b-monotonous , or simply quasi-monotonous, if for every vertex

We show study the quasi-monotonicity of several classes. We show in particular that chordal graphs are not quasi-monotonous in general,whereas chordal graphs with large b-chromatic number, and (P, coP, chair, cochair)-free graphs are quasimonotonous; (P 5 , coP 5 , P )-free graphs are monotonous.Finally we give new bounds for the b-chromatic number of any vertex deleted subgraph of a chordal graph.

Introduction

All graphs considered here are simple and undirected. We denote by P n (respectively C n ) an elementary path (resp. an elementary cycle) with n vertices. Let G be a graph with a proper coloring. For any two disjoints subsets A and B, let E(A, B) be the set of edges of G with one extremity in A and the other in B. Let u i be any vertex u of color i. Let us denote by C i the class of color i. If y is a vertex of the graph G, let N i (y) be the set of neighbours of y of color i; while for any integer p non zero, N p (y) is the set of vertices at distance exactly p from y.

In a proper coloring, a vertex x i of color i is said a dominating vertex if x i adjacent to at least one vertex in each of the other classes. The vertex x i is also called a dominant. The color i is said dominating if there exists at least a vertex of color i which is dominating. A dominating coloring by k colors is a proper k coloring where every color i has a at least a dominating vertex.

The b-chromatic number, b(G), of a graph G is the largest integer k such that G admits a dominating coloring by k colors. A dominating coloring with b(G) colors will be called a b-coloring. This parameter was defined by Irving and Manlove [START_REF] Irving | The b-chromatic number of a graph[END_REF]. They proved that determining b(G) for an arbitrary graph G is an NP-complete problem.

For a given graph G, it may be easily remarked that χ(G) ≤ b(G) ≤ ∆(G) + 1. If we are limited to regular graphs, Kratochvil et al. proved in [START_REF] Kratochvil | On the b-chromatic number of graphs[END_REF] that for a d-regular graph G with at least d 4 vertices, b(G) = d + 1. Kouider and El Sahili ([4]) proved that for every regular graph of girth 5 and no induced cycle C 6 the same equality holds.

Let v be any vertex of a graph G. It is known that χ(Gv) ≤ χ(G). The function χ is said monotonous. This is not the case for the b chromatic number.

A graph G = (V, E) is called b-monotonous if b(H 1 ) ≥ b(H 2 ) for every induced subgraph H 1 of G and every subgraph H 2 of H 1 .
This was a definition of Bonomo et al.

Here we say that a graph G is quasi b-monotonous , or simply quasi-monotonous, if for every vertex

v ∈ V , b(G -v) ≤ b(G) + 1.
A chordal graph is a graph where every cycle of length at least 4 has at least one chord. A quasi-line graph is a graph where the neighborhood of every vertex has a partition into at most 2 cliques. A P 4 -sparse graph is a graph where every 5-vertex subset contains at most one induced P 4 .

It was shown by Bonomo and al.([2]) that P 4 -sparse graphs are b monotonous. On the other hand, we showed in [START_REF] Kouider | On b chromatic number of graphs, subgraphs and degrees[END_REF] that every graph of girth at least 5 is b-monotonous.

Clique-width A parameter used in complexity of graphs is the clique-width. Many problems of optimisation which are NP Hard can be solved efficiently on graphs with bounded clique-width. Some of the classes with bounded cliquewidth are defined by forbidden subgraphs on 5 vertices, among P 5 ,coP 5 , P , chair, cochair, coP (see fig. 1)( [START_REF] Brandstadt | On Variations of P 4 sparse graphs[END_REF]).

The class of (P 5 , coP 5 , cochair)-free graphs was defined, by Giakoumakis and Fouquet,as the class of semi-P 4 -sparse graphs, a superclass of P 4 -sparse graphs.The class (P 5 , coP, chair, cochair)-free deserves the name of semi P 4 -sparse.

For general graphs S.F.Raj and R.Balakrishnan proved that Theorem 1 [START_REF] Raj | Bounds for the b-chromatic number of vertex deleted subgraphs and the extremal graphs[END_REF] For every connected graph of order n ≥ 5, and for every

vertex v ∈ V (G), b(G) -(⌈n/2⌉ -2) ≤ b(G -v) ≤ b(G) + (⌊n/2⌋ -2)
The upper bound is attained.

2

Quasi-monotonous graphs

Our main results are the following.

Theorem 2 Let G = (V, E) be a graph.

1) If each vertex is contained in at most two cycles of length 4. Then G is quasi-b-monotonous.

2) If G is (P, coP, Chair, Cochair)-free, G is quasi-b-monotonous.

Corollary 1 [START_REF] Kouider | On b chromatic number of graphs, subgraphs and degrees[END_REF] Every graph of girth at least 5 is quasi-b-monotonous.

Theorem 3 Let G = (V, E) be a graph.

1) If G is (P 5 , P, Cochair)-free, G is b-monotonous.

2) If G is (P 5 , coP 5 , P )-free, G is b-monotonous.

Theorem 4 Let G = (V, E) be quasi-line-graph. Then for each vertex x, b(G- x) ≤ b(G) + 2
Theorem 5 Let G = (V, E) be a chordal graph of clique-number ω.

Then, for each vertex x of G,of degree

d(x), b(G -x) ≤ b(G) + 1 + d(x) -1 b(G -x) (1) b(G -x) ≤ b(G) + 1 + ω -1 b(G -x) -ω (2). b(G -x) ≤ b(G) + 1 + (ω -1) 3/4 (b(G) -ω) 1/2 (3)
From the preceding theorem, we deduce

Corollary 2 Let G = (V, E) be a chordal graph of clique-number ω and b- chromatic number b(G). Then, for each vertex x, b(G -x) ≤ b(G) + 1 + d(x) -1 b(G -x) ≤ b(G) + 1 + √ ω -1.
Corollary 3 Let G = (V, E) be a chordal graph of clique-number ω and bchromatic number b such that b ≥ 2ω -3.

Then G is quasi b-monotonous.

There exist chordal graphs and quasi-line graphs not b-monotonous.

Examples 1) Let k ≥ 3 be an integer .

Let ω be an even integer and 2k be a divisor of ω, furthermore we suppose ω ≥ 4.k 2 . We give an example of a chordal graph G 1 with dominating number

b = ω + ω 2k -k + 1 and not quasi-b-monotonous. The gap b(G 1 -x) -b(G 1 )
in this example is of the order of √ ω.

Consider the following graph H composed by 4 vertex-disjoint cliques

A 1 , A 2 , A 3 , A 4 such the order of A 1 (resp. of A 4 ) is ω -ω/2k. Furthermore, A 1 ∪ A 2 is a clique of order ω as well as A 4 ∪A 3 , and, A 3 ∪A 2 is a clique of order ω/k (see fig.2).Let us call H ′ the graph H -A 4 .
The graph G 1 is a graph composed by k disjoint copies of H and a copy of H ′ , and, with a vertex x, external to the copies of H and H ′ , joined to every vertex of any copy of A 1 and to every vertex of H ′ .

X H k H' H 1 A A A 1 1 1 x

Fig. 2. Chordal graph not quasi-monotonous

We observe that

d(v) ≤ ω + 1 for every vertex v of H ′ ; d(x) = k.ω + ω/2 + ω/2k; and, d(u) = ω + ω/2k -1
for every vertex u of a copy of A 2 in G 1 or every vertex of a copy of A 3 in G 1 -H ′ . The other vertices have degree at most ω. The number of vertices of degree at least ω

+ ω/2k -k -1 is ω + ω/2k + 1 (a)
The graph G 1x has a b-chromatic number equal to ω + ω/2k, the set of dominating vertices is the set of vertices of maximum degree inG 1x . We show that the graph

G 1 has a b-chromatic number equal to ω + ω/2k -k + 1. Indeed, suppose b(G 1 ) ≥ ω + ω/2k -k, so b(G 1 ) ≥ ω + 3. Given a b coloring of G, at least ω/2k -k -1 colors have a dominating vertex in H ′ ; then x is neighbour of b -1 colors,
) ≤ ω + ω/2k -k + 1. So b(G 1 -x) = b(G 1 ) + k -1. In that example, if ω = 4k 2 , then b(G 1 -x) = b(G 1 ) -1 + √ w 2 .
2) With the notations of the precedent example, we consider a graph G 2 composed by two vertex disjoint copies of H, and an external vertex x joined to each copy of A 1 . We have

|A 1 | = |A 4 | = 2ω/3 and |A 2 | = |A 3 | = ω/3. Then G 2 is a quasi-line graph and b(G 2 -x) = b(G 2 ) + 1. x H 1 H 2

Fig. 3. Quasi-line graph not monotonous

Remark: There exist chordal graphs with b-chromatic number at least 2ω.

Let ω ≥ 2, p = 5(ω -1). Let S(u) be the graph composed by 5 cliques sharing exactly one vertex u. Consider the graph H composed by an elementary path P (u 1 , ..., u p ) and a family of p graphs S(u i ) for 1 ≤ i ≤ p. It is easy to see that H is chordal and b(H) ≥ p ≥ 4ω.

Proofs

Remarks For each of our results the following remarks are valid. The proofs are by contradiction. Let x be a fixed vertex of

G. Let H = G -x. We may suppose first that q = b(H) ≥ ω + 2 otherwise we have b(H) ≤ b(G) + 1.
Suppose the b-coloring of H is not extendable to G. Then, necessarily, R1) All the colors appear in N (x). R2) x is not neighbour to q dominating vertices s of different colors, so there exists an integer r such that for every color i ≥ r + 1, N i (x) contains no dominanting vertex.

R3)Let us consider r minimum. For each i ≥ r + 1, N (N i (x)) ∩ N 2 (x) contains all the dominating vertices of some color j and no one of these dominating vertices has a neighbour of color i outside N i (x); otherwise for each y ∈ N i (x), we change the color i of the vertex y into a color missing in the neighborhood of y and we give color i to the vertex x and we obtain a b-coloring of G with q colors. Let us call I the set colors i, i ≥ r + 1.

Note that, as the coloring is proper and j > r,we get qr ≥ 2. From now we say that a set A ∈ N i (x) covers a color j if N (A)) ∩ N 2 (x) contains all the dominating vertices of some color j and no one of these dominating vertices has a neighbour of color i outside A. Note that j ∈ I necessarily.

Now we give first the proof of theorem2.

Proof of Theorem 2

Proof of the first part of the theorem2 Case 1:There exists i ≥ r + 1 such that N i (x) covers at most one color, say j

For each y ∈ N i (x), we change the color i of y into a color missing in the neighborhood of y.

We x by i. Either there remains a dominating vertex of the color j, we keep color j. Or the color j has no dominating vertex.For each vertex of color j we give a color missing in its neighborhood. In any case, we get a b coloring of G with at least q -1 colors..

Case 2:

For each i ≥ r + 1, N i (x) covers at least 2 different colors.

Let b ′ the number of colors with all dominating vertices contained in N 2 (x) and neighbours of ∪ i≥r+1 N i (x). As the coloring is proper, and qr ≥ 2, then b ′ ≥ 3 by definition of case 2; so br ≥ b ′ ≥ 3. Let S be a system of b ′ dominating vertices of the b ′ different colors.

There exist at least 2(qr) edges between ∪ i≥r+1 N i (x) and the set S, by definition of case 2.Then either there exists a vertex s 0 which sends at least 3 edges to ∪ i≥r+1 N i (x), or each vertex of S sends exactly 2 edges to ∪ i≥r+1 N i (x).

As |S| ≥ 3, there are at least 3 cycles of length 4 containing x. A contradiction to the hypothesis on G.

This ends the proof of part1 of theorem 2.

Proof of part 2 of Theorem 2

We use the proof of the first part. And we may suppose we are in case 2. For each color j, j ≥ r + 1, N j (x) covers at least 2 colors. Let i, i ≥ r + 1 be a color such that a dominating vertex x i is in N 2 (x), neighbour of u t ∈ N (x). Let us note that, by definition of the covering,x i is independent of the dominants of each color covered by N i (x).

There exists a vertex y i ∈ N i covering a color k, otherwise, there are y i and y ′ i in N i (x), x k and x ′ k dominants of the same color such that the path Q = {x k , y i , x, y ′ i , x ′ k } is induced and forms with u k ∈ N k (x) a chair,a coP or a cochair; and we get a contradiction with the hypothesis. Furthermore,there is a second color, say s, covered by N i (x); either s is covered by y i , then as there is no chair the dominants x k and x s are adjacent; or|N i (x)| ≥ 2, and there exists y ′ i ∈ N i (x) neighbour of a dominant x s , s = k independent of y i ; x k is independent of y ′ i otherwise x i , y ′ i , x, y i , x k should be a P .

Case α: x k , u t adjacent

The set u t , x, y i , x i , x k forms P if y i , u t are independent, or a cochair if y i , u t are adjacent.

Case β: x k , u t independent Case α being excluded, we may suppose that x s , u t are independent too. (a) If y i , u t are independent, we have a chair or coP composed by u t , y i , x s , x k , or if y ′ i exists, a chair or a cochair composed by u t , x, y i , y ′ i , x k .

(b) If y i , u t are adjacent, Either y i is adjacent to x k , x s , we have coP composed by x i , u t , y i , x s , x k .

Or, y i is adjacent to x k and not to x s , and y ′ i is adjacent to x s and not to x k otherwise we are in some precedent case. Then

y i , u t , x, y ′ i , x s forms either a coP (if [y ′ i , u t ] / ∈ E(G)) or a cochair (if [y ′ i , u t ] ∈ E(G)).
As the subgraphs P ,coP,chair,cochair are excluded, in any subcase, there is a contradiction. Case2 cannot occur.We get part2 of the theorem.

Proof of theorem 3

1) Each class considered here is hereditary. It is sufficient to show by contradiction that for any graph G of the class and any vertex x of G a dominating coloring of Gx extends to G, so b(Gx) ≤ b(G).

We keep the notations of the proof of the second part of Theorem 2. There exists at least a vertex y i such that N (y) ∩ N 2 (x) contains all the dominants of at least a color k, otherwise we know that there is at least a color k with all dominants in N (N i (x)) ∩ N 2 (x) and we get a P 5 composed by xy i y ′ i x k x ′ k where y i , y ′ i are in N i (x) and x k , x ′ k are 2 dominants of color k, a contradiction with the hypothesis on G . By remark R3, no dominating vertex of the color k has a neighbour of color i outside N i (x).

1) Case α: y i , u t independent

We have a P 5 or P composed by x k , y i , x, u t , x i .

Case β: y i , u t adjacent As u t is not dominant, there is a color s and a vertex z s ∈ N (x) not neighbour of u t . As x i is dominant,there exists a vertex v s neighbour of x i . We may suppose x k , u t independent otherwise we have a cochair x k , y i , u t , x i . subcase:z s neighbour of x i : (a) Either x k is not neighbour of z s , then x k , y i , u t , x i , z s gives either P 5 or P ;

(b) Or, x, u k , z s , x i , x k form P . subcase:z s , x i independent :

As u t and v s are independent, then x, u t , v s , x i and z s form either P 5 or P . As the graph is (P 5 , P, cochair) free, there is a contradiction in any case. So there exists a color j such that N (N j (x)) ∩ N 2 (x) contains no dominant. 2) The proof is similar to that of part1 . The only difference is that in the subcase where x k and y i are adjacent to u t , we have a coP 5 composed by y i , u t , x i , v s , x

Proof of theorem4

Let i be a color in I. As G is a quasi-line graph,there are at most two neighbours u i and u ′ i of x which are of color i;

N 2 (x) ∩ N (u i ) is a clique, the same holds for N 2 (x) ∩ N (u ′ i ) if u ′ i exists.
By remarque R3, there exists at least a color j ∈ I with all dominating vertices in N

2 (x) ∩ (N (u i ) ∪ N (u ′ i )).
We do the following operation:

1) We change the color of u i into a missing color p(u i ) and that of u ′ i into a missing color p(u ′ i ). We color x by i.

2)We choose one color, say s, which is no more dominating a) either the initial dominating vertex w s was unique and in N 2 (x) ∩ N (u) ,where u ∈ {u i , u ′ i }, we recolor w s by the color i.

Furthermore, if there is a color s ′ which the initial dominating vertex w s ′ was unique and in N 2 (x) ∩ N (v) where v ∈ {u i , u ′ i }, v = u, we choose one such color and we do the same operation as precedently on w s ′ . b) case (a) being excluded, the color s had exactly 2 initial dominating vertices and they were in N 2 (x) ∩ (N (u i ) ∪ (N (u ′ i )), we recolor them by i.

3) For each color, s or s ′ , we recolor each vertex of the corresponding class by a missing color.

Thus, after steps(1) and ( 2) of this operation, we get a proper coloring; the vertex x is so a dominant vertex of the color i;furthermore, each neighbour of u i (resp. of u ′ i ) which is not of color is neighbour of a vertex of color i. At most 2 colors of the initial coloring are not used, namely s and s ′ . After step (3), we have a dominating coloring of G with at least q -2 colors.

This finishes the proof of theorem4

Proof of theorem 5 We suppose we have a dominating coloring of H = Gx. We use notations and remarks R1, R2,R3 given upper, in the proof of Theorem2. For each color i in I, we choose a dominating vertex w i . Let W be the set of these dominating vertices. Let t, t ≥ r + 1 be a fixed color. Let y in N t (x), and let p(y) = t a color not neighbour of y. If no ambiguity, we shall write simply p instead of p(y). We call C t,p (y) the set of vertices joined to y by a path with vertices in C t ∪ C p ∪ W such that no 2 vertices of W are consecutive.

Let us first describe the operation O on N (x).

We fix a color t. O 1 ) Process O 1 (y): If y ∈ N t (x) is not neighbour of N p (x) for some p, we choose such a color and we color y by p . We exchange the two colors t and p in the component C t,p (y). We do this operation successively for each vertex y of N t (x). O 2 ) Finally, we give the color t to x.

We remark that:

As G is a chordal graph, two vertices of N t (x) have no common neighbour outside x ∪ N (x); furthermore, there is no path P (y, N t (x)) with internal Lemma 2 Let G be a chordal graph. Then, for each t ∈ I,

1) b(G -x) ≤ b(G) + |R t |
2)For any vertices y, y ′ of R t , then p(y) = p(y ′ ). And, if d -(y) is the number of colors which do not appear in N (x) ∩ N (y), we have y∈Rt d -(y) ≤ (q -1) .

Proof of Lemma 2

1) The first part is a consequence of (2) of Lemma1.

2)If y and y ′ are elements of R t , there exists a path P (y, w p(y) ) in C (t,p(y)) , and a path P (y, w p(y ′ ) ) C (t,p(y ′ )) in by Lemma 1. As C (t,p(y)) ∩ C (t,p(y ′ )) = ∅, then by Lemma1, they have no common missing color j, so we get the inequality • End of the proof of theorem 5

We consider a b-dominating coloring of Gx by q = b(Gx) colors. After operation O 1 (v) applied on a vertex v, the color p(v) remains dominating if N t (x) = v was missing only one color in G and v is a reprentative of p(v) .

In N (x), let C be a class of colors such that by the operation O the minimum number of colors are no more dominating.

In a chordal graph, if S 1 and S 2 are two vertex disjoint stable sets, the induced vertex graph of vertex-set S 1 ∪S 2 is a forest. Then given a coloring of N (x)\C by a minimum number of colors, we have a partition X 1 , ..., X s of N (x) \ C. Then, as there is no induced C 4 , the set of edges E(R, X i ) is a matching between R and X i . So e(R, X i ) ≤ min(|R|, |X i |)

for each i ≤ s.

As N (x) -C is chordal of clique-number at most (ω -1), we get by summing e(R, N (x) -C) ≤ min((ω -1).|R|, (d(x) -|R|))

(5)

Each vertex y of C is not neighbour in N (x) of at least (q -1)d N (x) (y)) colors. So (q -1)|R|e(R, N (x) -C) ≤ y∈R d -(y).

On the other hand, as G is chordal,by Lemma 2, y∈R d -(y) ≤ (q -1), we get, using inequality [START_REF] Kouider | On b chromatic number of graphs, subgraphs and degrees[END_REF], that (q -1)|R| -(d(x) -|R|] ≤ q -1 and, (q -1)|R| -(ω -1)|R| ≤ q -1 So |R| ≤ 1 + min( d(x) -1 q , (ω -1) (qω) )

As

Fig. 1 .

 1 Fig. 1. Extensions of P4

6 ) 6 )

 66 by Lemma2, b(Gx) ≤ b(G) + |R|, we get the inequalities 1 and 2 of the theorem.Let us set θ = b(Gx)b(G) -1, and a = qω. From inequality (2), we getθ 2 + a.θ -(ω -1) ≤ 0. It follows that θ ≤ (ω -1)a 2 /4 + (ω -1) + a/2 (As a 2 /4 + (ω -1) ≥ √ a.(ω-1) 1/4 ,we get the third inequality of the theorem Proof of corollary 2 From inequality 1 of the last theorem, we have (θ+1) 2 ≤ d(x) -1. Whereas inequality (6) of the last proof gives θ ≤ (ω -1) a 2 /4 + (ω -1) + a/2 (Proof of corollary 3 Let us set θ = b(Gx)b(G). The inequality (2) of the last theorem gives (θ -1)(b(G)ω + 3) ≤ ω -1 Suppose θ ≥ 2. Then we get b(G) ≤ 2ω -4. The corollary 2 follows •

  and is dominating. Every dominating vertex outside H ′ must be neighbour of the color c(x). And as ω/2k -(k + 1) > 0, each copy of A 2 and each copy of A 3 outside H ′ must contains a dominating vertex; as x is neighbour of each copy of A 1 , this implies that each copy of A 2 ∪ A 3 outside H ′ must contain a vertex of color c(x). Then by (a), b(G 1 ) ≤ ω +ω/2k -k +1. One can verify easily the equality b(G 1

vertices in C (t,p) (y), and, no path P (y, N p (x)) in C (t,p) (y) ;so C (t,p) (y) does not meet x ∪ N (x) outside y.

The operation O is possible for every color t with no dominating vertex in N (x).

Lemma 1 Let t ≥ r + 1 fixed. 1)After an application of operation O 1 (y), we obtain a proper coloring of G; at most one element of W , w t or w p , is no more dominant. If the color p(y) is no more dominating, then w p ∈ C t,p(y) (y)

2)After operation O, the vertex x is a dominating vertex of color t. The colors which have no dominating vertex are among the chosen missing colors.

Proof of Lemma 1 1)If for some j = p(y), j = t, w j ∈ C t,p(y) (y), then necessarily its neighbours of colors p(y) and t are also in C t,p(y) (y); then by operation O 1 (y), there is a permutation of the colors p(y) and t in C t,p(y) (y);so the vertex w j remains dominating of color j. We remark that if w j / ∈ C t,p(y) (y), then its neighbours of colors p(y) and t are not in C t,p(y) (y); their colors are not changed after operation O 1 (y), the same conclusion holds for w j ; so vertex w j remains dominating of color j.

If w t ∈ C t,p(y) (y), then after operation O 1 (y), the vertex w t becomes dominating of color p. Analogously, if w p ∈ C t,p(y) (y), after operation O 1 (y), w p becomes a dominating vertex of color t.

Suppose u ∈ C t,p(y) (y) ∩ C t,p(y ′ ) (y ′ ). Then there exists a path from u to y and another one from u to y ′ , so there is a cycle C containing the induced path [y, x, y ′ ] and no vertex of C -{y, y ′ } is neighbour of x. We may suppose C is a shortest cycle with the latest properties . C is of length at least 4 and has no chord. As G is chordal we get a contradiction.

2) After operation O, the vertex x is neighbour of every color except t; so x is dominating vertex of color t. As C t,p(y) (y) ∩ C t,p(y ′ ) (y ′ ) = ∅, any vertex is recolored at most one time and by 1) of the Lemma, the possible non dominating colors are in the set (p(y)) y∈Nt(x) • Let R t be the set of vertices of C t such that for each vertex y of R t for any missing color p(y), after the operation O, the color p(y) has no dominating vertex. Furthermore, if C t = C , let us denote R t simply by R.