IMFM Institute of Mathematics, Physics and Mechanics Jadranska 19, 1000 Ljubljana, Slovenia Preprint series Vol. 48 (2010), 1131 ISSN 2232-2094 ON THE B-CHROMATIC NUMBER OF REGULAR GRAPHS Sergio Cabello Marko Jakovac Ljubljana, October 14, 2010 On the b-chromatic number of regular graphs* Sergio Cabello^ Faculty of Mathematics and Physics, University of Ljubljana Jadranska 19, 1000 Ljubljana, Slovenia sergio.cabello@fmf.uni-lj.si Marko Jakovac Faculty of Natural Sciences and Mathematics, University of Maribor Koroska 160, 2000 Maribor, Slovenia marko .j akovac@uni-mb .si U CD o O o 00 CO CD September 29, 2010 Abstract The b-chromatic number of a graph G is the largest integer k such that G admits a proper k-coloring in which every color class contains at least one vertex that has a neighbor in each of the other color classes. We prove that every d-regular graph with at least 2d3 vertices has b-chromatic number d + 1, that the b-chromatic number of an arbitrary d-regular graph with girth g = 5 is at least and that every d-regular graph, d > 6, with diameter at least d and with no 4-cycles admits a b-coloring with d +1 colors. 00 Key words: b-chromatic number, size, girth, diameter AMS subject classification (2010): 05C15 W CO 1 Introduction and preliminaries HH The b-chromatic number f(G) of a graph G is the largest integer k such that G admits a proper k-coloring in which every color class has a vertex adjacent to at least one vertex in each of the other color classes. Such a coloring is called a b-coloring. Let G be a graph and c a b-coloring of G. If x € V(G) has a neighbor in each other color class we will say that x realizes color c(x) and that c(x) is realized on x. We can easily imagine the color classes as different communities, where every community i has a representative (a vertex realizing color i) that is able to communicate with all the others communities. This concept was introduced in 1999 by Irving and Manlove [14] who proved that determining <^(G) is NP-hard in general, but can be computed in polynomial time for trees. Kratochvll, Tuza, and Voigt [23] further showed that determining <^(G) is NP-hard already for bipartite graphs. Corteel, Valencia-Pabon, and Vera [7] proved that there is no constant e > 0 for which the b-chromatic number can be approximated within a factor of (120/113) — e fi in polynomial time, unless P=NP. *Research supported in part by the Slovenian Research Agency, program P1-0297 and project J1-2043. ^Also at the Institute of Mathematics, Physics and Mechanics; Jadranska 19, 1000 Ljubljana, Slovenia. CD o o 00 From the combinatorial perspective, b-colorings have been studied for different families of graphs. Effantin and Kheddouci [8, 9, 10] studied the b-chromatic number of powers of paths, cycles, complete binary trees, and complete caterpillars. Hoang and Kouider [13] introduced and studied the concept of b-perfect graphs. Kouider and Zaker [22] gave several bounds for ^>(G) depending on the clique number and the clique partition number of G. Barth, Cohen, and Faik [3] discussed the b-spectrum of graphs. More recent work has considered cographs and P4-sparse graphs [5], Kneser graphs [15], vertex-deleted subgraphs [12], and Mycielskians [1, 2]. The b-chromatic number of the Cartesian product of general graphs was studied in [20, 21], while the Cartesian product of complete graphs is considered in [6]. In [17] three standard products were considered: the strong, the lexicographic, and the direct product. Tight lower and upper bounds were determined. The lower bounds can be derived from the b-chromatic number of factors of the product. It is shown that there is no upper bound with respect to the b-chromatic number of the factors for the Cartesian, the strong, the lexicographic, and the direct product. A trivial upper bound for ^>(G) is A(G) + 1, where A(G) denotes the maximum degree of G. Let d(vi) > d(v2) > ... > d(vn) be the degree sequence of G. The parameter m(G) = max{i | d(vj) > i — 1} is an improved upper bound for ^>(G); see Irving and Manlove [14]. Regular graphs play an important role when studying the b-chromatic number because for every regular graph G the equality m(G) = A(G) + 1 holds. In this paper we study the b-chromatic number of regular graphs. Our results. Kouider and El Sahili [19] and Kratochvll, Tuza, and Voigt [23] proved that fi(G) = A(G) + 1 for any d-regular graph G with at least d4 vertices. This means that for a given d there are only a finite number of d-regular graphs G with fi(G) < d + 1. It is known [16] that there are precisely four cubic graphs with (p(G) < A(G) + 1, one of them being the Petersen graph. All the exceptions have no more then 10 vertices. In this paper we reduce the bound of d4 vertices to 2d3 vertices. Thus, any d-regular graph with at least 2d3 vertices has b-chromatic number d + 1. This result is derived in Section 2. El Sahili and Kouider [11] asked whether it is true that every d-regular graph G with girth at least 5 satisfies ^>(G) = d + 1. The question was solved for (i) d-regular graphs with girth at least 6 [18]; (ii) d-regular graphs with girth 5 and no C6 [11]; (iii) d-regular graphs different from the Petersen graph with girth at least 5 and d < 6 [4]. However, there are regular graphs with small b-chromatic number, like for example the complete bipartite graph Kn,n. We show that the b-chromatic number of d-regular graphs with girth g = 5 is at least • Therefore, for graphs of girth at least 5 the parameter ip(G) is bounded from below by a linear function of the degree. This result is derived in Section 3. In Section 4 we show that the b-chromatic number of d-regular graphs with diameter at least d and no 4-cycles is d + 1. This result provides another sufficient condition for regular ^ graphs to achieve maximum b-chromatic number. We conclude in Section 5. m CD Approach. Henceforth, G will denote a d-regular graph. For any positive integer m we will use the notation [m] = {1,..., m}. We construct b-colorings using variations of the following technique. Assume we have a partial coloring that realizes some of the colors. Let s be an uncolored vertex. To decide if the partial coloring can be extended so that s realizes color i, we construct a bipartite graph H where one partition consists of the neighborhood N(s) = Ng(s) of s, the other partition consists of the colors [d +1] \ {i}, and we have an edge between vertex u and color c whenever CD coloring u with c does not conflict with the current partial coloring. If the graph H has a perfect matching M, then we can extend the partial coloring so that vertex s realizes color CO CO i. This is achieved assigning color i to s, and assigning to each vertex of N(s) the color matched via M. To decide if H has a perfect matching we can then use Hall's theorem. 2 Size u CD o o o 00 0 o 1 00 ^ CO CO We will use the following result to extend the number of realized colors in a partial coloring. See Fig. 1. U N(U) V(G) \ (U U N(U)) Figure 1: Schematic situation in Lemma 2.1. Lemma 2.1. Assume we have a partial coloring of G assigning colors from [d + 1] to U C V(G). Let s € V(G) \ (U U N(U)). If for each j € [d - 1] |{v € N(s) | v is adjacent to at least j vertices of U}| < d — j , then we can extend the partial coloring such that an arbitrary color of the set [d+1] is realized on vertex s. Proof. Let c : U ^ [d + 1] be the partial coloring of G. Without loss of generality, let d + 1 be the color we wish to realize on s. Consider a bipartite graph H, where one partition consists of Ng(s) and the other of colors [d]. Vertex v € NG(s) is adjacent to color a € [d] in H if and only if vertex v can receive color a; that is, if a € c(NG(v) n U) (Fig. 2). v Q . O O O 1 O 2 O 3 CO CD Jh CD CO u a CD U o Nc(s) O d colors We have Figure 2: Graph H degH(v) = d — |c(Ng(v) n U)| > d — |Ng(v) n U|. With Hall's theorem we shall prove that within the given assumptions there exists a perfect matching in H. Take any T C NG(s). If |T| = 1, then |NH(T)| > 1 because s € U. If |T| > 2, the assumptions of the lemma imply |{v € Ng(s) | |Ng(v) n U| > d — |T| + 1}| < d — (d — |T| + 1) = |T| — 1, s which means that T has at least one vertex t with |NG(t) n U| < d — |TTherefore u CD o ^ o o 00 £ CO CO CO |Nh(T)| > inax{degH(t)} = d — mm{|c(NG(t) n U)|} > d — mm{|NG(t) n U|} > d — (d — |T|) = |T We conclude by Hall's theorem that the graph H has a perfect matching M. We can extend the partial coloring c to U U{s}U NG (s) assigning to s color d+1 and assigning to each vertex v € Ng (s) the color given by the matching M. In this partial coloring, vertex s realizes color d + 1. □ Theorem 2.2. Let G be a d-regular graph with at least 2d3 vertices. Then ^>(G) = d + 1. Proof. Let |V(G)| > 2d3. The proof will iteratively construct a partial coloring of G in such a way that, at the end of iteration z (z = 1,2,..., d + 1), we have a partial coloring that realizes the colors of [z]. In the partial coloring, only vertices that realize a color and their neighborhoods are colored. We start with a partial coloring that does not color any vertex. Ng(U ) U d - < j d - 1 o >j Bj <1 J"^/ ' Ad-1 I c^ W Figure 3: Schema showing the sets Ai and Bj in the proof of Theorem 2.2. Consider an iteration z € [d + 1]. Let U be the set of vertices that were already colored. For z = 1 we have U = 0. We can assume by induction that the colors [z — 1] are already realized by the partial coloring of U. We want to find a vertex where to realize color z. The size of U is at most d(d + 1) because it contains z — 1 < d vertices realizing some color and their neighborhoods. For each i € [d], let Ai be the set of vertices from V(G) \ U that are adjacent to exactly i vertices of U. See Fig. 3. Note that N(U) = Q Ai i=1 Next we double count the edges (U, N(U)) between U and N(U). On the one hand, (U, N(U)) contains exactly ^i i ■ |Ai| edges. On the other hand, since the vertices of U that realize a color do not contribute any edge to (U,N(U)), there are at most (z — 1)d < d2 vertices in U that are adjacent to N(U). Using that each one of them has at most d — 1 neighbors in N(U) because they have at least one neighbor within U, we conclude that & d ■ |Ai| = |(U,N(U))| < d2(d — 1). (1) i= 1 Q It also follows that |N(U)| < d2(d — 1). o For each j € [d — 1], let Bj = {v € U U N(U) | |N(v) n (Ad U Ad-1 U ... U Ad-j)| > j}, and define d-1 B = [J Bj . j=1 o o Assume that there is a vertex s that does not belong to U U N(U) U B. Then, for each j € [d — 1], the vertex s does not belong to Bj, which means that |N(s) n (Ad U Ad-1 U ... U Ad-j)| < j. Setting j' = d — j, we see that, for each j' € [d — 1], the neighborhood N(s) has at most d — j' vertices which are adjacent to at least j' vertices of U. By Lemma 2.1, color z can be realized on vertex s. We have to determine the minimum size of V(G) in order to ensure that U U N(U) U B is not the whole V(G). Double counting the edges between Bj and (Ad U Ad-1 U ... U Ad-j), and noting that a vertex of Aj has at most d — i neighbors outside U U N(U), we obtain 00 d j ■ |Bj| < £ (d — i) ■ |Aj| = £ i ■ |Ad-j|, i=d-j j=1 o ^ and thus 1 j \B,\ < -J^i-lA^l j i=1 This leads to d-1 d-1 1 j j=1 j=1j j=1 d-1 d-1 1 = Et j=1 j=j d-1 d j=1 d-1 ^(d — i) ■ |Ad-j | j=1 m CD where in the last step we have used (1). Joining the bounds we see < d2(d — 1), |U| + |N(U)| + |B| < d(d + 1) + d2(d — 1) + d2(d — 1) = 2d3 — d2 + d. Therefore, if |V(G)| > 2d3 — d2 + d, we can find in every iteration z a vertex s on which color z can be realized. When |F(G)| > 2d3 this condition holds. As usual, after iteration z = d + 1 we can color the rest of the graph G greedily. □ u CD o ^ o o 00 0 o 1 00 ^ CO CO CO CD $H CD CO Next we show that the bound 2d3 can not be lowered below d2 in general. For this purpose we first introduce the definition of lexicographic product. The lexicographic product of graphs G and H, denoted by G[H], has vertex set V(G) x V(H) and two vertices are adjacent if (i) they are adjacent in the first coordinate, or (ii) they are equal in the first and adjacent in the second coordinate. From the definition it is obvious that the lexicographic product is not commutative. Let d > 2 be an even positive integer and let Sd/2 be an independent set on | vertices. The graph C2d [Sd/2], where C2d is a cycle on 2d vertices, is a d-regular graph with exactly 2d ■ f = d2 vertices. Fig. 4 shows the 4-regular graph C8 [S2]. We prove that its b-chromatic number is at most d. 1 Figure 4: Lexicographic product C8 [S2] Proposition 2.3. Let d > 2 be an even positive integer. Then ^ (C2d [Sd/2]) < d. Proof. The vertices of C2d [Sd/2] whose first coordinate is the same form a so-called Sd/2-fiber, which is a copy of the independent set Sd/2. There are 2d different Sd/2-fibers, and they form a partition of the vertex set of the graph. Consider a b-coloring of graph C2d [Sd/2] with ^ (C2d [Sd/2]) colors. Consider the vertex realizing color i and let F be the Sd/2-fiber that contains it. See for example the case i = 1 for the graph C8 [S2] in Fig. 4. Colors [d +1] \ {i} must then be used on the two neighboring Sd/2-fibers. However, this implies that all the vertices of F must have color 1. Thus none of the vertices of F or the two neighboring Sd/2-fibers can realize any of the colors [d + 1] \ {i}. This means that the Sd/2-fibers which have a vertex that realizes a color must be at least at distance two apart. Since there are only 2d Sd/2-fibers, at most d colors can be realized, and thus fi{C2d[Sd/2]) |U|/2 for all x € U U V \ {u*, v*} and degH(u*), degH(v*) > 0, then H has a perfect matching. Proof. Let T C U a nonempty subset of U. We will show that |NH(T)| > |T|. We have four cases to consider. Case 1: |T| = 1. In this case T = {u} for some vertex u € U. Since degH(u) > 0 we have |Nh(T)| = degH(u) > 1 = |T|. Case 2: 1 < \T\ < M Then |U | \NH(T)\ > max{degH(.T)} > ^ > \T\. x£l 2 Case 3: ^ < \T\ < \U\ - 1. For all x € V \ {v*} we have degH{x) > ^ and therefore Nh(x) n T = 0. This means that V \ {v*} C Nh(T), which implies |Nh(T)| > |V| - 1 = |U |- 1 >|T |. Case 4: |T| = |U|. Because degH(x) > 0 for all x € V, it follows that |Nh(T)| = |V| = |T|. Combining all the cases and using Hall's theorem completes the proof. □ Theorem 3.2. Let G be a d-regular graph with girth 5. Then <^(G) > |_ d+1 2 . Proof. Consider a vertex vi, and denote its neighbors by vj, i € {2,..., d + 1}. We define Vj = N(vj) \ {v1}. Since G has girth 5, the sets Vj and Vj are disjoint for each i = j in the range {2,..., d + 1}. See Fig. 5, where the edges adjacent to vj, i € [d + 1], are included, but there may be some additional edges between the other vertices that are not shown in the figure. Note that a vertex of Vj may be adjacent to at most one vertex of Vj, as otherwise G would contain a 4-cycle. d - 1 m CD CD m u a CD U Figure 5: Girth 5 subgraph We construct a partial coloring of G. Firstly, we color vertex vj with color i for each i € [d+1]. Then, we iteratively consider i = 2,..., , and distribute colors {2,..., d+l}\{?'} to the vertices Vj in such a way that we realize color i on vertex vj. Assume we are on the i-th iteration. We have already colored N(vj) for all j < i. Consider the bipartite graph Hj, where one partition consists of vertices Vj and the other of colors {2,... ,d +1}\{i}. In the graph Hj, vertex u € Vj is adjacent to color c € {2,... ,d + 1}\{i} if and only if vertex u can be colored with color c in the current partial coloring of G. We next argue that degH. (x) > d — i for each x € V(H). Since in G each vertex u € Vj is adjacent to at most one vertex in each Vj, it follows that u has at most i — 1 neighbors that are already colored. Therefore, degH.(u) > d — 1 — (i — 1) = d — i for all u € Vi. Similarly, for j < i each color c appears at most once in each Vj because the partial coloring realizes color j in vj. Therefore, each color c is forbidden for at most i — 1 vertices of Vi, and we (N have degH.(c) > d — 1 — (i — 1) = d — i. Since the bipartite graph Hi has minimum degree d — i and each class of the partition has d — 1 vertices, Lemma 2.1 guarantees that Hi has a perfect matching, provided that U d — 1 min {degH.(.r) | x € V(Hi)} > d-i > —— . q This condition is fulfilled when . ^ , d — 1 d + 1 Therefore, at each iteration we can find a matching in Hi, and use it to color Vi such that vi realizes color i. When we finish the iteration i = , we have a partial (d, + l)-coloring of G where colors {1,..., are realized. We color the rest of the graph with the greedy algorithm using colors {1,...,d + 1}. The resulting coloring is not necessarily a proper b-coloring. However, we can convert it into a proper b-coloring with a stepwise recoloring, as follows. Set the color set S = [d + 1]. While the current coloring is not a proper b-coloring with colors S, we choose a color c € S that is not realized, recolor any vertex of color c with another color of the set S \ {c}, and remove c from the set S. Thus, at each step we reduce the size of S by one and obtain a new coloring using the colors S \ {c}. It is obvious that when the procedure finishes, we have a proper b-coloring of G with colors S. Moreover, the colors {1,..., are realized throughout the recoloring process, and therefore we obtain a b-coloring with at least colors. □ CO 4 Diameter In this section we show that a d-regular graph with large diameter and no 4-cycles has CO b-chromatic number d + 1, thus providing another sufficient condition to attain maximum CO b-chromatic number. Theorem 4.1. Let G be a d-regular graph with no 4-cycles and diam(G) > d. Then <^(G) = fc d + 1. Proof. Let d > 6. Since diam(G) > d, there exists a path v1v2 ...vd,vd+1 (Fig. 6) that satisfies d(v1 ,vd+1) = d. Let V1 = N(v1) \ {v2}, Vm = N(vd+1) \ {vd}, and Vi = N(vi) \ {vi-1, vi+1}, i € {2,..., d}. The size of V1 and Vd+1 is d — 1 and the size of Vi, i € {2,..., d}, is d — 2. To reduce the number of boundary cases, we define Vj- = 0 for any j / [d + 1]. Since G has no 4-cycle and v1v2 ... vd, vd+1 is a shortest path, the vertices of V have the 5h following properties: (a) |Vi-1 n Vi| < 1. When Vi-1 n Vi is nonempty, we denote by ui its unique vertex. CD ■ i-H J-H CD CO (b) Vi n Vj- = 0, for each j < i — 2. Here we use that there are no 4-cycles for j = i — 2 and the shortest path property for j < i — 2. & (c) Any vertex of Vi is adjacent to at most one vertex of Vi-2 and at most one vertex of Vi-3. (d) No vertex of Vj is adjacent to any vertex of Vj, for each j < i — 4 or j = i — 1. (e) If Vj n Vj+i is nonempty, then uj+i is not adjacent to any vertex of Vj, for each j < i — 3 or j = i — L U CD o ^ o o 00 We will construct a (d + 1)-b-coloring of G such that vertex vi realizes color i for each i € [d + 1]. We start assigning color i to vertex vi, for each i € [d + 1]. The vertices of Vi, V2,... will be colored inductively such that, when we finish coloring Vi, the following inductive statement holds: vertex vj realizes color j for each j € [i], and if Vi n Vj+i is nonempty, then uj+i has a color distinct from i + 2. We start coloring the vertices of Vi with colors {3,..., d + 1} injectively, such that, if Vi n V2 is not empty, then u2 gets assigned color d + 1 = 3. vi Vi-2 Vi-1 Vd+1 0 o 1 00 ^ CO CO CO CD $H CD CO $H a CD Jh Figure 6: Path viv2 ... vd, vd+i Consider now the case i > 2, where we want to color Vi. Because of properties (a) and (b), at most one vertex of Vj is already colored, namely the unique vertex mj that may be in Vi-i n Vi. Let Q be the set of colors [d + 1] \ {i — 1, i, i + 1}. Note that Q| = |Vj| > d — 2, with equality when i = d + 1. If the vertices of Vj are colored injectively with the colors Q, then vertex vi will realize color i. Note that we have to respect the color already assigned to mi, if such vertex exists. Consider a bipartite graph H where one partition is Vi and the other partition is C. The graph Hj contains an edge between a vertex v and a color c if coloring v with color c does not conflict with the current coloring. In particular, if the vertex mj exists, then it has degree 1 in Hj. Furthermore, if Vi n Vj+i is nonempty, we remove from Hj the edge between vertex uj+i and color i + 2, to avoid that uj+i could get color i + 2. We next look at the degrees in Hj for vertices in Vi. Because of properties (c) and (d), each vertex from Vj\ (Vj+i U Vj-i) has at most three colored neighbors: vj, one from Vj-2, and one from Vj-3. Since color i +1 is not in Cj, we conclude that each vertex of Vj \ (Vj+i U Vj-i) has degree at least |Cj| — 2 in Hj. If Vj n Vj+i is nonempty, then the vertex uj+i has at most three colored neighbors because of properties (c) and (e): vj, vj+i, and a vertex from Vj-2. Since colors i and i + 1 are not in Cj and we removed from Hj the edge between uj+i and i + 2, it follows that uj+i also has degree at least |Cj| — 2 in Hj. If Vj-i n Vj is nonempty, then the vertex uj has degree one in Hj. We conclude that any vertex of Vj \ Vj-i has degree at least |Cj| — 2 in Hj, while uj has degree at least one. We next look at the degrees in Hj for colors in Cj. Each color c € Cj appears at most once in Vj-2 and at most once in Vj-3 because each vertex vj realizes a color, for j < i — 1. Because of a symmetric version of property (c), each vertex of Vj-3 or Vj-2 has at most one neighbor in Vj. This means that each color of Cj\{i + 2} is forbidden for at most two vertices of Vj, and has degree at least |Cj| — 2 in Hj. Color i + 2 may be additionally forbidden for vertex uj+i, if such vertex exists, because we removed that edge from Hj. We conclude that any color of Cj \ {i + 2} has degree at least |Cj| — 2 in Hj, while color i + 2 has degree at least |Cj| — 3. By Lemma 3.1, if |Cj| — 2 > |Cj|/2 and |Cj| — 3 > 0, then we can injectively color the vertices of Vj \ Vj-i with the colors of Cj. This last condition is equivalent to |Cj| > 4, which v i is fulfilled when d > 6. Moreover, since Hi does not contain the edge between vertex ui+1 and color i + 2, the inductive statement holds. When we finish coloring Vd+1, the inductive statement implies that vertex vj realizes color j for all j € [d + 1]. The rest of the graph can be colored greedily using d + 1 colors. □ One might think that the assumption about 4-cycles is forced. However, the graph C2d [Sd/2] considered in Section 2, where d is even, is d-regular and has diameter d, but its b-chromatic number is not d +1. O 5 Concluding remarks O O 00 CO CD We have shown two sets of sufficient conditions that force a d-regular graph to have b-chromatic number d + 1. One of them concerns the size of the graph and the other the diameter. We have also seen that girth 5 forces large b-chromatic number. We think that progress in the following problems would be of interest: • We conjecture that there exists a constant c > 1 such that any d-regular graph with at least c ■ d2 vertices has b-chromatic number d + 1. Perhaps a probabilistic method would be useful for improving our bound in Section 2. • Petersen graph is the only known d-regular graph with girth 5 whose b-chromatic number is not d +1. It is tempting to think that this may be the only exception [4, 11]. A weaker conjecture is that the b-chromatic number should be at least d, which would improve our results from Section 3. In this case d-regular graphs with girth 5 would have only two possibilities for the b-chromatic number, namely d or d + 1. • Are there any other sufficient conditions to ensure that the b-chromatic number of a d-regular graph is d +1? References £ [1] R. Balakrishnan, S. Francis Raj, Bounds for the b-chromatic number of the Mycielskian of some familes of graphs, manuscript. HH [2] R. Balakrishnan, S. Francis Raj, Bounds for the b-chromatic number of G — v, manuscript. [3] D. Barth, J. Cohen, T. Faik, On the b-continuity property of graphs, Discrete Appl. Math. 155 (2007) 1761-1768. [4] M. Blidia, F. Maffray, Z. Zemir, On b-colorings in regular graphs, Discrete Appl. Math. 157 (2009) 1787-1793. [5] F. Bonomo, G. Duran, F. Maffray, J. Marenco, M. Valencia-Pabon, On the b-coloring of cographs and P4-sparse graphs, Graphs Combin. 25 (2009) 153-167. [6] F. Chaouche, A. Berrachedi, Some bounds for the b-chromatic number of a generalized Hamming graphs, Far East J. Appl. Math. 26 (2007) 375-391. Jh [7] S. Corteel, M. Valencia-Pabon, J-C. Vera, On approximating the b-chromatic number, Discrete Appl. Math. 146 (2005) 106-110. [8] B. Effantin, The b-chromatic number of power graphs of complete caterpillars, J. Discrete Math. Sci. Cryptogr. 8 (2005) 483-502. [9] B. Effantin, H. Kheddouci, The b-chromatic number of some power graphs, Discrete Math. Theor. Comput. Sci. 6 (2003) 45-54. CSI CSI CO CO CD [10] B. Effantin, H. Kheddouci, Exact values for the b-chromatic number of a power complete k-ary tree, J. Discrete Math. Sci. Cryptogr. 8 (2005) 117-129. [11] A. El Sahili, M. Kouider, About b-colourings of regular graphs, Res. Rep. 1432, LRI, Univ. Orsay, France, 2006. [12] S. Francis Raj, R. Balakrishnan, Bounds for the b-chromatic number of vertex-deleted subgraphs and the extremal graphs (extended abstract), Electron. Notes Discrete Math. 34 (2009) 353—358. i—l [13] C. T. Hoang, M. Kouider, On the b-dominating coloring of graphs, Discrete Appl. Math. 152 (2005) 176-186. [14] R. W. Irving, D. F. Manlove, The b-chromatic number of a graph, Discrete Appl. Math. 91 (1999) 127-141. [15] R. Javadi, B. Omoomi, On b-coloring of the Kneser graphs, Discrete Math. 309 (2009) 4399-4408. C^ [17] M. Jakovac, I. Peterin, On the b-chromatic number of strong, lexicographic, and direct product, manuscript. [16] M. Jakovac, S. Klavzar, The b-chromatic number of cubic graphs, Graph Combin. 26 (2010) 107-118. [18] M. Kouider, b-chromatic number of a graph, subgraphs and degrees, Res. Rep. 1392, LRI, Univ. Orsay, France, 2004. £ [19] M. Kouider, A. El Sahili, About b-colouring of regular graphs, Rapport de Recherche No 1432, CNRS-Universite Paris Sud-LRI. [20] M. Kouider, M. Maheo, Some bounds for the b-chromatic number of a graph, Discrete Math. 256 (2002) 267-277. [21] M. Kouider, M. Maheo, The b-chromatic number of the Cartesian product of two graphs, Studia Sci. Math. Hungar. 44 (2007) 49-55. [22] M. Kouider, M. Zaker, Bounds for the b-chromatic number of some families of graphs, Discrete Math. 306 (2006) 617-623. [23] J. Kratochvll, Zs. Tuza, M. Voigt, On the b-chromatic number of graphs, In WG '02: CD CO u a CD U Graph-Theoretic Concepts Comput. Sci., Lecture Notes in Comput. Sci. 2573 (2002) 310-320.