Determining the b-chromatic number of subdivision-vertex neighbourhood coronas

DOI: 10.2478/auom-2024-0019 An. S¸t. Univ. Ovidius Constant¸a Vol. 32(2),2024,53–84 Determining the b-chromatic number of subdivision-vertex neighbourhood coronas Ra´ul M. Falc´on, M. Venkatachalam and S. Julie Margaret Abstract Let Gand Hbe two graphs, each one of them being a path, a cycle or a star. In this paper, we determine the b-chromatic number of every subdivision-vertex neighbourhood corona GHor GKn, where Kn is the complete graph of order n. It is also established for those graphs KnGhaving m-degree not greater than n+ 2. All the proofs are accompanied by illustrative examples. 1 Introduction In 1999, Irving and Manlove [1] introduced the b-chromatic coloring of a graph G= (V(G), E(G)) as a proper k-coloring c:V(G)→ {0, . . . , k −1}with a b-vertex for each color i. That is, a vertex v∈V(G) such that c(v) = i and, for each color j6=i, there exists a vertex w∈NG(v) satisfying that c(w) = j. Here, NG(v) denotes the neighborhood of the vertex v. The bchromatic number ϕ(G) is the maximum positive integer kfor which a bchromatic coloring of Gwith kcolors exists. Any such a b-chromatic coloring is said to be optimal. Irving and Manlove proved that the problem of determining the b-chromatic number of a graph is NP-hard in general, and polynomial-time solvable for trees. It has been dealt with by a wide amount of graph theorists (see [2] for a survey). Key Words: b-chromatic number; subdivision-vertex neighbourhood corona; path; cycle; star; complete graph. 2010 Mathematics Subject Classification: Primary 05C15. Received: 27.02.2023 Accepted: 11.07.2023 53 DETERMINING THE b-CHROMATIC NUMBER OF SVN CORONAS 54 Of particular interest for the aim of this paper, it is remarkable the study of the b-chromatic number of distinct graph products as the Cartesian product [3–12], the direct product [13, 14], the strong product [13, 15], the lexicographic product [13, 15, 16], the corona product [17] or the subdivision edge and vertex corona [18]. This paper delves into this topic for the subdivisionvertex neighborhood corona (from here on, SVN corona) of paths, cycles, stars and complete graphs. Recall here that the subdivision graph S(G) of a graph Garises from inserting a new vertex into every edge of G. In 2013, Liu and Lu [19] introduced the SVN corona GHof two graphs Gand H, with V(G) = {u0, . . . , un−1}, as the graph arising from adding nvertex-disjoint copies of Hto S(G), so that every vertex in NS(G)(ui) is joined to every vertex in the (i+ 1)th copy of H, for all i<n. The paper is organized as follows. In Section 2, we describe some preliminary concepts and results on Graph Theory that are used throughout the manuscript. Then, Sections 3–6 deal separately with the b-chromatic number of SVN coronas of paths, cycles, stars and complete graphs. 2 Preliminaries All the graphs throughout this paper are finite and simple. This section deals with some notations and preliminary results on graph theory that are used throughout the paper. Let G= (V(G), E(G)) be a graph. The neighborhood and degree of a vertex v∈V(G) are respectively denoted by NG(v) and dG(v). If there is no risk of confusion, then we use the respective notations N(v) and d(v). In addition, ∆(G) denotes the maximum vertex degree of the graph G. The path, cycle and star of order n > 2 are respectively denoted by Pn,Cn, and Sn−1. The complete graph of order nis denoted by Kn. Aproper k-coloring of a graph Gis any map c:V(G)→ {0, . . . , k −1} assigning kcolors to the set of vertices V(G) so that no two adjacent vertices share the same color. The chromatic number χ(G) is the minimum positive integer kfor which a proper k-coloring of Gexists. An example of proper k-coloring is the b-chromatic coloring with kcolors that has been described in the introductory section. Lemma 1. [1] Let Gbe a graph. Then, χ(G)≤ϕ(G)≤∆(G)+1. Proposition 2. [3] Let nbe a positive integer. Then, •ϕ(Pn) = (2,if n∈ {3,4}, 3,if n > 4. DETERMINING THE b-CHROMATIC NUMBER OF SVN CORONAS 55 •ϕ(Cn) = (2,if n= 4, 3,if either n= 3 or n > 4. •ϕ(Sn) = 2, for all n > 2. •ϕ(Kn) = n. To study the b-chromatic number of any graph, Irving and Manlove defined the m-degree of a graph Gof order nas m(G) := |{i∈ {1, . . . , n}:d(vi−1)≥i−1}| , where V(G) = {v0, . . . , vn−1}is such that d(v0)≥. . . ≥d(vn−1). Lemma 3. [1] Let Gbe a graph. Then, ϕ(G)≤m(G). We finish this preliminary section by introducing some notation concerning any SVN corona GH. Here, we assume that V(G) = {u0, . . . , u|V(G)|−1}and V(H) = {v0, . . . , v|V(H)|−1}. In addition, let I(G) denote the set of vertices that are inserted into the edges of the graph Gto get the subdivision graph S(G). Then, we use the following notation throughout the paper. •si,j denotes the vertex in I(G) that is inserted in an edge uiuj∈E(G). Depending on convenience, we may also denote this vertex by sj,i. •vi,j denotes the copy of each vertex vj∈V(H) in the (i+ 1)th copy of the graph H. In the constructive proofs of the paper, all the indices of the just described vertices are considered to be modulo either |V(G)|or |V(H)|(depending on the case). Furthermore, concerning the graphical representation of the SVN corona GH, edges between S(G) and one of the copies of Hare drawn with dashed lines. Figure 1 illustrates these notations. Figure 1: SVN corona product. DETERMINING THE b-CHROMATIC NUMBER OF SVN CORONAS 56 In particular, dGH(v) =          dG(v),if v∈V(G), 2· |V(H)|+ 2,if v∈I(G), dG(ui) + dH(vj),if v=vi,j ,with (0≤i < |V(G)|, 0≤j < |V(H)|. (1) Proposition 4. The following statements hold. (a) ∆(GH) = max{2· |V(H)|+ 2,∆(G) + ∆(H)}. (b) If ∆(G)≤ |V(H)|+ 3, then: (b.1) ϕ(GH)≤2· |V(H)|+ 3. (b.2) If ∆(G) + ∆(H) + 1 ≤ |I(G)| ≤ 2· |V(H)|+ 2, then ϕ(GH)≤ |I(G)|. Proof. The first statement follows readily from (1). Thus, in what follows, we assume that ∆(G)≤ |V(H)|+ 3. Since ∆(H)≤ |V(H)| − 1, we have that ∆(GH)=2· |V(H)|+ 2, whenever ∆(G)≤ |V(H)|+ 3. Hence, (b.1) follows from Lemma 1. Furthermore, there are |I(G)|vertices in GHhaving maximum degree 2t+ 2. From (1), the highest vertex degree in GHbeing less than this maximum is ∆(G)+∆(H). Thus, the assumptions of (b.2) imply that m(GH) = |I(G)|. Hence, the last statement follows from Lemma 3. Finally, in order to make easier the identification of b-vertices in the constructive proofs described in the next four sections, we define a b-rainbow set of a graph to be any set formed by exactly one b-vertex of each one of the colors associated to an optimal b-chromatic coloring of the graph under consideration. In the illustrative figures of this manuscript, vertices of a particular b-rainbow set are represented by crosses ×; other b-vertices are represented by triangles Nand the remaining vertices are represented by circles •. 3 SVN corona of paths From here on, let Gdenote the set of paths, cycles, stars and complete graphs of any order. In this section, we determine the b-chromatic number of the SVN corona PnGof a path Pn=hu0, . . . , un−1i, with n > 2, and a graph G∈G. As a preliminary result, Proposition 4 enables us to study this number for the SVN corona PnH, for any arbitrary graph Hsuch that n≥∆(H) + 4. DETERMINING THE b-CHROMATIC NUMBER OF SVN CORONAS 57 Proposition 5. The following statements hold. (a) ϕ(PnH)≤n−1, whenever ∆(H)+4≤n≤2· |V(H)|+ 3. (b) ϕ(PnH)=2· |V(H)|+ 3, whenever n > 2· |V(H)|+ 3. Proof. The first statement follows readily from (b.2) in Proposition 4 once it is observed that ∆(Pn) = 2 and |I(Pn)|=n−1. Further, since ∆(Pn)=2< |V(H)|+3, we have from (b.1) in Proposition 4 that ϕ(PnH)≤2·|V(H)|+3. In order to prove that this upper bound is reached, it is enough to define the b-chromatic coloring cof the graph PnHsuch that, for each triple of non-negative integers i<n,j < n −1 and k < |V(H)|, we have that c(ui) = (i+ 1) mod (2 · |V(H)|+ 3), c(sj,j+1) = jmod (2 · |V(H)|+ 3) and c(vi,k) = (i+ 2k+ 3) mod (2 · |V(H)|+ 3). A b-rainbow set is formed by the vertices s0,1, . . . , s2·|V(H)|+2,2·|V(H)|+3. Figure 2 illustrates the b-chromatic coloring described in the previous theorem for (n, t) = (10,3). Figure 2: Optimal b-chromatic coloring of P10 P3. Now, we focus separately on each one of the mentioned graphs PnG, with G∈G. In all the proofs, we define an appropriate b-chromatic coloring c of the graph PnGsuch that (c(ui)=(i+ 1) mod min{m(PnPt), n}, c(sj,j+1) = jmod min{m(PnPt), n}.(2) for every pair of non-negative integers i<nand j < n −1. We start by determining the b-chromatic number for the SVN corona of two paths. Theorem 6. Let n > 2and t > 2be two positive integers. Then, ϕ(PnPt) =                4,if n= 3 and t∈ {3,4}, 5,if (n= 3 and t≥5, n∈ {4,5}, n−1,if 6≤n≤2t+ 3, 2t+ 3,otherwise. DETERMINING THE b-CHROMATIC NUMBER OF SVN CORONAS 58 Proof. The case n > 2t+ 3 follows from Proposition 5. So, we assume from now on that n≤2t+3. From Lemma 3 and (1), we have that all the described values are upper bounds of the b-chromatic number under consideration. In order to see that they are reached, we define an appropriate b-chromatic coloring cof the graph PnPtsatisfying (2). For each pair of non-negative integers i<nand j < t, the following two cases arise. (Here, we assume that Pt=hv0, . . . , vt−1i.) First, if n≤6, then c(vi,j) = ((i+ (jmod 2) + 1) mod 4,if n= 3 and t∈ {3,4}, (i+ (jmod 3) + 1) mod 5,otherwise. Ab-rainbow set is formed by the vertices s0,1, . . . , sn−2,n−1, together with the vertex v1,1, if n < 6; the vertex v1,2, if n∈ {3,4}; and the vertex v1,3, if n= 3 and t≥5. (Figure 3 illustrates the case n=t= 4.) Figure 3: Optimal b-chromatic coloring of P4P4. Second, if 7 ≤n≤2t+ 3, then c(vi,j ) is                (i+ 2j+ 3) mod (n−1),if neven and j < n−4 2, (i+ 2j+ (4 −2(imod 2))) mod(n−1),if (n, i + 1 odd and j < n−4 2, n, i odd and j < n−4 2, (i+ 2) mod 6,if (j, n) = (1,7) and ieven, c(vi,j−2),otherwise. Ab-rainbow set is formed by the vertices s0,1, . . . , sn−2,n−1. (Figure 4 illustrates the case (n, t)∈ {(7,4),(8,4)}.) The next graph to study is the SVN corona of a path and a cycle. DETERMINING THE b-CHROMATIC NUMBER OF SVN CORONAS 59 Figure 4: Optimal b-chromatic colorings of P7P4and P8P4. Theorem 7. Let n > 2and t > 2be two positive integers. Then, ϕ(PnCt) =                4,if (n, t) = (3,4), 5,if (n= 3 and t6= 4, n∈ {4,5}, n−1,if 6≤n≤2t+ 3, 2t+ 3,otherwise. Proof. The case n > 2t+ 3 follows from Proposition 5. So, we assume from now on that n≤2t+ 3. From Lemma 3 and (1), we have that ϕ(PnCt)≤m(PnCt) = (5,if n∈ {3,4,5}, n−1,otherwise.(3) This upper bound is not reached for (n, t) = (3,4), because every b-chromatic coloring of the SVN corona P3C4with five colors would imply the existence of a b-chromatic coloring of the cycle C4with three colors. It is not possible, because ϕ(C4) = 2 (see Proposition 2). Hence, ϕ(P3C4)≤4. Figure 5 shows that this upper bound is indeed reached. To prove that the upper bound in (3) is reached for all (n, t)6= (3,4), we define an appropriate b-chromatic coloring cof PnCtsatisfying (2). Two cases arise for each pair of non-negative integers i < n and j < t. (Here, we assume that Ct=hv0, . . . , vt−1, v0i.) First, if n≤6 and (n, t)6= (3,4), then c(vi,j) =      2,if (n, i, j) = (3,1,2), (i+ 2 + (jmod 2)) mod 5,if j6=t−1 and (n, i, j)6= (3,1,2), i+ 1,if j=t−1. DETERMINING THE b-CHROMATIC NUMBER OF SVN CORONAS 60 Figure 5: Optimal b-chromatic coloring of P3C4. Ab-rainbow set is formed by the vertices s0,1, . . . , sn−2,n−1, together with the vertex v2,0, if n∈ {4,5}; the vertex v1,0, if n∈ {3,4}; and the vertices v1,1 and v1,t−1, if n= 3. (Figure 6 illustrates the case n=t= 4.) Second, if 7 ≤n≤2t+ 3, then we define c(vi,j ) as in the proof of Theorem 6, except for c(vi,j) = (i+ 1,if n= 8, t is odd and j=t−1, i+ 3,if n∈ {7,9}, t is odd and j=t−1. Ab-rainbow set is formed by the vertices s0,1, . . . , sn−2,n−1. Figure 6: Optimal b-chromatic coloring of P4C4. Now, we study the SVN corona of a path and a star. (Recall here that St is the star with tleaves, so its order is t+1. It is important for the application of Proposition 5.) DETERMINING THE b-CHROMATIC NUMBER OF SVN CORONAS 61 Theorem 8. Let n > 2and t > 2be two positive integers. Then, ϕ(PnSt) =                2n−1,if n≤t+3 2, t+ 2,if n=dt+4 2e, t+ 3,if dt+4 2e< n ≤t+ 4, n−1,if t+ 4 < n ≤2t+ 5, 2t+ 5,otherwise. Proof. The case n > 2t+ 5 follows from Proposition 5. So, we may assume that n≤2t+ 5. From Lemma 3 and (1), all the described values are upper bounds of the b-chromatic number. To see that they are reached, we define an appropriate b-chromatic coloring cof the graph PnStsatisfying (2). For each pair of non-negative integers i < n and j≤t, the following two cases arise. (Here, we assume that V(St) = {v0, . . . , vt}, where v0is the center of the star.) First, if n≤t+ 4, then let αn,t =m(PnSt)−n+ 1. Then, we define c(vi,j) as                n−1 + ((i+j) mod αn,t),if j < αn,t, (j−αn,t + 1) mod (n−1),if αn,t ≤j < αn,t +n−2 and i= 0, (j−αn,t) mod (n−1),if αn,t ≤j < αn,t +n−2 and i=n−1, (i+j−αn,t + 1) mod (n−1),if αn,t ≤j < αn,t +n−3 and i6∈ {0, n −1}, c(vi,j−1),otherwise. Ab-rainbow set is formed by the vertices s0,1, . . . , sn−2,n−1, together with either the vertices v0,0, . . . , vn−1,0, if n≤t+3 2; or the vertices v0,0, . . . , vt−n+2,0, if n=dt+4 2e; or the vertices v0,1, . . . , vt−n+4,0, if dt+4 2e< n ≤2t+ 5. (Figure 7 illustrates the case (n, t)∈ {(3,4),(4,4),(6,4)}.) Second, if t+ 4 < n ≤2t+ 5, then c(vi,j) =          (i+ 3) mod (n−1),if j= 0, (i−j−2) mod (n−1),if iis even and 0 < j ≤min{n−6, t}, (i+j+ 3) mod (n−1),if iis odd and 0 < j ≤min{n−6, t}, c(vi,j−1),otherwise. Ab-rainbow set is formed by the vertices s0,1, . . . , sn−2,n−1. (Figure 8 illustrates the graph P9S4.) Finally, we study the SVN corona of a path and a complete graph. DETERMINING THE b-CHROMATIC NUMBER OF SVN CORONAS 68 Figure 14: Optimal b-chromatic colorings of C5C3and C6C3. First, if n≤t+ 2, then let αn,t =m(CnSt)−n, then c(vi,j ) =                n+ ((i+j) mod αn,t),if j < αn,t, (j−αn,t + 1) mod n, if αn,t ≤j < αn,t +n−2 and i= 0, (j−αn,t) mod n, if αn,t ≤j < αn,t +n−2 and i=n−1, (i+j−αn,t + 1) mod n, if αn,t ≤j < αn,t +n−3 and i6∈ {0, n −1}, c(vi,j−1),otherwise. Ab-rainbow set is formed by the vertices s0,1, . . . , sn−2,n−1, s0,n−1, together with either the vertices v0,0, . . . , vn−1,0, if n≤ bt+3 2c; or the vertices v1,1, . . . , vt+3−n,1, if bt+3 2c< n ≤t+ 2. Second, if t+ 3 ≤n≤2t+ 5, then c(vi,j) =          (i+ 3) mod n, if j= 0, (i−j−2) mod n, if iis even and 0 < j ≤min{n−5, t}, (i+j+ 3) mod n, if iis odd and 0 < j ≤min{n−5, t}, c(vi,j−1),otherwise. Ab-rainbow set is formed by the vertices s0,1, . . . , sn−2,n−1, s0,n−1. Figure 15 illustrates Theorem 13 for the graphs C3S3,C5S3and C7S3. Finally, we focus on the SVN corona of a cycle and a complete graph. DETERMINING THE b-CHROMATIC NUMBER OF SVN CORONAS 69 Figure 15: Optimal b-chromatic coloring of CnS3, for all n∈ {3,5,7}. Theorem 14. Let n > 2and tbe two positive integers. Then, ϕ(CnKt) =      t+ 2,if n≤t+ 1, n, if t+ 2 ≤n≤2t+ 3, 2t+ 3,otherwise. Proof. The case n > 2t+ 3 follows from Proposition 10. So, we assume that n≤2t+ 3. From Lemma 3 and (1), all the described values are upper bounds of the b-chromatic number. To see that they are reached, we define an appropriate b-chromatic coloring cof CnKtsatisfying (2) and (4). For each pair of non-negative integers i<nand j < t, we define c(vi,j ) as in the proof of Theorem 9, except for c(v0,n−2) = t, if n≤t+1. In this last case, a b-rainbow set is formed by the vertices s0,1, . . . , sn−2,n−1, v1,n−3, . . . , v1,t−1. Otherwise, if t+1 < n ≤2t+3, then a b-rainbow set is formed by s0,1, . . . , sn−2,n−1, s0,n−1. (Figure 16 illustrates the graphs C5K4and C6K4.) 5 SVN corona of stars In this section, we determine the b-chromatic number of the SVN corona of a star Sn, with n > 2, of set of vertices V(Sn) = {u0, . . . , un}, where u0 is the center, with a graph G∈G. As a preliminary result, we determine this number for the SVN corona SnH, for any arbitrary graph H, with ∆(H)+1<min{n, |V(H)|+ 2}+ϕ(H). Lemma 15. Let n > 2be a positive integer and let Hbe a graph of order t≥1such that ∆(H)+1< ϕ(SnH). Then, ϕ(SnH) = min{n, |V(H)|+ 2}+ϕ(H). DETERMINING THE b-CHROMATIC NUMBER OF SVN CORONAS 70 Figure 16: Optimal b-chromatic colorings of C5K4and C6K4. Proof. Since ∆(H)+1< ϕ(SnH), the vertex vi,j cannot be a b-vertex of SnH. Thus, every b-rainbow set of SnHis formed by a subset of vertices of the form si,j, together with either the vertex u0or a subset of vertices of the form v0,k. (Observe to this end that the remaining vertices ui, with 0< i < n, have degree one; and also that the vertex u0is not adjacent to any vertex of the form v0,k.) Then, the required result of being upper bound follows readily from Lemma 3 applied to the graph obtained after removing the vertices u0, v0,0, . . . , v0,|V(H)|−1from the graph SnH, together with the fact that every vertex si,j is adjacent to u0and every vertex v0,k. Now, in order to prove that the described upper bound is reached, we define an appropriate b-chromatic coloring cof SnH. To this end, let αn,|V(H)|= min{n, |V(H)|+ 2}and let c0:V(H)→ {0, . . . , ϕ(H)−1}be an optimal b-chromatic coloring of the graph H. Then, we define c(u0) = 0 and c(v0,k) = c0(vk), for every non-negative integer k < |V(H)|. In addition, for each positive integer i≤n, we define c(s0,i) = ϕ(H) + ((i−1) mod αn,|V(H)|) and c(ui) = ϕ(H)+(imod αn,|V(H)|). Furthermore, we have from Brooks’ Theorem [20] that every proper coloring of the vertices vi,0, . . . , vi,|V(H)|−1 requires at least either ∆(H) or ∆(H) + 1 distinct colors. These vertices can always be colored by using all the colors of the set {ϕ(H), . . . , ϕ(H) + αn,|V(H)|−1}\{c(s0,i), c(ui)}, together with, at most, the colors 0,...,∆(H)+ 2−nin case of being n≤∆(H) + 2. Figure 17 illustrates the previous result for the graphs SnP3, with n∈ {3,4,5}. DETERMINING THE b-CHROMATIC NUMBER OF SVN CORONAS 71 Figure 17: Optimal b-chromatic colorings of SnP3, for all n∈ {3,4,5}. In addition, the following lemma establishes a lower bound for the bchromatic number of the graph SnH, where His an arbitrary graph. Lemma 16. Let n > 2be a positive integer and let Hbe any graph. Then, ϕ(SnH)≥4. Proof. It is readily verified that χ(SnH) = χ(H) + 1. Thus, if χ(H)≥3, then the result follows straightforwardly from Lemma 1. So, we may assume that χ(H)∈ {1,2}. It is enough to prove the existence of a b-rainbow set of four b-vertices in both cases. If χ(H) = 1, then let cbe the proper 4-coloring of SnHthat is defined so that, for every non-negative integer i∈ {0,1,2}, it is c(s0,i) = i,c(ui) = (i+ 1) mod 3 and c(vi,0) = (i+ 2) mod 3. Any other vertex vis colored as c(v) = 3. Then, the set of vertices {s0,0, s0,1, s0,2, u0} is a b-rainbow set of SnH. Furthermore, if χ(H) = 2, then we may assume without loss of generality that v0,0and v0,1are adjacent. In addition, let c0:V(SnH)→ {0,1,2}be a proper 3-coloring of SnH. Then, let c00 be the proper 4-coloring of SnH that is defined so that, c00(s0,0) = c00(u1) = 3, and c00(v) = c0(v), otherwise. As such, the set of vertices {s0,0, s0,1, v0,0, v0,1}is a b-rainbow set of SnH. As an immediate consequence of the previous two results, the following theorem establishes the b-chromatic number of the SVN corona of a star with either a path, a cycle, or a complete graph. Theorem 17. Let n > 2,t > 2and t0be three positive integers. Then, ϕ(SnPt) =                    n+ 2,if (t= 3 and n∈ {3,4,5}, t= 4 and n∈ {3,4,5,6}, n+ 3,if n≤t+ 2 and t > 4, t+ 4,if (t= 3 and n > 5, t= 4 and n > 6, t+ 5,if n>t+ 2 >6. DETERMINING THE b-CHROMATIC NUMBER OF SVN CORONAS 72 ϕ(SnCt) =      n+ 2,if n= 4, n+ 3,if n≤t+ 2,with n6= 4, t+ 5,if n>t+ 2. and ϕ(SnKt0) = min{n, t0+ 2}+t0. Proof. The respective b-chromatic numbers of both graphs SnPtand SnCt follow straightforwardly from Proposition 2 and Lemmas 15 and 16 once it is observed that ∆(Pt) = ∆(Ct) = 2. Furthermore, we have from Proposition 2 and Lemma 15 that ϕ(SnKt0) = min{n, t0+ 2}+t0, whenever t0< min{n, t0+ 2}+t0. That is, it always holds. Now, we determine the b-chromatic number of the SVN corona of two stars. Theorem 18. Let n > 2and t > 2be two positive integers. Then, ϕ(SnSt) =      2n+ 1,if n≤t+1 2, t+ 2,if t+1 2< n < t, min{n, t + 3}+ 2,otherwise. Proof. Since ∆(St) = t, we have from Proposition 2 and Lemma 15 that ϕ(SnSt) = min{n, t + 3}+ 2, whenever t+ 1 <min{n, t + 3}+ 2. That is, whenever n≥t. So, we assume from now on that n<t. From Lemma 3 and (1), all the described values are upper bounds of the b-chromatic number under consideration. In order to see that they are reached, we define an appropriate b-chromatic coloring cof the graph SnSt. Here, we assume that V(St) = {v0, . . . , vt}, where v0is the center of the star. For each pair of positive integers i<nand j < t, the following two cases arise. First, if n≤t+1 2, then we define c(ui) = c(u0) = c(v0,0) = 2n,c(s0,i) = 2(i−1), c(v0,j) = 1 + ((j−1) mod n), c(vi,0)=2i−1 and c(vi,j ) = 2i+ ((j− 1) mod (2n−1)). (Figure 18 (left) illustrates the graph S3S6.) Second, if t+1 2<n<t, then we define c(ui) = c(u0) = c(v0,0) = 1, c(s0,i) = 2(i−1) mod (t+ 2), c(v0,j ) = 3, c(vi,0) = (2i−1) mod (t+ 2) and c(vi,j)=2i+ ((j−1) mod (t+ 2)). (Figure 18 (right) illustrates the graph S3S4.) DETERMINING THE b-CHROMATIC NUMBER OF SVN CORONAS 73 Figure 18: Optimal b-chromatic colorings of S3S6and S3S4. 6 SVN corona of complete graphs In this section, we study the b-chromatic number of the SVN corona KnG of a complete graph Knof set of vertices V(Kn) = {u0, . . . , un−1}and a graph G∈G, whenever m(KnG)≤n+2. Here, we assume that n > 1. Otherwise, K1G=K1. The following result establishes a lower bound for a general graph K2H. Lemma 19. Let Hbe a non-empty graph. Then, ϕ(K2H)≥ϕ(H)+1. Proof. Let c:V(H)→ {0, . . . , ϕ(H)−1}be a b-chromatic coloring of the graph H. If V(H) = {v0, . . . , vt−1}, then we define the b-chromatic coloring c0of the graph GHsuch that c0(u0) = c0(u1) = 0, c0(s0,1) = ϕ(H) and c0(vi,j) = c(vj), for all i∈ {0,1}and j < t. Hence, ϕ(K2H)≥ϕ(H)+1. Figure 19, together with Proposition 2, shows that the lower bound described in the previous lemma is tight, but the equality does not hold in general. It is so that ϕ(K2P3) = 2 = ϕ(P3) + 1, but ϕ(K2P4) = 4 >3 = ϕ(P4) + 1. We study separately each one of the mentioned graphs KnG, with G∈G. Firstly, we determine the b-chromatic number of the SVN corona KnPtin case of being m(KnPt)≤n+ 2. From Lemma 3 and (1), it is equivalent to say that either n∈ {2,3,4}or n≥2t+ 1. DETERMINING THE b-CHROMATIC NUMBER OF SVN CORONAS 74 Figure 19: Optimal b-chromatic colorings of K2P3and K2P4. Theorem 20. Let n > 1and t > 2be two positive integers. Then, ϕ(KnPt) =                n+ 1,if (n= 2 and t= 3, n≥7and t= 3, n+ 2,if      n= 2 and t > 3, n∈ {3,4}, n≥2t+ 1 >7. Proof. The case n= 3 follows from Theorem 11. So, we assume that n6= 3. Except for the case (n, t) = (7,3), all the described values coincide with m(KnPt) and hence, from Lemma 3, they are upper bounds of the bchromatic number under consideration. Proposition 2 and Lemma 19 imply that this upper bound is reached in case of being n= 2 and t6= 4. In addition, Figure 19 (right) illustrates the case t= 4. Further, even if m(K7P3) = 9, this lower bound is not reached, because every b-rainbow set of a b-chromatic coloring of K7P3with nine colors would only contain non-adjacent vertices of the form si,j or vk,1. A simple study of cases enables us to ensure that this condition is not feasible and hence, ϕ(K7P3)≤8. This new bound is indeed reached, as we prove later for the case n≥7 and t= 3. In order to prove that the remaining values are reached, we define an appropriate b-chromatic coloring cof the graph KnPtsuch that c(ui) = imod m(KnG), for every non-negative integer i<n. In addition, for every non-negative integers i, j < n, with i<j, and k < t, the following cases arise. Here, we assume that Pt=hv0, . . . , vt−1i. First, if n= 4, then c(si,j) = ((i−1) mod 4,if j=i+ 1, 4 + i, otherwise. DETERMINING THE b-CHROMATIC NUMBER OF SVN CORONAS 75 In addition, c(vi,j) =                4,if (i, j)∈ {(1,1),(3,1)}, 5,if (i, j)∈ {(0,1),(2,1)}, i, if j= 2, (i+ 1) mod 4,if j= 0, c(vi,j−2),otherwise. (Figure 20 illustrates the graph K4P3.) Figure 20: Optimal b-chromatic coloring of K4P3. Second, if n≥7 and t= 3, then c(si,j )=(i+j+ 1) mod (n+ 1), whenever nis odd. Otherwise, if nis even, then, for each positive integer h≤n 2, we define c(si,i+h) =          (i−2) mod (n+ 1),if h= 1, i+n−h 2mod (n+ 1),if 1 < h < n 2and his even , i−h−1 2mod (n+ 1),if 1 < h < n 2and his odd , i+ 1,if i<h=n 2. In addition, we define c(vi,k) =      c(ui),if k= 1, (2i+ 1) mod (n+ 1),if nis odd and k∈ {0,2}, c(si−1,i+1),otherwise. According to this definition of the map c, we have that, if nis odd, then a b-rainbow set is formed by the vertices v0,1, . . . , vn,1, vn−1 2,2. DETERMINING THE b-CHROMATIC NUMBER OF SVN CORONAS 76 Otherwise, if nis even, then a b-rainbow set is formed by the vertices v0,1, v0,2, . . . , vn 2−1,1, vn 2−1,2, vn 2,1. (Figure 21 illustrates the graphs K8P3 and K9P3.) Figure 21: Optimal b-chromatic colorings of K8P3and K9P3. Finally, if n≥2t+1 >7, then we define the map cas in the previous case, except for c(vi,k) =                    n+ 1,if            nis even and (i6=n 2and k∈ {0,3}, (i, k) = n 2,1, nis odd and (i6=n−1 2and k= 2, i=n−1 2and k∈ {0,3}, c(vi,j−3),if j∈ {4,5}, c(vi,k−2),otherwise. Ab-rainbow set is formed by the same b-vertices of the previous case, together with vn 2,1, if nis even, and v0,2, if nis odd. (Figure 22 illustrates the graphs K8P4and K9P4.) The next graph to study is the SVN corona KnCtsuch that m(KnCt)≤ n+ 2. From Lemma 3 and (1), it is equivalent to say that either n∈ {2,3,4} or n≥2t+ 1. DETERMINING THE b-CHROMATIC NUMBER OF SVN CORONAS 77 Figure 22: Optimal b-chromatic colorings of K8P4and K9P4. Theorem 21. Let n > 1and t > 2be two positive integers. Then, ϕ(KnCt) =                n+ 1,if ((n, t) = (2,4), n≥9and t= 4, n+ 2,if      n= 2 and t6= 4, n∈ {3,4}, n≥2t+ 1 and t6= 4. Proof. The case n= 3 follows from Theorem 12. In addition, since m(K2 Ct) = 4, the case n= 2 and t6= 4 follows from Lemmas 3 and 19, together with Proposition 2. Moreover, it is readily verified the non-existence of a b-rainbow set of K2C4formed by four distinct b-vertices. Thus, the same mentioned results imply that ϕ(K2C4) = 3. Now, we focus on the case n≥2t+ 1, for which Lemma 3 implies that ϕ(KnC4)≤m(KnC4) = n+ 2. To prove that this upper bound is not reached, we suppose the existence of an (n+ 2)-coloring of KnC4. If vi0,j0 were a vertex of a b-rainbow set of KnC4, for some i0< n and j0<4, then the four vertices vi0,0, vi0,1, vi0,2and vi0,3would be colored by at most three colors. One of them would be the color c(ui0), so that no vertex si0,k belongs to the b-rainbow set under consideration. Since cis a proper coloring, it would be c(vi0,k) = c(vi0,(k+2) mod 4), for some k < 4, and hence, from the mentioned four vertices, only the vertex vi0,j would be part of the b-rainbow set. It contradicts the case n > 9, for which only vertices vi,j belong to the b-rainbow set, so that the latter could only be formed by nvertices at most. DETERMINING THE b-CHROMATIC NUMBER OF SVN CORONAS 84 [11] C. Guo, M. Newman, On the b-chromatic number of Cartesian products, Discrete Appl. Math.,239 (2018), 82–93. [12] A. S. Afrose, S. J. Fathima, b-coloring of the product of paths and cycles, Int. J. Math. Trends Techn.,66 (2020), 105–109. [13] M. Jakovac, I. Peterin, On the b-chromatic number of some graph products, Studia Sci. Math. Hungar.,49 (2012), 156–169. [14] I. Koch, I. Peterin, The b-chromatic index of direct product of graphs, Discrete Appl. Math.,190/191 (2015), 109–117. [15] S. F. Raj, T. Kavaskar, On two conjectures on b-coloring of graph products, Studia Sci. Math. Hungar.,54 (2017), 141–149. [16] C. Linhares, L. Sampaio, A. Silva, On the b-continuity of the lexicographic product of graphs, . Graphs Combin.,33 (2017), 1165–1180. [17] J. Vernold Vivin, M. Venkatachalam, The b-chromatic number of corona graphs, Util. Math.,8(2012), 299–307. [18] T. Pathinathan, A. A. Mary, D. Bhuvaneswari, b-chromatic number of subdivision edge and vertex corona, Int. J. Comput. Algorithm,3(2014), 44–47. [19] X. Liu, P. Lu, Spectra of subdivision-vertex and subdivision-edge neighbourhood coronae, Linear Algebra Appl.,438 (2013), 3547–3559. [20] R. L. Brooks, On coloring the nodes of a network, Proc. Cambridge Philos. Soc.,37 (1941), 194–197. [21] D. Vijayalakshmi, Chromatic number of central graph of ladder graph and complete graph, Kong. Res. J.,1(2014), 27-28. [22] A. Jeeva , R. Selvakumar, The b-chromatic number of subdivision graph of complete graph, Int. J. Pure Appl. Math.,113 (2017), 185–191. RA´ UL M. FALC ´ ON, Department of Applied Mathematics I, Universidad de Sevilla, Avenida Reina Mercedes 4 A, 41012, Sevilla, Spain. Email: [email protected] M. VENKATACHALAM, Department of Mathematics, Kongunadu Arts and Science College, Coimbatore - 641 029, Tamil Nadu, India. Email: venk[email protected] S. JULIE MARGARET, Department of Mathematics, Kongunadu Arts and Science College, Coimbatore - 641 029, Tamil Nadu, India. Email: [email protected]