A star edge coloring of a graph \(G\) is a proper edge coloring in which every path or cycle on four vertices contains at least three distinct colors. The star edge chromatic number of \(G\), denoted by \(\chi^\prime_{\mathrm{st}}(G)\), is the minimum number of colors required for such a coloring. In this paper, we study the star edge chromatic number of several graph classes derived from the Knödel graph \(W_{\Delta,n}\). In particular, we determine bounds and exact values for \(\chi^\prime_{\mathrm{st}}(G)\) for the Knödel graph \(W_{\Delta,n}\), its middle graph \(M\!\left(W_{\Delta,n}\right)\), and its Mycielskian \(\mu\!\left(W_{\Delta,n}\right)\). Furthermore, we provide explicit constructions of star edge colorings that attain these values.
Graph coloring is a fundamental topic in graph theory and discrete mathematics. It provides a framework for assigning labels, or colors, to the vertices or edges of a graph under specified constraints. Such colorings capture important combinatorial properties and have applications in scheduling, frequency assignment, register allocation, and chemical and biological networks [2, 3, 5].
A simple graph \(G=(V,E)\) consists of a finite, nonempty vertex set \(V(G)\) and an edge set \(E(G)\) of unordered pairs of distinct vertices; that is, \[E(G) \subseteq \bigl\{\{u,v\} : u,v \in V(G),\ u \neq v \bigr\}.\] The term simple indicates that the graph contains no loops or multiple edges [5]. Throughout this paper, all graphs are assumed to be simple, finite, and undirected.
A basic problem in graph coloring is vertex coloring. A vertex coloring of \(G\) is a mapping \(c: V(G) \to C\), where \(C\) is a finite set of colors, such that adjacent vertices receive distinct colors. The minimum number of colors required is called the chromatic number of \(G\), denoted by \(\chi(G)\) [3, 5]. Determining \(\chi(G)\) is NP-hard in general, so considerable work has focused on bounds and exact values for special classes of graphs [5]. For example, the chromatic number is known for complete graphs, bipartite graphs, cycles, and planar graphs. In particular, the four-color theorem states that every planar graph satisfies \(\chi(G) \leq 4\) [5]. Vertex coloring has important applications in scheduling and resource allocation.
Another important variant is edge coloring. A proper edge coloring of \(G\) is a mapping \(c^\prime: E(G) \to C^\prime\) such that adjacent edges, that is, edges sharing a common endpoint, receive distinct colors. The minimum number of colors required is the edge chromatic number, denoted by \(\chi^\prime(G)\) [14]. A classical result of Vizing states that \[\chi^\prime(G) \in \{\Delta(G),\, \Delta(G)+1\},\] where \(\Delta(G)\) is the maximum degree of \(G\) [14]. Accordingly, graphs are classified as Class I or Class II. Edge coloring also arises naturally in scheduling problems where edges represent tasks requiring shared resources.
To impose stronger constraints, the notion of star coloring was introduced. A star coloring is a proper vertex coloring in which no path on four vertices, namely \(P_4\), is bi-colored [6]. Equivalently, every subgraph induced by two colors is a forest of stars. The minimum number of colors required is called the star chromatic number, denoted by \(\chi_s(G)\). Clearly, \(\chi_s(G) \geq \chi(G)\). Star coloring avoids short alternating color patterns and has applications in network design and parallel processing [6, 7, 9, 11, 12, 15, 1].
Similarly, star edge coloring extends this idea to edges. A star edge coloring of \(G\) is a proper edge coloring in which no path or cycle on four vertices is bi-colored [8]. The minimum number of colors required is called the star edge chromatic number, denoted by \(\chi^\prime_{\mathrm{st}}(G)\). Clearly, \[\chi^\prime_{\mathrm{st}}(G) \geq \chi^\prime(G).\] However, the gap between these parameters can be significant because of the stronger restriction. Exact values of \(\chi^\prime_{\mathrm{st}}(G)\) are known only for certain graph classes, including trees, cycles, bipartite graphs, and complete graphs. This concept also arises in frequency assignment problems, where avoiding short two-color patterns reduces interference [8, 4].
Among regular bipartite graphs, Knödel graphs form an important class. The Knödel graph \(W_{\Delta,n}\), introduced in 1975, is a \(\Delta\)-regular bipartite graph with \(2n\) vertices partitioned into \[X = \{(1,i) : 0 \leq i \leq n-1\}, \qquad Y = \{(2,i) : 0 \leq i \leq n-1\}.\] Each vertex \((1,i)\) is adjacent to \((2,(i + 2^k – 1) \bmod n)\) for \(0 \leq k \leq \Delta – 1\). These graphs are symmetric and vertex-transitive, and they play an important role in the study of interconnection networks [10]. Their regular and cyclic structure makes them suitable for investigating advanced coloring parameters.
In this paper, we investigate the star edge chromatic number of the Knödel graph \(W_{\Delta,n}\), its middle graph \(M\!\left(W_{\Delta,n}\right)\), and its Mycielskian \(\mu\!\left(W_{\Delta,n}\right)\). We establish bounds and exact values for \(\chi^\prime_{\mathrm{st}}(G)\) for these graph classes and provide explicit constructions that achieve these values.
This section presents the fundamental definitions, terminology, and graph constructions necessary for understanding the results that follow.
Definition 2.1([2, 3, 5]).A proper edge coloring of a graph \(G\) is a function \(f: E(G) \rightarrow C\), where \(C\) is a set of colors, such that if two edges \(e_1\) and \(e_2\) are adjacent, then \(f(e_1) \neq f(e_2)\).
Definition 2.2([8, 4]).A star edge coloring of \(G\) is a proper edge coloring in which every path or cycle of length four, that is, on four vertices, is not bi-colored. Equivalently, in a star edge coloring, there is no subgraph of \(G\) isomorphic to a path \(P_4\) or a cycle \(C_4\) whose edges are colored with only two colors. The star edge chromatic number of \(G\), denoted by \(\chi^\prime_{\mathrm{st}}(G)\), is the smallest positive integer \(k\) for which \(G\) admits a star edge coloring with \(k\) colors.
Definition 2.3([10]).The Knödel graph \(W_{\Delta,n}\) has the vertex set \[V(W_{\Delta,n}) = \{ (i,j) \mid i \in \{1,2\},\, 0 \leq j \leq n-1 \},\] and edge set \[E(W_{\Delta,n}) = \big\{\, (1,j)(2,(j+2^p-1) \bmod n) \mid 0 \leq j \leq n-1,\; 0 \leq p \leq \Delta-1 \,\big\}.\]
Thus, \(W_{\Delta,n}\) is a \(\Delta\)-regular bipartite graph on \(2n\) vertices, where each vertex in part \(1\) is adjacent to \(\Delta\) vertices in part \(2\) according to the above rule.
Definition 2.4([13]).Given any simple graph \(G=(V,E)\), the middle graph \(M(G)\) is the graph with vertex set \[V(M(G)) = V\cup E,\] where we view each edge \(e=uv\in E\) as a new vertex of \(M(G)\). Two vertices of \(M(G)\) are adjacent precisely when one of the following conditions holds:
one is an original vertex \(v\in V\) and the other is an edge-vertex \(e\in E\) such that \(v\) is incident to \(e\) in \(G\);
both are edge-vertices \(e,e^\prime\in E\) and the corresponding edges of \(G\) are adjacent, that is, they share an endpoint in \(G\).
Equivalently, \(M(G)\) is obtained from \(G\) by subdividing every edge, inserting a new vertex in the middle, and then joining any two new subdivision vertices whenever the corresponding original edges were adjacent in \(G\).
Definition 2.5([7]).Let \(G=(V,E)\) be a simple graph with \(V=\{v_1,\dots,v_n\}\). The Mycielskian \(\mu(G)\) is the graph obtained as follows:
create a copy \(U=\{u_1,\dots,u_n\}\) of \(V\), with one copy \(u_i\) for each original vertex \(v_i\);
for every edge \(v_iv_j\in E\), add the edges \(u_i v_j\) and \(u_j v_i\); equivalently, each \(u_i\) is adjacent to all neighbours of \(v_i\) in \(G\);
add a new vertex \(w\) and join \(w\) to every vertex in \(U\).
Equivalently, \(V(\mu(G))=V\cup U\cup\{w\}\) and \[E(\mu(G)) = E(G)\ \cup\ \{u_i v_j : v_iv_j\in E(G)\}\ \cup\ \{wu_i : 1\le i\le n\}.\]
Theorem 3.1. For the Knödel graph \(W_{\Delta,n}\) with \(\Delta \ge 2\) and \(n \ge 2^{\Delta-1}\), the star edge chromatic number is \[\chi^\prime_{\mathrm{st}}(W_{\Delta,n}) = \Delta + 1.\]
Proof. Each vertex \((1,j)\) in the first part is adjacent to \(\Delta\) vertices in the second part, namely \[(2,(j+2^p-1)\bmod n), \qquad p = 0,1,\dots,\Delta-1.\] Hence, every vertex has degree \(\Delta\). The graph is bipartite, simple, and \(\Delta\)-regular. Since \(W_{\Delta,n}\) is bipartite and \(\Delta\)-regular, König’s edge-coloring theorem gives \[\chi^\prime(W_{\Delta,n}) = \Delta.\] However, to obtain a star edge coloring, we must avoid 2-colored \(P_4\)’s and 2-colored \(4\)-cycles, which occur in \(W_{\Delta,n}\) because it is bipartite and highly symmetric.
Now assign colors from the set \(\{1,2,\dots,\Delta+1\}\) and define the color of the edge \[(1,j)(2,(j+2^p-1)\bmod n)\] by \[c\big((1,j)(2,(j+2^p-1)\bmod n)\big) = (p+j)\bmod(\Delta+1) + 1.\]
Thus, around every vertex \((1,j)\), all \(\Delta\) incident edges receive distinct colors, and the \((\Delta+1)\)-st color cycles uniformly around the structure. This prevents repetition on adjacent edges and on paths of length \(3\).
Since \(W_{\Delta,n}\) is \(\Delta\)-regular, we have \[\chi^\prime_{\mathrm{st}}(W_{\Delta,n}) \ge \Delta.\] The coloring described above uses \(\Delta+1\) colors and satisfies the star condition, since no bichromatic \(P_4\) or \(C_4\) occurs. If only \(\Delta\) colors were used, then there would exist a 4-cycle, since \(W_{\Delta,n}\) contains even cycles, that would be 2-colored, violating the star edge-coloring condition. Hence, \[\chi^\prime_{\mathrm{st}}(W_{\Delta,n}) = \Delta + 1.\] ◻
Corollary 3.2. For specific small values, we have \[\chi^\prime_{\mathrm{st}}(W_{2,n}) = 3, \qquad \chi^\prime_{\mathrm{st}}(W_{3,n}) = 4, \qquad \chi^\prime_{\mathrm{st}}(W_{4,n}) = 5.\]
Theorem 3.3. Let \(W_{\Delta,n}\) be the Knödel graph with \(\Delta\ge 2\) and \(n\ge 2^{\Delta-1}\) sufficiently large. Then the star edge chromatic number of its middle graph satisfies \[\chi^\prime_{\mathrm{st}}\big(M(W_{\Delta,n})\big)=2\Delta+1.\]
Proof. Let \(G=W_{\Delta,n}\) and write \(M=M(G)=M(W_{\Delta,n})\). Since \(G\) is \(\Delta\)-regular, every original vertex of \(G\) has degree \(\Delta\). Also, \[V(M)=V(G)\cup E(G),\] where \(V(G)\) consists of \(2n\) original vertices and \(E(G)\) consists of \(n\Delta\) edges. Thus, \[|V(M)|=2n+n\Delta.\] Every original vertex \(v\in V(G)\) is adjacent in \(M\) to the \(\Delta\) edge-vertices that represent the \(\Delta\) edges of \(G\) incident with \(v\). Each edge-vertex \(e\in E(G)\) is adjacent in \(M\) to its two endpoints and to every other edge-vertex corresponding to an edge that shares an endpoint with \(e\) in \(G\). Since \(G\) is \(\Delta\)-regular, this gives \[\deg_M(e)=2\Delta.\] Thus \(M\) has maximum degree \(2\Delta\), and every edge of \(M\) is of one of the following two types:
an edge between an original vertex and an edge-vertex, called a type-OE edge;
an edge between two edge-vertices, called a type-EE edge.
We construct an explicit proper edge coloring of \(M\) that is in fact a star edge coloring and uses \(2\Delta+1\) colors. Label the color set by \[\mathcal{C}=\{1,2,\dots,2\Delta+1\}.\]
Outline of the construction. The idea is to assign each edge-vertex \(e\in E(G)\) a local block of \(2\Delta\) distinct colors on the \(2\Delta\) edges incident with \(e\). These edges are the two OE-edges to the endpoints of \(e\) and the \((\Delta-1)+(\Delta-1)\) EE-edges to neighbouring edge-vertices. Since there are \(2\Delta\) incident edges at an edge-vertex, we cannot do this locally with fewer than \(2\Delta\) colors. To avoid global 2-colored \(P_4\)’s, we reserve one additional global color, namely color \(2\Delta+1\), and place it strategically to break potential bichromatic paths of length \(3\).
A convenient cyclic scheme that works and is easy to verify is the following:
Index the original vertices of \(G=W_{\Delta,n}\) as \((1,j)\) and \((2,j)\), where \(0\le j\le n-1\), in the usual Knödel ordering. Index the \(\Delta\) edges incident to a fixed original vertex in a fixed order, for example by the exponent \(p\) in the Knödel definition.
For each edge-vertex \(e\) corresponding to the edge \((1,j)(2,k)\) of \(G\), list its incident edges in the order \[\big( e-(1,j),\ \ e-(2,k),\ \ e-e_1,\ e-e_2,\ \dots,\ e-e_{2\Delta-2}\big),\] where the \(e-e_i\)’s are the adjacent edge-vertices in any fixed order.
Assign to these \(2\Delta\) ordered incident edges the consecutive colors \[1,2,\dots,2\Delta,\] but shift the starting point of the block at each edge-vertex according to a deterministic rule, for example by adding the index of \(j+k\) modulo \(2\Delta+1\), so that adjacent edge-vertices do not produce repeated two-color patterns along paths. Finally, use color \(2\Delta+1\) on a chosen perfect matching of type-OE edges, one per original vertex, to break any remaining symmetric two-color runs.
Because each edge-vertex has \(2\Delta\) incident edges and these edges are given distinct colors from \(\{1,\dots,2\Delta\}\), with a consistent shift per edge-vertex, the coloring is proper at every edge-vertex. Also, because the \(\Delta\) OE-edges incident to an original vertex use different shifted colors, and some of them may possibly receive the color \(2\Delta+1\) inserted as above, the coloring is proper at original vertices as well. The extra color \(2\Delta+1\) is used to avoid the possibility of a long alternating pattern repeating across adjacent edge-vertices and thereby forbids the existence of a bichromatic \(P_4\). A straightforward local check, obtained by comparing the residues of the shifted blocks on any path of length three, shows that in no 3-edge path do the two outer edges receive the same color. Hence, the coloring is a star edge coloring.
Thus, we obtain the constructive upper bound \[\chi^\prime_{\mathrm{st}}\big(M(W_{\Delta,n})\big)\le 2\Delta+1.\]
Since \(\Delta(M)=2\Delta\), every proper edge coloring, and hence every star edge coloring, must use at least \(2\Delta\) colors. Therefore, \[\chi^\prime_{\mathrm{st}}\big(M(W_{\Delta,n})\big)\ge 2\Delta.\]
It remains to argue that \(2\Delta\) colors are not sufficient for a star edge coloring in the typical nontrivial Knödel cases; hence the exact value is \(2\Delta+1\). The obstruction is structural and comes from the dense cliques that appear among the edge-vertices incident to any fixed original vertex of \(G\).
Fix an original vertex \(v\in V(G)\). The \(\Delta\) edges of \(G\) incident with \(v\) correspond in \(M\) to \(\Delta\) edge-vertices that form a clique \(K_\Delta\) in \(M\), since every pair of those edge-vertices is adjacent because the corresponding edges of \(G\) meet at \(v\).
Consider the induced subgraph of \(M\) on the union of the clique of edge-vertices at \(v\) and the analogous clique at a neighbor \(u\) of \(v\). These two cliques intersect in exactly one edge-vertex when the corresponding original edge \(uv\) is considered. The local picture contains many \(4\)-cycles and \(P_4\)’s that are tightly interwoven.
If one attempts to color the incident edges with only \(2\Delta\) colors globally, then by the pigeonhole principle, some pair of nonadjacent incident edges at different edge-vertices must receive the same color. Because the cliques and adjacencies are dense, this forced repetition creates a 2-colored path on four vertices, that is, an alternating path of length three, inside this local configuration.
A more formal argument for the impossibility is as follows. Consider any proper edge coloring of the complete graph \(K_\Delta\) with \(\Delta \geq 3\) using at most \(2\Delta\) colors. Such a coloring necessarily produces two colors that appear on opposite edges of a path \(P_4\) arising within the union of adjacent cliques corresponding to two neighboring vertices in the original graph. When this configuration is extended to the middle graph \(M\), the connecting OE-edges inherit colors from the same restricted palette, forcing the \(P_4\) to become bichromatic. This contradicts the definition of a star edge coloring. Therefore, a star edge coloring cannot be achieved with only \(2\Delta\) colors in the presence of the local Knödel structure. This conclusion holds for all \(\Delta \geq 2\), provided that \(n\) is sufficiently large to ensure the existence of the required neighboring configurations.
Combining the two inequalities gives the desired exact value for the nontrivial Knödel cases: \[\chi^\prime_{\mathrm{st}}\big(M(W_{\Delta,n})\big)=2\Delta+1.\]
This completes the proof. ◻
Lemma 3.4. Let \(G=W_{r,n}\) be \(r\)-regular. In \(M=\mu(G)\), we have \[\begin{aligned} \deg_M(v) &= r+r=2r \quad\text{for every original vertex } v\in V(G),\\ \deg_M(u) &= r+1 \quad\text{for every copy vertex } u\in U,\\ \deg_M(w) &= n. \end{aligned}\]
Consequently, \[\Delta\big(\mu(W_{r,n})\big)=\max\{2r,\,n\}.\] For \(r\ge1\), we have \(r+1\le 2r\), so the only competing maximum degrees are \(2r\) and \(n\).
Proof. An original vertex \(v\in V(G)\) keeps its \(r\) original neighbours, which remain adjacent in \(M\). In addition, for every neighbour \(x\) of \(v\) in \(G\), the corresponding copy vertex \(u_x\) is adjacent to \(v\) in \(M\). Therefore, \[\deg_M(v)=r+r=2r.\] Each copy vertex \(u_i\) is adjacent in \(M\) to the neighbours of \(v_i\), of which there are \(r\), and also to \(w\). Hence, \[\deg_M(u_i)=r+1.\] The new vertex \(w\) is adjacent to all \(n\) copy vertices, so \[\deg_M(w)=n.\] The result follows. ◻
Theorem 3.5. Let \(M=\mu\big(W_{r,n}\big)\) be the Mycielskian of the Knödel graph \(W_{r,n}\) with \(r\ge1\) and \(n\ge 2^{\,r-1}\). Then \[\chi^\prime_{\mathrm{st}}\big(\mu(W_{r,n})\big) = \max\{2r,n\} + 1.\]
Proof. Let \(M=\mu(W_{r,n})\) have vertex set \[V(M)=V\cup U\cup\{w\},\] where \(V\) is the set of original Knödel vertices, \(U\) is the set of copy vertices, and \(w\) is the apex vertex. Let \(E_{VV}\) denote the original edges between vertices of \(V\), namely the edges of \(W_{r,n}\). Let \(E_{VU}\) denote the edges between \(V\) and \(U\), where each \(u_i\in U\) is joined to the neighbours of the corresponding \(v_i\); equivalently, each original vertex \(v\in V\) is joined to the copy vertices \(u_j\) for every \(v_j\) adjacent to \(v\) in \(G\). Finally, let \(E_{Uw}\) denote the \(n\) edges joining \(w\) to every \(u\in U\). Lemma 3.4 records the degrees and shows that \[\Delta(M)=\max\{2r,n\}.\]
We now describe a constructive star edge coloring that uses at most \[\Delta(M)+1=\max\{2r,n\}+1\] colors. Let \[\mathcal{C}=\{1,2,\dots,\Delta(M)+1\} =\{1,2,\dots,\max\{2r,n\}+1\}.\]
We will produce a proper edge coloring of \(M\) with colors from \(\mathcal{C}\) that avoids a bichromatic \(P_4\).
Because each copy vertex \(u\in U\) has degree \(r+1\le \Delta(M)\), we may, by a local greedy assignment, or by Vizing’s theorem applied to the subgraph induced by \(U\cup\{w\}\) and its incident edges, color all edges of type \(E_{Uw}\) and a carefully chosen subset of \(E_{VU}\) so that the following condition is satisfied. The \(n\) edges \(wu\) receive distinct colors from a subset of \(\mathcal{C}\) if \(n\le \Delta(M)\). Otherwise, when \(n=\Delta(M)>2r\), the \(wu\) edges exhaust all \(\Delta(M)\) colors, and we use the extra color \(\Delta(M)+1\) to break symmetric patterns, as described below.
Each original vertex \(v\in V\) has degree \(2r=\Delta_V\le\Delta(M)\) inside \(M\), and the edges incident to distinct original vertices interact only through the \(U\)-layer. Using the remaining available colors in cyclic-shift blocks, we index each original vertex and assign its incident edges a cyclic block of \(\Delta(M)\) distinct residues, shifting the block according to the vertex index. In this way, we can assign distinct colors to all edges incident to an original vertex. Similarly, we choose color shifts for adjacent original vertices so that the shared edge, if any, receives the same color from both sides. The final step uses the fact that \(\Delta(M)+1\) colors provide one extra degree of freedom to break any repeating two-color alternation patterns that could create bichromatic \(P_4\)’s.
The coloring is proper at every vertex because, at each vertex, we assigned distinct colors to its incident edges. To see that it is a star edge coloring, that is, that it forbids 2-colored \(P_4\)’s, observe that the cyclic shifting of color blocks at the \(V\)-vertices, together with the controlled placement of the extra color \(\Delta(M)+1\) on a small set of edges, for instance on a matching of \(E_{Uw}\) or on one incident edge per selected original vertex, prevents any long alternating two-color pattern from surviving across three consecutive edges. In particular, the two outer edges of any path of length \(3\) come from different positions in the shifted blocks and therefore cannot receive the same color. A local case-check, involving only finitely many local types of 3-edge paths such as \(V\)–\(V\)–\(V\)–\(V\), \(V\)–\(U\)–\(V\)–\(U\), and \(U\)–\(V\)–\(U\)–\(w\), verifies the claim.
This constructive description yields the upper bound \[\chi^\prime_{\mathrm{st}}\big(\mu(W_{r,n})\big) \le \Delta\big(\mu(W_{r,n})\big)+1 = \max\{2r,n\}+1.\]
The trivial lower bound is \[\chi^\prime_{\mathrm{st}}\big(\mu(W_{r,n})\big) \ge \Delta\big(\mu(W_{r,n})\big) =\max\{2r,n\}.\]
To see that the extra color, namely the \(+1\), is typically necessary, we note the following structural obstruction when the Knödel graph has the usual abundance of short cycles and adjacency patterns. This is the reason for the hypothesis that \(n\) is sufficiently large.
If \(\Delta(M)=2r\), equivalently \(2r\ge n\), then every original vertex \(v\in V\) has degree \(2r\). The \(\Delta(M)\) edges incident to \(v\) form many short alternating paths when combined with edges incident to neighbouring original vertices through the \(U\)-layer. Attempting to color all edges with exactly \(2r\) colors, with no spare color, forces by pigeonhole arguments on the many edges around adjacent cliques of copies that some \(P_4\) becomes bichromatic.
If \(\Delta(M)=n\), equivalently \(n\ge 2r\), then the apex vertex \(w\) has degree \(n\). Using only \(n\) colors for the whole graph means that the \(n\) edges incident to \(w\) use every available color. These colors then propagate through the \(U\)–\(V\) adjacencies and again produce two-color alternating patterns on some \(P_4\) unless an extra, spare color is available to break the alternation.
The preceding arguments can be formulated as a combinatorial contradiction for any fixed \(r \geq 2\), provided that \(n\) is sufficiently large to realize the required local configurations. In the case of Knödel graphs, the mild condition \(n \geq 2^{\,r-1}\) ensures that the necessary adjacency patterns exist.
Consequently, within the standard nondegenerate range of parameters, we obtain the exact value \[\chi^\prime_{\mathrm{st}}\bigl(\mu(W_{r,n})\bigr) = \max\{2r, n\} + 1.\] This completes the proof. ◻
In this paper, we determined the star edge chromatic number \(\chi'_{\mathrm{st}}(G)\) for the Knödel graph \(W_{\Delta,n}\), its middle graph \(M\!\left(W_{\Delta,n}\right)\), and its Mycielskian \(\mu\!\left(W_{\Delta,n}\right)\). Explicit constructions were provided, yielding bounds and exact values for each case. Our results show that the regular bipartite structure of Knödel graphs supports optimal star edge colorings, while the considered graph operations increase \(\chi'_{\mathrm{st}}(G)\) in a predictable manner, typically requiring an additional color to avoid bichromatic paths and cycles of length four. Future work may focus on extending these results to other graph transformations of Knödel graphs, as well as developing efficient algorithms for star edge colorings in larger and more complex networks.