EUROPEAN JOURNAL OF PURE AND APPLIED MATHEMATICS 2025, Vol. 18, Issue 3, Article Number 6188 ISSN 1307-5543 – ejpam.com Published by New York Business Global On a b-chromatic Sum of a Mycielskian of Paths Panupong Vichitkunakorn1,2, Wipawee Tangjai3,∗, Sittichai Chaiyakhot4, Rawit Sinthuket3 1 Division of Computational Science, Faculty of Science, Prince of Songkla University, Songkla, Thailand 2 Research Center in Mathematics and Statistics with Applications, Prince of Songkla University, Songkhla, Thailand 3 Department of Mathematics, Faculty of Science, Mahasarakham University, Maha Sarakham, Thailand 4 Department of Mathematics, Faculty of Science, Khon Kaen University, Khon Kaen, Thailand Abstract. A b-coloring of a graph G is a proper coloring such that there exists a vertex in each color class that is adjacent to at least one vertex in other color classes. The b-chromatic number of a graph G, denoted by φ(G), is the largest integer k such that G has a b-coloring with k colors. The b-chromatic sum of a graph G, denoted by φ′(G), is defined as the minimum sum of the colors c(v) of v for all v ∈ V where c is a b-coloring using φ(G) colors. In this work, we improve the bounds on the b-chromatic sum given by Lisna and Sunitha [1]. We give the b-chromatic sum of the Mycielskian of a path µ(Pn) when n = 7, 9 and n ≥ 16. For the case 10 ≤ n ≤ 15, we give bounds on φ′(µ(Pn)). 2020 Mathematics Subject Classifications: 05C15, 05C78, 05C76, 05C38, 05C69 Key Words and Phrases: b-coloring, b-chromatic number, b-dominating, b-chromatic sum, path, Mycielskian 1. Introduction For a graph G = (V,E) with a proper coloring c : V → {1, . . . , k}, we denote a color class of Ci = {v ∈ V : c(v) = i} for i = 1, . . . , k. For S ⊂ V , we denote c(S) = {c(s) : s ∈ S}. A vertex v is a b-dominating vertex of color class i if v is adjacent to a vertex from each color class j ̸= i. A b-coloring is a proper coloring where each color has a b-dominating vertex. R. W. Irving and D. F. Manlove [2] introduced the concept of the b-chromatic number of a graph G. The b-chromatic number φ(G) of a graph G is the largest positive integer k such that G admits a b-coloring. Many research on the ∗Corresponding author. DOI: https://doi.org/10.29020/nybg.ejpam.v18i3.6188 Email addresses: panupong.v@psu.ac.th (P. Vichitkunakorn) , wipawee.t@msu.ac.th (W. Tangjai) , 63010213002@msu.ac.th (R. Sinthuket) https://www.ejpam.com 1 Copyright: © 2025 The Author(s). (CC BY-NC 4.0) P. Vichitkunakorn et al. / Eur. J. Pure Appl. Math, 18 (3) (2025), 6188 2 of 13 b-chromatic number and its bounds have been studied [3–5]. A collection of results on the b-chromatic number appeared in [6]. The application of the b-chromatic number appears in data clustering [7]. In comparison to the well-known chromatic number, the idea of chromatic sum was originated in 1989 by Kubicka and Schwenk [8]. The chromatic sum had also gained more attention from its application in the resource allocation problem [9]. Later in 2015, Lisna and Sunitha [10] introduced the b-chromatic sum following the same structure as the chromatic sum. The b-chromatic sum of a graph G, denoted by φ′(G), is the minimum of ∑ v∈V c(v) over a b-coloring c giving the b-chromatic number. Many questions related to the b-chromatic sum are still widely open. The b-chromatic sum of only a few classes of graphs had been investigated. Some examples include paths, cycles, wheel graphs, complete graphs [11, 12]. For a graph G = (V,E) where V = {v1, v2, . . . , vn}, the Mycielskian or Mycielski graph µ(G) of G is a graph in which the vertex set consists of two copies of the vertices in G and a vertex u, i.e., V (µ(G)) = V ∪U ∪ {u} such that V = {v1, . . . , vn} and U = {u1, . . . , un} where ui is a copy of vi. For the edge set of µ(G), we keep the adjacency of the vertices in V ⊂ V (µ(G)) as in G, then join u to each vertex ui, for 1 ≤ i ≤ n, and join ui to each neighbor of vi in G. In 2011, Massimiliano et. al. [13] discussed the applications of Mycielski graphs in the multiprocessor task scheduling problem. In 2017, Lisna and Sunitha [1] gave an upper bound on the b-chromatic sum of a Mycielskian path µ(Pn). They stated that such a bound is the b-chromatic sum of µ(Pn) for n ≥ 2; however, we find that such results are a close upper bound on the b-chromatic sum of µ(Pn) when n = 7 or n ≥ 9. In this work, we improve such results and give the b-chromatic sum of µ(Pn) when n = 7, 9 or n ≥ 16 and give a lower bound and an upper bound when 10 ≤ n ≤ 15. 2. Preliminaries In this section, we present definitions and related results for the Mycielskian graph and the b-chromatic sum. Definition 1. ([14]). Let G be a graph with n vertices, where V (G) = {v1, v2, . . . , vn}. The Mycielskian or Mycielski graph µ(G) is a graph where V (µ(G)) = V (G)∪{u, u1, . . . , un} and E(µ(G)) = E(G) ∪ {uui : 1 ≤ i ≤ n} ∪ {uiv : 1 ≤ i ≤ n and v ∈ NG(vi)}. Let Un = {ui : 1 ≤ i ≤ n}. We partition V (µ(Pn)) according to the definition of the Mycielskian into {V (Pn), Un, {u}} as shown in Figure 1. Theorem 1 provides the maximum number of colors that µ(Pn) admit a b-coloring. We note that for a graph G and a coloring c to admit a b-chromatic number, there must be at least φ(G) b-dominating vertices. Thus, G has at least φ(G) vertices with φ(G) − 1 degree. P. Vichitkunakorn et al. / Eur. J. Pure Appl. Math, 18 (3) (2025), 6188 3 of 13 u u1 u2 u3 u4 u5 . . . un v1 v2 v3 v4 v5 · · · vn Figure 1: The graph of µ(Pn) Theorem 1. ([15]). The b-chromatic number of Mycielskian path µ(Pn) is φ(µ(Pn)) =  3 if 2 ≤ n ≤ 4, 4 if 5 ≤ n ≤ 7, 5 if n ≥ 8. Lisna and Sunitha [1] provided the following results. We note that Theorem 3 was originally stated as the exact value of the b-chromatic sum φ′(µ(Pn)). However, the proof assumes that a b-coloring cn yielding the b-chromatic sum of µ(Pn) must be obtained from a b-coloring cn−1 yielding the b-chromatic sum of µ(Pn−1) for n ≥ 9. However, this assumption does not always hold. So, the b-colorings provided in the proof only give an upper bound on φ′(µ(Pn)). The results for small values of n, except for n = 7, are valid as listed in Theorem 2. Theorem 2. ([1]). The b-chromatic sum of Mycielskian of path µ(Pn) is φ′(µ(Pn)) =  4 if n = 1, 3 + 2(⌈n2 ⌉+ 2⌊n2 ⌋) if n = 2, 3, 4, 6 + n+ 3⌊n−1 2 ⌋+ 2⌈n−1 2 ⌉ if n = 5, 6, 44 if n = 8. Theorem 3. ([1]). The b-chromatic sum of Mycielskian of path µ(Pn) is as follows φ′(µ(Pn)) ≤  28 if n = 7, 48 if n = 9, 45 + 4⌈n−8 2 ⌉+ 2⌊n−8 2 ⌋ if n ≥ 10. For n ≥ 10, Theorem 3 can be restated as φ′(µ(Pn)) ≤ { 3n+ 21 if n is even, 3n+ 22 if n is odd. In this work, we improve Theorem 3 by giving the value of the b-chromatic sum in the case of n = 7, 9 and n ≥ 16 and we lower the upper bound given by Lisna and Sunitha in the case when 10 ≤ n ≤ 15. We also give an explicit coloring giving the sum of the colors. To be more precise, we show that φ′(µ(P7)) = 27, φ′(µ(P9)) = 46, 3n+ 18 ≤ φ′(µ(Pn)) ≤ 3n+ 19 for 10 ≤ n ≤ 15, and φ′(µ(Pn)) = 3n+ 19 for n ≥ 16. P. Vichitkunakorn et al. / Eur. J. Pure Appl. Math, 18 (3) (2025), 6188 4 of 13 3. Main results In [1], they gave the b-chromatic sum of µ(P8) by giving a b-coloring that achieves such value and showed the minimality by counting the number of vertices in each color class. Then they adjusted such coloring to be cn for n ≥ 9. However, the adjusted coloring does not yield the b-chromatic sum. In this section, we improve the result of Lisna and Sunitha [1]. We give b-chromatic sum of µ(Pn) when n = 7, 9 and n ≥ 16, and its bound when 10 ≤ n ≤ 15. We give the b-chromatic sum of µ(P7) in Theorem 4. Then we investigate several properties of µ(Pn) and its colorings that lead to the bound and the exact value of the b-chromatic sum as mentioned. Theorem 4. φ′(µ(P7)) = 27. Proof. By Theorem 1, we have φ(µ(P7)) = 4. Let c : V (µ(P7)) → {1, 2, 3, 4} be a b-coloring giving a b-chromatic number of µ(P7). We first show that there are at most 7 vertices with color 1. Suppose to the contrary that there exists the b-coloring giving a b-chromatic number with at least 8 vertices of color 1. There are at least three b-dominating vertices of colors other than 1. If c(u) = 1, then 1 /∈ c(U7). Hence |C1| ≤ ⌈ |V (P7)| 2 ⌉ + 1 = 5 is a contradiction. Now, we suppose that c(u) ̸= 1. Since there are at most 4 vertices of color 1 in V (P7), there are at least 4 vertices of color 1 in U7. If |C1 ∩ U7| = 4, then |C1 ∩ V (P7)| = 4. It follows that C1 = {v1, v3, v5, v7, u1, u3, u5, u7}. Hence, the vertex u is the only possible b-dominating vertex of color other than 1, which is not possible. For j = 1, 2, 3, if |C1 ∩ U7| = 4 + j, then |NP7(C1 ∩ U7)| ≥ |C1 ∩ U7| ≥ 4 + j. Thus, |V (P7) \Nµ(P7)(C1 ∩ U7)| ≤ 3 − j which is not enough to complete the color 1. Therefore |C1| ≤ 7. Next, we show that if |C4| = 1, then |C3| ≥ 2. Suppose to the contrary that |C3| = 1. Thus, the vertices with color 3 and 4 are both b-dominating vertices and are adjacent. Since µ(P7) is triangle-free, there is no b-dominating vertices for colors 1 and 2, a contradiction. Thus, if |C4| = 1, then |C3| ≥ 2. If |C4| = 1, then ∑ v∈V (µ(P7)) c(v) ≥ 4|C4|+ 3|C3|+ 2|C2|+ |C1| ≥ 4 · 1 + 3 · 2 + 2 · 5 + 1 · 7 = 27. If |C4| ≥ 2, then ∑ v∈V (µ(P7)) c(v) ≥ 4 · 2 + 3 · 1 + 2 · 5 + 1 · 7 = 28. Thus, φ′(µ(P7)) ≥ 27. Next, we give a b-coloring giving the b-chromatic sum of µ(Pn), as shown in Figure 2. For the rest of the paper, each bold vertex in a figure represents a b-dominating vertex P. Vichitkunakorn et al. / Eur. J. Pure Appl. Math, 18 (3) (2025), 6188 5 of 13 and the number above each vertex represents its assigned color. Define c7 : V (µ(P7)) → {1, 2, 3, 4} by c7(x) =  1 if x = v1, v3, u1, u3, u5, u6, u7, 2 if x = v2, v4, v7, u2, u4, 3 if x = v6, u, 4 if x = v5. (1) We can see that c7 is a b-coloring and φ′(µ(P7)) = 27. u 3 u1 1 u2 2 u3 1 u4 2 u5 1 u6 1 u7 1 v1 1 v2 2 v3 1 v4 2 v5 4 v6 3 v7 2 Figure 2: A b-coloring of µ(P7) with 4 colors Lemmas 1–5 give a structure of colors in a b-coloring giving the b-chromatic number. The structure will be used to determine the lower bound of the b-chromatic sum in Theorem 5. The idea of proof of Lemma 1 is extended from the calculation of φ′(µ(P8)) in [1]. Lemma 1. For a graph µ(Pn) where n ≥ 8 with a coloring cn giving b-chromatic number, the following properties hold: (i) the b-dominating vertices are in V (Pn) ∪ {u}, (ii) each color appears at least twice in V (Pn) ∪ Un. Proof. (1) Let n ≥ 8. From φ(µ(Pn)) = 5, the b-vertices have degree 4 in µ(Pn). Since ui has degree 3 in µ(Pn) for 1 ≤ i ≤ n, it follows that the b-vertices must be in V (Pn) ∪ {u}. (2) Suppose there is only one vertex x ∈ V (Pn)∪Un of color 1. Since the b-dominating vertices of colors 2, 3, 4, 5 are in V (Pn) ∪ {u}, at least three of them are in V (Pn). These three vertices must be all adjacent to x. However, x has at most two neighbors in V (Pn), a contradiction. Lemma 2. For a graph µ(Pn) where n ≥ 8 with a coloring cn giving the b-chromatic number, the following properties hold: (i) |cn(V (Pn))| = 5, (ii) |Ccn(u)| ≤ ⌈ n 2 ⌉ + 1. P. Vichitkunakorn et al. / Eur. J. Pure Appl. Math, 18 (3) (2025), 6188 6 of 13 Proof. (1) We note that cn(u) does not appear in Un. For a vertex in V (Pn) to be a b- dominating vertex, the color cn(u) must appear in V (Pn). Thus |cn(V (Pn))| = 5. (2) Since vi and vi+1 in V (Pn) cannot get the same color, there are at most ⌈ n 2 ⌉ vertices in V (Pn) with color cn(u). Since cn(u) does not appear in Un, we have |Ccn(u)| ≤ ⌈ n 2 ⌉ +1. Lemma 3. For a graph µ(Pn) where n ≥ 8 with a coloring cn giving the b-chromatic number, if there exists m ∈ {1, 2, 3, 4, 5} where |Cm| = 2, then |Ci| ≥ 3 for i ̸= m. Proof. By Theorem 1, we have φ(µ(Pn)) = 5. Without loss of generality, we suppose |C5| = 2. By Lemma 1, we have cn(u) ̸= 5. Hence 5 ̸∈ {cn(u)} ∪ {cn(ui), cn(vi) : i = 1, n}. Let k ∈ {2, . . . , n − 1} be such that vk is the b-dominating vertex of color 5 and j ∈ {1, . . . , n} be such that 5 ∈ {cn(uj), cn(vj)}. At least one of vk−1 and vk+1 is a b- vertex. Suppose that vk+1 is a b-dominating vertex of color 4, and cn(vk−1) = 3 (see Figure 3). It follows that cn(vk+2) = 3 and cn({uk−1, uk+1}) = cn({uk, uk+2}) = {1, 2}. Thus cn(u) ∈ {3, 4}, says cn(u) = 3. So |C3| ≥ 3. Since the vertices in Un are not b-dominating vertices, there exists b-dominating vertices of colors 1 and 2 in V (Pn). Thus |C1| ≥ 3 and |C2| ≥ 3. There are 2 vertices of color 5. Since vk−1 and u cannot be a b-dominating vertex of color 1 nor 2, we have j ∈ {2, 3, . . . , n − 1} and the vertices vj−1 and vj+1 are the b-dominating vertices of color 1 and 2. It remains 3 b-dominating vertices that have to be adjacent to a vertex of color 4 and they have no common neighbor. So, it requires at least 2 more vertices of color 4. Now |C4| ≥ 3. Therefore, |Ci| ≥ 3 for i = 1, . . . , 4. This completes the proof. u 3 uk−2 uk−1 1 uk 1 uk+1 2 uk+2 2 vk−2 vk−1 3 vk 5 vk+1 4 vk+2 3 Figure 3: A coloring in Lemma 3 For n ≥ 8, we consider a b-coloring cn giving the b-chromatic sum of µ(Pn). If |C5| = 2, then ∑ v∈V (µ(Pn)) cn(v) ≥ 5 · 2 + 4 · 3 + 3 · 3 + 2 · (2n− 7− |C1|) + |C1| = 4n− |C1|+ 17. If |C5| ≥ 3, then∑ v∈V (µ(Pn)) cn(v) ≥ 5 · 3 + 4 · 2 + 3 · 3 + 2 · (2n− 7− |C1|) + |C1| = 4n− |C1|+ 18. P. Vichitkunakorn et al. / Eur. J. Pure Appl. Math, 18 (3) (2025), 6188 7 of 13 Lemma 4. For n ≥ 8, let cn be a coloring giving the b-chromatic number of µ(Pn). If there exists m such that |Cm| = 2, then c(u) ̸= m and |Cc(u)| ≥ 4. Proof. Let m be such that |Cm| = 2. From Lemma 1, we have c(u) ̸= m. Without loss of generality, we suppose |C5| = 2 and c(u) = 3. By Lemma 3, we have |Ck| ≥ 3 for k ̸= 5. Next, we suppose to the contrary that |C3| = 3. We see that 3 ̸∈ cn(Un). Let vi, vj be such that cn(vi) = cn(vj) = 3. We have that NPn({vi, vj}) = {vi−1, vi+1, vj−1, vj+1} consists of b-dominating vertices of colors 1,2,4 and 5, says c(vj−1) = 5. Since |C5| = 2, either cn(u) = 5 or vi+1 and vj−1 are adjacent. In either case, we need 3 vertices of color 5 to complete the neighbors of the b-vertices, a contradiction. We note that, by using Lemmas 1–4, a lower bound of φ′(µ(P8)) can be obtained from a configuration where |C5| = 2, |C4| = |C3| = 3. From Lemmas 2 and 4, c8(u) ∈ {1, 2} and 4 ≤ |Cc8(u)| ≤ ⌈ n 2 ⌉ + 1 = 5. So, |C2| = 4 and |C1| = 5 give the lowest sum. Hence,∑ v∈V (µ(P8)) c8(v) ≥ 5 · 2 + 4 · 3 + 3 · 3 + 2 · 4 + 1 · 5 = 44. Combined with the b-coloring provided by [1], it follows that φ′(µ(P8)) = 44, which aligns with the result in [1]. For n ≥ 9, Lemma 5 will give a better lower bound on the b-chromatic sum (if not exact) than using only Lemmas 1–4. Lemma 5. For n ≥ 9, let cn be a coloring giving the b-chromatic number of µ(Pn). There are at most n− 1 vertices of color 1. Proof. If u ∈ C1, then |C1| ≤ 1 + ⌈ n 2 ⌉ ≤ n− 1. Without loss of generality, we assume that u ∈ C2. Let vk be a b-dominating vertex of color 3 where 2 ≤ k ≤ n − 1. There is only one vertex in Nµ(Pn)(vk) = {vk−1, vk+1, uk−1, uk+1} with color 1. We consider two cases of positions of 1’s up to left-right reflection as in Figure 4. The X marked in all figures mentioned in this proof means that the color of such vertex cannot be 1. Let l = k − 2 and r = n − k. We have l and r columns that possibly contain 1 on the left and right of vk, respectively. Case 1. cn(vk−1) = 1 or cn(vk+1) = 1. Without loss of generality, we suppose that cn(vk+1) = 1 as shown in Figure 4 (the left figure). The left side of vk contains at most l of 1’s when l is even, and l+1 of 1’s when l is odd. The right side of vk contains at most r of 1’s. Hence |C1| ≤ (l + 1) + r = n− 1. Case 2. cn(uk−1) = 1 or cn(uk+1) = 1. Without loss of generality, we suppose that cn(uk+1) = 1 as shown in Figure 4 (the right figure). There are at most l+ 1 and r of 1’s on the left and right of vk, respectively. In this case, it is possible that cn(uk) = 1. Hence |C1| ≤ (l+1)+ r+1 = n. Suppose to a contrary that |C1| = n. It implies that there are exactly l+1 of 1’s on the left of vk. Thus l is odd and the positions of 1’s must appear as in Figure 5. It follows that there are no b-dominating vertex of color 4 and 5 in these columns. Thus, the b-dominating vertices of 4 and 5 are on the right side of vk. Since there are exactly r vertices of color 1 on the P. Vichitkunakorn et al. / Eur. J. Pure Appl. Math, 18 (3) (2025), 6188 8 of 13 right of vk, there is only one vertex that can possibly be the b-dominating vertex of both colors 4 and 5, as shown in Figure 6. This leads to a contradiction. Therefore |C1| ≤ n− 1. uk−1 X uk X uk+1 X uk+2 X vk−1 X vk 3 vk+1 1 vk+2 X uk−1 X uk uk+1 1 uk+2 vk−1 X vk 3 vk+1 X vk+2 X Figure 4: Positions of 1’s in each type of b-dominating vertex positioning u1 1 u2 X u3 1 u4 X · · · uk−2 1 v1 1 v2 X v3 1 v4 X · · · vk−2 1 odd ℓ Figure 5: Positions of 1’s on the left side of a b-dominating vertex vk 1 · · · 1 1 X 1 · · · X 1 X · · · X X X 1 · · · X 1 r Figure 6: Positions of 1’s on the right side of a b-dominating vertex The following theorem gives a lower bound on φ′(µ(Pn)) for n ≥ 9. Theorem 5. For n ≥ 9, φ′(µ(Pn)) ≥ { 3n+ 18 for 10 ≤ n ≤ 15, 3n+ 19 for n = 9 or n ≥ 16. Proof. Let cn : V (µ(Pn)) → {1, 2, 3, 4, 5} be a b-coloring of µ(Pn) for n ≥ 9. In this proof, we assume the minimality of the sum of the colors by maximizing the number of vertices with smaller colors and minimizing the number of vertices with larger colors. Case 1. cn(u) ∈ {3, 4, 5}. By Lemmas 1, 3 and 4, we have that |C3| ≥ 3, |C4| ≥ 3, |C5| ≥ 3, or |Ci| ≥ 2, |Cj | ≥ 3, |Ck| ≥ 4 where {i, j, k} = {3, 4, 5}. Hence, the minimum of 5|C5| + 4|C4| + 3|C3| is P. Vichitkunakorn et al. / Eur. J. Pure Appl. Math, 18 (3) (2025), 6188 9 of 13 5 · 2 + 4 · 3 + 3 · 4 = 34. By Lemma 5, to achieve the minimum sum, we assume the maximality of |C1| = n− 1. Then, we have |C2| = n− 7. Thus,∑ w∈V (µ(Pn)) cn(w) ≥ 34 + 2(n− 7) + (n− 1) = 3n+ 19. Case 2. cn(u) = 1. By Lemma 2, we have |C1| ≤ ⌈ n 2 ⌉ + 1. We assume the maximum value of |C1| and minimum values of |C3|, |C4| and |C5|. We have that |C1| = ⌈ n 2 ⌉ + 1, |C3| = |C4| = 3 and |C5| = 2. Hence, |C2| = n+ ⌊ n 2 ⌋ − 8. It follows that∑ w∈V (µ(Pn)) cn(w) ≥ 5 · 2 + 4 · 3 + 3 · 3 + 2 ( n+ ⌊n 2 ⌋ − 8 ) + (⌈n 2 ⌉ + 1 ) = 3n+ ⌊n 2 ⌋ + 16 > 3n+ 19. Case 3. cn(u) = 2. We first assume the maximum value of |C1| and minimum values of |C3|, |C4| and |C5|. We have that |C1| = n − 1, |C3| = |C4| = 3 and |C5| = 2. It follows that |C2| = n − 6. Hence, φ′(µ(Pn)) ≥ 5 · 2 + 4 · 3 + 3 · 3 + 2(n− 6) + (n− 1) = 3n+ 18. Next, we consider two special subcases. • When n = 9, it is not possible that |C1| = 8 since Lemma 4 gives an extra condition that |C2| ≥ 4, |C3| = |C4| = 3 and |C5| = 2 are the lowest possible values. Thus |C1| = 7 and |C2| = 4. Hence, φ′(µ(P9)) ≥ 5 · 2 + 4 · 3 + 3 · 3 + 2 · 4 + 1 · 7 = 46 = 3n+ 19. • When n ≥ 16, we assume |C1| = n− 1 and |C4| = 3 and |C5| = 2. From Lemma 2, we assume |C2| = ⌈ n 2 ⌉ + 1. It follows that |C3| = (2n+ 1)− 2− 3− (⌈n 2 ⌉ + 1 ) − (n− 1) = ⌊n 2 ⌋ − 4. We have ∑ w∈V (µ(Pn)) cn(w) ≥ 5 · 2 + 4 · 3 + 3 (⌊n 2 ⌋ − 4 ) + 2 (⌈n 2 ⌉ + 1 ) + (n− 1) ≥ 3n+ ⌊n 2 ⌋ + 11 ≥ 3n+ 19. From the three cases, we can conclude that φ′(µ(Pn)) ≥ 3n+ 18 for 10 ≤ n ≤ 15, and φ′(µ(Pn)) ≥ 3n+ 19 for n = 9 or n ≥ 16. The following remark is obtained from the proof of Theorem 5. P. Vichitkunakorn et al. / Eur. J. Pure Appl. Math, 18 (3) (2025), 6188 10 of 13 u 2 u1 1 u2 1 u3 5 u4 1 u5 3 u6 1 u7 1 u8 3 u9 4 v1 2 v2 3 v3 4 v4 1 v5 2 v6 4 v7 5 v8 2 v9 1 Figure 7: A b-coloring of µ(P9) u 2 u1 1 u2 1 u3 5 u4 1 u5 3 u6 1 u7 1 u8 3 u9 1 u10 4 v1 2 v2 3 v3 4 v4 1 v5 2 v6 5 v7 4 v8 2 v9 1 v10 2 Figure 8: A b-coloring of µ(P10) Remark 1. For 10 ≤ n ≤ 15, if φ′(µ(Pn)) = 3n+18, then cn(u) = 2, |C1| = n−1, |C2| = n− 6, |C3| = |C4| = 3 and |C5| = 2. Theorem 6. For n ≥ 9, φ′(µ(Pn)) ≤ 3n+ 19. Proof. We define b-colorings c9, c10 and c11 of µ(P9), µ(P10) and µ(P11) as in Figures 7, 8 and 9, respectively. We see that ∑ v∈V (µ(Pn)) cn(v) = 3n + 19 for 9 ≤ n ≤ 11. Thus φ′(µ(Pn)) ≤ 3n+ 19 for 9 ≤ n ≤ 11. For an even n ≥ 12, we define the proper coloring cn : V (µ(Pn)) → {1, 2, 3, 4, 5} by cn(xi) =  c11(xi−1) if xi ∈ {ui, vi} for i = 2, . . . , 12, 1 if xi = u1 or xi ∈ {ui, vi} for even i ≥ 14, 2 if xi = v1 or xi ∈ {ui, vi} for odd i ≥ 13. For an odd n ≥ 13, we define the proper coloring cn : V (µ(Pn)) → {1, 2, 3, 4, 5} by cn(xi) =  c11(xi) if xi ∈ {ui, vi} for i = 1, . . . , 11, 2 if xi ∈ {ui, vi} for even i ≥ 12, 1 if xi ∈ {ui, vi} for odd i ≥ 13. It is clear that cn is a b-coloring and that ∑ x∈V (µ(Pn)) cn(x) = 3n+19 for n ≥ 12. Hence, φ′(µ(Pn)) ≤ 3n+ 19 for n ≥ 12. Therefore, φ′(µ(Pn)) ≤ 3n+ 19 for n ≥ 9. The following theorem is a direct result from Theorems 4, 5 and 6. P. Vichitkunakorn et al. / Eur. J. Pure Appl. Math, 18 (3) (2025), 6188 11 of 13 u 3 u1 1 u2 1 u3 5 u4 1 u5 2 u6 1 u7 1 u8 2 u9 1 u10 4 u11 1 v1 3 v2 2 v3 4 v4 1 v5 3 v6 5 v7 4 v8 3 v9 1 v10 2 v11 1 Figure 9: A b-coloring of µ(P11) Theorem 7. The followings hold: • φ′(µ(P7) = 27, • 3n+ 18 ≤ φ′(µ(Pn)) ≤ 3n+ 19 for 10 ≤ n ≤ 15, • φ′(µ(Pn)) = 3n+ 19 for n = 9 or n ≥ 16. 4. Conclusion and Discussion In the work of Lisna and Sunitha [1], they gave the b-coloring giving a b-chromatic sum of µ(P8), i.e. φ′(µ(P8)) = 44. Then they extended and adjusted such coloring to a b-coloring of µ(Pn) for n ≥ 9. Even though this extended coloring is a b-coloring, the sum of the colors may not be minimum. One of the main reason is because the number of color 1 in the extended coloring is less than the maximum number of color 1 as shown in Lemma 5. In this work, we give a b-coloring giving a lower b-chromatic sum. We also analyze a lower bound. Our method relies heavily on Lemma 5 by setting |C1| = n − 1 when computing the lower bound. The proof of Lemma 5 also describes valid configurations of color 1. As a result, we give lower and upper bounds on the b-chromatic sum of a Mycielskian path µ(Pn) for 10 ≤ n ≤ 15. We get the exact value of the b-chromatic sum φ′(µ(P7)) = 27 and φ′(µ(Pn)) = 3n + 19 when n = 9 or n ≥ 16. Table 1 compares the results given by Lisna and Sunitha [1] and the results in this paper. From the table, we propose the following conjecture. Conjecture 1. For n ≥ 9, we have φ′(µ(Pn)) = 3n+ 19. A vast area of research related to the b-chromatic sum still remains open. The b- chromatic sum of only a few specific classes of graphs such as paths, cycles, stars and certain classes of Mycielskian graphs had been studied. One of the intuitive problems is to find a bound on the b-chromatic sum for more generalized classes of graphs, for example, regular graphs and connected graphs. Another possible question is to find an efficient algorithm to compute the b-chromatic sum of a graph. P. Vichitkunakorn et al. / Eur. J. Pure Appl. Math, 18 (3) (2025), 6188 12 of 13 n Our results [1] Lower bound Upper bound Upper bound 7 27 27 28 8 44 44 44 9 3n+ 19 3n+ 19 3n+ 21 10, 12, 14 3n+ 18 3n+ 19 3n+ 21 11, 13, 15 3n+ 18 3n+ 19 3n+ 22 even n ≥ 16 3n+ 19 3n+ 19 3n+ 21 odd n ≥ 17 3n+ 19 3n+ 19 3n+ 22 Table 1: Bounds on φ′(µ(Pn)) for n ≥ 7 Acknowledgements We dedicate this work to the memory of Sittichai Chaiyakhot, a young mathematician whose passion, curiosity, and dedication laid the foundation for this project. His commit- ment to discovery continues to inspire us. Though he is no longer with us, his contribution remains at the heart of this research. We are deeply grateful for his work and honor his memory by delivering his discovery. This research project was financially supported by Mahasarakham University. References [1] P. C. Lisna and M. S. Sunitha. b-chromatic sum of Mycielskian of paths. Electronic Notes in Discrete Mathematics, 63:407–414, 2017. [2] R. W. Irving and D. F. Manlove. The b-chromatic number of a graph. Discrete Applied Mathematics, 91(1-3):127–141, 1999. [3] M. Alkhateeb and A. Kohl. Upper bounds on the b-chromatic number and results for restricted graph classes. Discuss. Math. Graph Theory, 31:709–735, 2011. [4] C. Guo and M. Newman. On the b-chromatic number of cartesian products. Discrete Applied Mathematics, 239:82–93, 2018. [5] K. Kouider and M. Zaker. Bounds for the b-chromatic number of some families of graphs. Discrete Mathematics, 306:617–623, 2006. [6] M. Jakovac and I. Peterin. The b-chromatic number and related topics—a survey. Discrete Applied Mathematics, 235:184–201, 2018. [7] H. Elghazel, H. Kheddouci, V. Deslandres, and A. Dussauchoy. A graph b-coloring framework for data clustering. Journal of Mathematical Modelling and Algorithms, 7:389–423, 2008. [8] E. Kubicka and A. J. Schwenk. An introduction to chromatic sums. In Proceedings of the 17th Conference on ACM Annual Computer Science Conference, CSC ’89, page 39–45, New York, NY, USA, 1989. Association for Computing Machinery. [9] A. Bar-Noy, M. Bellare, M. M. Halldórsson, H. Shachnai, and T. Tamir. On chromatic sums and distributed resource allocation. Information and Computation, 140(2):183– 202, 1998. P. Vichitkunakorn et al. / Eur. J. Pure Appl. Math, 18 (3) (2025), 6188 13 of 13 [10] P. C. Lisna and M. S. Sunitha. b-chromatic sum of a graph. Discrete Mathematics, Algorithms and Applications, 7(3):1550040, 2015. [11] P. C. Lisna and M. S. Sunitha. b-chromatic sum of a graph. Discrete Mathematics, Algorithms and Applications, 07(04):1550040, 2015. [12] P. C. Lisna and M. S. Sunitha. On the b-chromatic sum of Mycielskian of Km,n,Kn and Cn. Journal of Interconnection Networks, 20(02):2050007, 2020. [13] M. Caramia and P. Dell’Olmo. A lower bound on the chromatic number of mycielski graphs. Discrete Mathematics, 235(1-3):79–86, 2001. [14] J. Mycielski. Sur le coloriage des graphs. In Colloquium Mathematicae, volume 3, pages 161–162, 1955. [15] P. C. Lisna and M. S. Sunitha. The b-chromatic number of Mycielskian of some graphs. International Journal of Convergence Computing, 2(1):23–40, 2016.