Electronic Journal of Graph Theory and Applications

Jayson Tolentino*a,b, Reginaldo Marcelob, Mark Anthony Tolentinob

^aDepartment of Mathematics, Eulogio "Amang" Rodriguez Institute of Science and Technology, Manila, Philippines

jdtolentino@ateneo.edu, rmarcelo@ateneo.edu, mtolentino@ateneo.edu

Let \(k \geq 2\) be an integer and G be a connected graph of order at least 3. A twin k-edge coloring of G is a proper edge coloring of G that uses colors from \(\mathbb{Z}_k\) and that induces a proper vertex coloring on G where the color of a vertex v is the sum (in \(\mathbb{Z}_k\)) of the colors of the edges incident with v. The smallest integer k for which G has a twin k-edge coloring is the twin chromatic index of G and is denoted by \(\chi'_t(G)\). In this paper, we study the twin edge colorings in m-ary trees for \(m \geq 2\); in particular, the twin chromatic indices of full m-ary trees that are not stars, r-regular trees for even \(r \geq 2\), and generalized star graphs that are not paths nor stars are completely determined. Moreover, our results confirm the conjecture that \(\chi'_t(G) \leq \Delta(G) + 2\) for every connected graph G (except G) of order at least G, for all trees of order at least G.

Keywords: twin edge coloring, edge coloring, vertex coloring, m-ary trees

Mathematics Subject Classification: 05C05, 05C15

DOI: 10.5614/ejgta.2022.10.1.8

1. Introduction

Let G = (V, E) be a simple graph. A proper vertex coloring of G is a function from V to a given set of colors such that adjacent vertices are colored differently. On the other hand, a proper edge coloring of G is a function from E to a given set of colors such that adjacent edges are colored

Received: 11 September 2020, Revised: 30 December 2021, Accepted: 13 February 2022.

^&lt;sup>b</sup>Department of Mathematics, Ateneo de Manila University, Quezon City, Philippines

^*Corresponding author

differently. The minimum number of colors needed in a proper vertex coloring and a proper edge coloring of G are the chromatic number and chromatic index of G and are denoted by \(\chi(G)\) and \(\chi'(G)\), respectively. Thus \(\chi(G) \leq \Delta(G) + 1\) and \(\chi'(G) \geq \Delta(G)\), where \(\Delta(G)\) is the maximum degree of G.

A relatively new kind of graph coloring that has been studied in literature is the twin edge colorings of graphs. This concept was introduced by Chartrand [9] and was initially studied in [2, 3, 4].

Definition 1.1. For a connected graph G of order at least 3, a proper k-edge coloring \(c: E(G) \to \mathbb{Z}_k\) for some integer \(k \geq 2\) is called a twin k-edge coloring of G if the induced vertex coloring \(c': V(G) \to \mathbb{Z}_k\) defined by

\[c'(v) = \sum_{e \in E_v} c(e) \text{ in } \mathbb{Z}_k,\]

where \(E_v\) is the set of edges of G incident with v, is proper as well. The minimum k for which G has a twin k-edge coloring is the twin chromatic index of G, denoted by \(\chi'_t(G)\).

Since a twin edge coloring of G is a proper edge coloring of G, \(\chi'_t(G) \geq \Delta(G)\). It has been shown in [2] that every connected graph of order at least 3 has a twin edge coloring.

In [2], Andrews et.al obtained the twin chromatic indices of paths, cycles, complete graphs, and complete bipartite graphs. Their results are summarized in Theorem 1.2.

Theorem 1.2 ([2]). If n, a, b are integers with \(n \ge 3\), \(1 \le a \le b\) and \(b \ge 2\), then

1. \[\chi'_t(P_n) = 3\],

2. \[\chi'_t(C_n) = \begin{cases} 3, & \text{if } n \equiv 0 \pmod{3}, \\ 4, & \text{if } n \not\equiv 0 \pmod{3} \text{ and } n \neq 5, \\ 5, & \text{if } n = 5, \end{cases}\]

3. \[\chi'_t(K_n) = \begin{cases} n, & \text{if } n \text{ is odd,} \\ n+1, & \text{if } n \text{ is even,} \end{cases}\]

4. \[\chi'_t(K_{a,b}) = \begin{cases} b, & \text{if } b \ge a + 2 \text{ and } a \ge 2, \\ b + 1, & \text{if } (a = 1 \text{ and } b \ne 1 \pmod{4}) \text{ or } (b = a + 1 \ge 3), \\ b + 2, & \text{if } (a = 1 \text{ and } b \equiv 1 \pmod{4}) \text{ or } (b = a \ge 2). \end{cases}\]

Based on the results stated in Theorem 1.2, Andrews et.al [3] formulated Conjecture 1.3 and verified it for permutation graphs of 5-cycle, grids and prisms, and trees with maximum degree at most 6. Likewise, in [4], Conjecture 1.3 was also verified for several types of trees such as brooms, double stars and some regular trees (see Theorem 1.4). Also, the twin chromatic indices of most of the graphs discussed in [3, 4] are determined.

Conjecture 1.3 ([3]). If G is a connected graph of order at least 3 that is not a 5-cycle, then \(\chi'_t(G) \leq \Delta(G) + 2\).

Theorem 1.4 ([4]). Let T be a tree of order at least 3. Then the following statements hold:

• 1. If T is a broom that is not a star, then T has a twin \((\Delta(T)+1)\)-edge coloring and so \(\chi'_t(T) \le \Delta(T)+1\);
• 2. If T is a regular double star, then

\[\text{[rumus tidak dapat ditampilkan dengan baik — lihat PDF asli]}\]

• 3. If T is an irregular double star, then T has a twin \((\Delta(T) + 1)\)-edge coloring and so \(\chi'_t(T) \le \Delta(T) + 1\);
• 4. For each integer \(r \ge 3\), the star \(K_{1,r}\) has a twin (r+2)-edge coloring; and
• 5. If T is a regular tree of order at least 6 such that \(\Delta(T) \equiv 1 \pmod{4}\), then \(\chi'_t(T) = \Delta(T) + 2\).

In recent years, several studies on twin edge colorings have been conducted. Some of these studies are the works of Lakshmi and Kowsalya [5], Rajarajachozhan and Sampathkumar [6], Yang et.al [8], Anantharaman [1], and Tolentino et.al [7]. In [5] and [6], Lakshmi and Kowsalya determined the twin chromatic index of wheel graphs while Rajarajachozhan and Sampathkumar investigated the twin chromatic indices of the square graphs \(P_n^2\), where \(n \geq 4\), and \(C_n^2\), where \(n \geq 6\) and the twin chromatic index of the Cartesian product \(C_m \square P_n\), where \(m, n \geq 3\). In [8], Yang et.al determined the twin chromatic indices of direct product of paths. Recently, in [1] and [7], Anantharaman computed the twin chromatic indices of the total graphs of paths and cycles, and constructed special graphs whose twin chromatic indices are \(\Delta + 2\) while Tolentino et.al determined the twin chromatic indices of some graphs with maximum degree 3 such as circulant graphs \(C_n(1, \frac{n}{2})\), where \(n \geq 8\) and \(n \equiv 0 \pmod{4}\), and some generalized Petersen graphs.

A rooted tree T is a tree in which one vertex of T is assigned as the root. Suppose T is a rooted tree and let \(v_0\) be the root of T. If v is a vertex in T other than the root, an ancestor of v is a vertex \(z \neq v\) of T that is in the unique path from \(v_0\) to v and the parent of v is the unique ancestor u of v that is adjacent with v. If u is the parent of v, then v is a child of u. The descendants of a vertex w of T are the vertices of T that have w as an ancestor. A vertex of T is called an internal vertex if it has at least one child. A height in T is the distance between a leaf w and \(v_0\). A rooted tree is called an m-ary tree if every internal vertex has at most w children and is called a full m-ary tree if every internal vertex has exactly w children. For an integer w is a descendant of w is equal to w.

In the remaining sections, given an m-ary tree T, we will use c to denote an edge coloring with colors \(\mathbb{Z}_{m+2}\), unless stated otherwise; also, we will use c' to denote the vertex coloring induced by c on T. Moreover, when constructing an edge coloring c, we will denote by \(c(E_v)\) the set \(\{c(e): e \in E_v\}\) where the edge colors have been assigned so that \(c(e_1) \neq c(e_2)\) for any distinct \(e_1, e_2 \in E_v\).

In this paper, we determine the twin chromatic indices of some m-ary trees as well as an upper bound for the twin chromatic index of all trees of order at least 3, including those that were not discussed in [2, 3, 4]. More specifically, in sections 2 and 3, we discuss results on the twin edge colorings in full m-ary trees that are not stars where \(m \ge 2\) and in m-ary trees that are not stars with degrees equal to m, \(m \ge 3\), respectively. As a consequence, Conjecture 1.3 is verified for all trees of order at least 3.

2. Full m-ary Trees

In this section, we show that for an integer \(m \geq 2\), the twin chromatic index of a full m-ary tree T that is not a star nor a double star is \(m+2=\Delta(T)+1\). Moreover, for an odd integer \(m\geq 3\), the twin chromatic index of a full m-ary tree which is a double star is determined. The following observations will be useful.

Observation 2.1 ([2]). If a connected graph G contains two adjacent vertices of degree \(\Delta(G)\), then \(\chi'_t(G) \geq 1 + \Delta(G)\). In particular, if G is a connected r-regular graph for some integer \(r \geq 2\), then \(\chi'_t(G) \geq 1 + r\).

Observation 2.2. If G is a connected graph that contains two vertices u and v such that

• 1. \(deg(u) = deg(v) = \Delta(G)\);
• 2. both u and v are adjacent with exactly \(\Delta(G) 1\) leaves in G; and
• 3. u and v are adjacent with a common vertex w in G,

then \[\chi'_t(G) \geq \Delta(G) + 1\].

Proof. We just need to show that \(\chi'_t(G) \neq \Delta(G)\). Suppose on the contrary that \(\chi'_t(G) = \Delta(G)\); that is, G has a twin \(\Delta(G)\)-edge coloring c. Now, let u, v, and w be vertices in G that satisfy conditions (1) - (3). Then, \(c(E_u) = c(E_v) = \mathbb{Z}_{\Delta(G)}\) and so c'(u) = c'(v) = a where a = 0 if \(\Delta(G)\) is odd and \(a = \frac{\Delta(G)}{2}\), otherwise. Since c is a proper edge coloring, \(c(uw) \neq c(vw)\). Therefore, c(ux) = a or c(vx) = a for some leaf x. Then c'(x) = a, and we get a contradiction. Hence \(\chi'_t(G) \neq \Delta(G)\).

Note that if T is a full m-ary tree that is not a star, then \(\Delta(T) = m + 1\). Moreover, for every full m-ary tree T that is not a star nor a double star, T has at least two vertices with degree equal to \(\Delta(T)\). For the rest of the paper, we shall denote by \(v_0\) the root of a rooted tree.

Lemma 2.3. If \(m \ge 2\) is even and T is a full m-ary tree which is not a star, then \(\chi'_t(T) \ge m + 2\).

Proof. Since T is a full m-ary tree which is not a star, then \(\Delta(T) = m + 1\). Therefore, \(\chi'_t(T) \ge m + 1\). Let \(v_0\) be the root of T. We now consider the following cases:

Case 1. Suppose T is a double star. Then there are exactly two adjacent vertices \(u=v_0\) and v of T with degrees m and m+1, respectively. Now, suppose T has a twin (m+1)-edge coloring \(c: E(T) \to \mathbb{Z}_{m+1}\). Since deg(v) = m+1, we must have \(c(E_v) = \mathbb{Z}_{m+1}\). If \(c(uv) \neq 0\), then c(vx) = 0 for some leaf \(x \in N(v)\). Then c'(v) = c'(x) = 0. Thus c(uv) = 0. Since deg(u) = m, \(a \notin c(E_u)\) for some \(a \in \mathbb{Z}_{m+1}^*\). Then we have c'(u) = -a, where \(-a \in \mathbb{Z}_{m+1}^*\), \(-a \neq a\). Hence c(uw) = -a for some child w of u and so c'(w) = -a and c' becomes improper. Hence, \(\chi'_t(T) \geq m+2\).

Case 2. Suppose T has a maximum height h=2 and T is not a double star. Then there exist two children u and v of \(v_0\) in T such that u and v have exactly m children with deg(u)=deg(v)=m+1. Therefore, by Observation 2.2, \(\chi'_t(T) \geq \Delta(T)+1=m+2\).

Case 3. Suppose T has a maximum height \(h \geq 3\). Then there exist two adjacent vertices u and v of T such that deg(u) = deg(v) = m+1. Therefore, by Observation 2.1, \(\chi'_t(T) \geq \Delta(T) + 1 = m+2\).

Lemma 2.4. If \(m \ge 2\) is even and T is a full m-ary tree which is not a star, then \(\chi'_t(T) = m + 2\).

Proof. By Lemma 2.3, we have \(\chi'_t(T) \ge m+2\) and so we only need to show that \(\chi'_t(T) \le m+2\), that is, T has a twin (m+2)-edge coloring. We show this by construction, that is, we will construct an (m+2)-edge coloring \(c: E(T) \to \mathbb{Z}_{m+2}\) of T. Let \(v_0\) be the root of T and \(b = \frac{m+2}{2}\).

First, we let \(c(E_{v_0}) = \mathbb{Z}_{m+2}^* \setminus \{b\}\) so that \(c'(v_0) = 0\) and \(c(v_0 z) \neq 0\) for any child z of \(v_0\). In this construction, we will completely define \(c(E_v)\) whenever \(c(E_u)\) is known for any child v of u such that c(uv) will not be changed. We continue this until all edges of T are colored. To do that, we will consider the following cases:

Case 1. Suppose \(c(uv) \notin \{\frac{b}{2}, \frac{3b}{2}\}\). In this case, we define \(c(E_v) = \mathbb{Z}_{m+2} \setminus \{b - c(uv)\}\) so that c'(v) = b - (b - c(uv)) = c(uv).

Case 2. Suppose \(c(uv) \in \{\frac{b}{2}, \frac{3b}{2}\}\). In this case, \(m \equiv 2 \pmod{4}\) and \(\frac{b}{2}, \frac{3b}{2} \in \mathbb{Z}_{m+2}\). Let \(c(E_v) = \mathbb{Z}_{m+2} \setminus \{-c(uv)\}\) so that c'(v) = b - (-c(uv)) = -c(uv).

Figure 1 shows examples of the coloring of \(E_v\) in a full 6-ary tree using the colors in \(\mathbb{Z}_8\).

Figure 1. Possible colorings of \(E_v\) in a full 6-ary tree

From the construction of c, it follows that c is a proper (m+2)-edge coloring of T. Moreover, if v is the parent of a leaf w in T, then \(c'(w) = c(vw) \in c(E_v) \setminus \{c(uv)\}\), so \(c'(w) \neq c'(v)\). Now, let u and v be two adjacent internal vertices in T where u is the parent of v. If \(u = v_0\), then c'(u) = 0 and \(c(uv) \neq 0\); since \(c'(v) = \pm c(uv)\) from the consctruction, \(c'(v) \neq c'(u)\).

Now, let \(u \neq v_0\) and let c'(u) = a. If \(a \notin \{\frac{b}{2}, \frac{3b}{2}\}\), then \(c(uv) \neq a\). So if \(c(uv) \notin \{\frac{b}{2}, \frac{3b}{2}\}\), then \(c'(v) = c(uv) \neq a\). On the other hand, if \(c(uv) \in \{\frac{b}{2}, \frac{3b}{2}\}\), then \(c'(v) = -c(uv) \neq a\). Now, if \(a \in \{\frac{b}{2}, \frac{3b}{2}\}\), then \(-a \in \{\frac{b}{2}, \frac{3b}{2}\}\) and \(c(uv) \notin \{\frac{b}{2}, \frac{3b}{2}\}\). Therefore, \(c'(v) = c(uv) \neq a\). Then for any adjacent internal vertices u and v in T, \(c'(u) \neq c'(v)\). Therefore, c' is also proper and so c is a twin (m+2) edge coloring of T. Hence \(\chi'_t(T) \leq m+2\).

Recall that a tree T is said to be r-regular or simply regular, for an integer \(r \ge 2\), if each vertex of T that is not a leaf has degree r. Otherwise, T is an irregular tree.

Lemma 2.5. If \(m \ge 3\) is odd and T is a full m-ary tree which is a double star, then

\[\text{[rumus tidak dapat ditampilkan dengan baik — lihat PDF asli]}\]

Proof. Here, T is an irregular double star. Since \(\Delta(T) = m+1\), \(\chi'_t(T) \ge m+1\) and by Theorem 1.4.3, \(\chi'_t(T) \le \Delta(T) + 1 = m+2\). Let u and v be the vertices of T with degrees m and m+1 respectively.

Case 1. Suppose \(m+1\equiv 0\pmod 4\). We define a proper (m+1)-edge coloring \(c:E(T)\to \mathbb{Z}_{m+1}\) by \(c(E_v)=\mathbb{Z}_{m+1}\) such that c(uv)=b, where \(b=\frac{m+1}{2}\) and \(c(E_u)=\mathbb{Z}_{m+1}\setminus\{\frac{b}{2}\}\). Then we have c'(v)=b and \(c'(u)=\frac{b}{2}\) and so \(c'(v)\neq c'(u)\). Moreover, \(c(vx)\neq b\) and \(c(uy)\neq\frac{b}{2}\) for any child x,y of v,u respectively. Therefore, c' is proper. Hence c is a twin (m+1)-edge coloring of T and so \(\chi'_t(T)=m+1\).

Case 2. Suppose \(m+1\not\equiv 0\pmod 4\). We just need to show that \(\chi'_t(T)\not\equiv m+1\). Suppose on the contrary that T has a twin (m+1)-edge coloring \(c:E(T)\to\mathbb{Z}_{m+1}\). Since deg(v)=m+1, we must have \(c(E_v)=\mathbb{Z}_{m+1}\) and so c'(v)=b, where \(b=\frac{m+1}{2}\). Thus, we must have c(uv)=b; otherwise c(vx)=b and so c'(x)=b for some child x of v which contradicts the fact that c' is proper. Since \(deg(u)=m, 0\in c(E_u)\); otherwise c'(u)=b and c' becomes improper. Therefore, \(c(E_u)=\mathbb{Z}_{m+1}\setminus\{d\}\) for some \(d\in\mathbb{Z}_{m+1}^*\setminus\{b\}\). Then \(c'(u)=b-d\not\equiv d\) since b is odd. But c(uy)=b-d for some child \(y\not\equiv v\) of u and so c'(y)=b-d and c' becomes improper. Hence \(\chi'_t(T)\not\equiv m+1\) and so \(\chi'_t(T)=m+2\).

We will now determine the twin chromatic index of full m-ary trees that are not stars nor double stars, where \(m \geq 3\) is odd. First, we consider algorithm 1.

Algorithm 1. To construct a twin (m + 2)-edge coloring of a full m-ary tree T that is not a star \((m \ge 3 \text{ is odd})\)

• 1. Let \(c(E_{v_0}) = \mathbb{Z}_{m+2}^* \setminus \{m+1\}\) such that \(c(v_0 z) = 1\), for some \(v_0 z \in E(T)\) with \(deg(z) \neq 1\).
• 2. If each edge of T has been assigned a color, then we are done. Else, choose a vertex \(v \in V(T)\) with the parent u such that \(c(E_u)\) is completely determined, but not \(c(E_v)\). We define \(c(E_v)\) such that c(uv) will not be changed. Unless stated otherwise, we assign the

colors to the edges arbitrarily. Let \(A = \{0, c(uv), -c(uv), -c'(u)\} \subset \mathbb{Z}_{m+2}\) and suppose v is k-ancestor, \(k \ge 1\).

• 3. If k > 3:
  • (a) if \(c(uv) \neq 0\), let \(c(E_v) = \mathbb{Z}_{m+2} \setminus \{a\}\) for some \(a \notin A\) such that c(vy) = -a and c(vw) = 0 for some children y and w of v, where \(deg(y) \neq 1\) and w is not 1-ancestor;
  • (b) if c(uv) = 0, let \(c(E_v) = \mathbb{Z}_{m+2} \setminus \{c'(u)\}\) such that c(vw) = -c'(u) for some child w of v with \(deg(w) \neq 1\);
• 4. If k = 2:
  • (a) if \(c(uv) \neq 0\), let \(c(E_v) = \mathbb{Z}_{m+2}^*\);
  • (b) if c(uv) = 0, follow #3.b;
• 5. If k = 1:
  • (a) if c'(u) = 0, let \(c(E_v) = \mathbb{Z}_{m+2} \setminus \{-c(uv)\};\)
  • (b) if \(c'(u) \neq 0\), let \(c(E_v) = \mathbb{Z}_{m+2}^*\);

We show in the proof of Lemma 2.6 that Algorithm 1 produces a twin (m + 2)-edge coloring for any full m-ary tree T that is not a star nor a double star if m ≥ 3 is odd.

Lemma 2.6. If m ≥ 3 is odd and T is a full m-ary tree which is not a star nor a double star, then χ 0 t (T) = m + 2.

Proof. Using similar arguments in Cases 2 and 3 of Lemma 2.3, we have χ 0 t (T) ≥ m + 2. Then we just need to show that χ 0 t (T) ≤ m + 2, that is, T has a twin (m + 2)-edge coloring. We do this by proving that Algorithm 1 produces a twin (m + 2)-edge coloring for T. Let v⁰ be the root of T. Let c : E(T) → Zm+2 be an (m + 2)-edge coloring of T obtained by applying Algorithm 1.

In Steps 1 through 5, c(e) 6= c(e 0 ) for any adjacent edges e and e 0 in T and so c is proper. In Step 1, c 0 (v0) = 1 and if there is a child z of v⁰ that is a leaf, then c 0 (z) 6= 1 and so c 0 (v0) 6= c 0 (z).

In Step 3, c 0 (v) 6= 0 since 0 ∈ c(Ev). Now, since u is (k + 1)-ancestor, k ≥ 3, c(Eu) is also determined in Step 3 before c(Ev) or in Step 1 if u = v0. Therefore, for any vertex v of T, where v is k-ancestor, k ≥ 3, c 0 (v) 6= 0. If c(uv) 6= 0, then c 0 (v) = −a 6= c 0 (u). If c(uv) = 0, then c 0 (v) = −c 0 (u) 6= 0 and so c 0 (u) 6= c 0 (v).

In Step 4, c 0 (u) 6= 0 since c(Eu) is determined in Step 3 or Step 1. If c(uv) 6= 0, then c 0 (v) = 0 and so c 0 (u) 6= c 0 (v). If c(uv) = 0, then c 0 (v) = −c 0 (u) 6= 0 and so c 0 (u) 6= c 0 (v). In any case, c(vw) 6= 0 for any child w of v.

Therefore, in Step 5, all possible values for c(uv) and c 0 (u) are considered. Now, if c 0 (u) = 0, then c 0 (v) = c(uv) and so c 0 (u) 6= c 0 (v); if c 0 (u) 6= 0, then c 0 (v) = 0 and so c 0 (u) 6= c 0 (v).

Moreover, in Steps 3 through 5, c 0 (z) 6= c 0 (v) whenever z is a child of v that is a leaf. Therefore, c 0 (u) 6= c 0 (v) for any adjacent vertices u and v of T and so c 0 is proper. Hence, c is a twin (m + 2) edge coloring for T.

In summary, we have the following theorem.

Theorem 2.7. Let m ≥ 2 and T be a full m-ary tree that is not a star. Then χ 0 t (T) = m + 1 if T is a double star and m ≡ −1 (mod 4) and χ 0 t (T) = m + 2, otherwise.

Therefore, χ 0 t (T) = ∆(T) + 1 for every full m-ary tree T that is not a star nor a double star, where m ≥ 2. We will now work on the twin edge colorings in m-ary trees that are not full in the next section.

3. Non Full m-ary Trees

In the following discussion, we let S ⊂ Zⁿ and S ⁰ = {s ∈ S | −s 6∈ S}. Also, for an m-ary tree T with ∆(T) = m, we fix the root v⁰ of T so that deg(v0) = m. If m is even, we let b = m+2 2 .

Figure 2. A twin 5-edge coloring of a 3-ary tree produced by Algorithm 1

Algorithm 2. To construct a twin (m + 2)-edge coloring of a tree T that is not a star with ∆(T) = m (m ≥ 3 is odd)

• 1. Let c(E^v0 ) = Z ∗ ^m+2\{m + 1} such that c(v0z) = 1 for some v0z ∈ E(T) with deg(z) 6= 1.
• 2. If each edge of T has been assigned a color, then we are done. Else, choose a vertex v ∈ V (T) with the parent u such that c(Eu) is completely determined, but not c(Ev). We define c(Ev) such that c(uv) will not be changed. We define c(Ev) to be a set S ⊂ Zm+2 with |S| = |Ev|, such that conditions in each case are satisfied. Note that this set may not be unique. If deg(v) = 2, we just define the color of the uncolored edge vw ∈ Ev. Let A = {0, c(uv), −c(uv), c⁰ (u)} ⊂ Zm+2 and suppose v is k-ancestor, k ≥ 1.
• 3. If k ≥ 3:
  • (a) if deg(v) is odd:
    • i. if c(uv) 6= 0 and c 0 (u) 6= −c(uv), let 0 6∈ S and S ⁰ = {a} for some a ∈ Zm+2 \ A, such that c(vw) = a for some child w of v with deg(w) 6= 1;
    • ii. if c(uv) = 0 and c 0 (u) 6= 0, let S ⁰ = ∅;
  • (b) if deg(v) > 2 is even:

• i. if c(uv) 6= 0 and c 0 (u) 6= −c(uv), let 0 ∈ S, S ⁰ = {a} for some a ∈ Zm+2 \ A, c(vy) = 0 and c(vw) = a for some children y and w of v, where y is not 1-ancestor and deg(w) 6= 1;
• ii. if c(uv) = 0 and c 0 (u) 6= 0, let S ⁰ = {−c 0 (u)}, such that c(vw) = −c 0 (u) for some child w of v with deg(w) 6= 1;
• (c) if deg(v) = 2:
  • i. if c(uv) = 0 and c 0 (u) 6= 0, let c(vw) = −c 0 (u);
  • ii. if c(uv) 6= 0 and c 0 (u) 6∈ {0, −c(uv)}, let c(vw) = −c(uv);
  • iii. if c(uv) 6= 0 and c 0 (u) = 0, let c(vw) = −2c(uv);
• 4. If k = 2:
  • (a) if deg(v) is odd, follow #3.a;
  • (b) if deg(v) is even:
    • i. if c(uv) 6= 0 and c 0 (u) 6= 0, let 0 6∈ S and S ⁰ = ∅;
    • ii. if c(uv) 6= 0 and c 0 (u) = 0, let0 6∈ S and S ⁰ = {−2c(uv), c(uv)};
    • iii. if c(uv) = 0 and c 0 (u) 6= 0, let S ⁰ = {−c 0 (u)}, such that c(vw) = −c 0 (u) for some child w of v with deg(w) 6= 1;
• 5. If k = 1:
  • (a) if deg(v) is odd:
    • i. if c(uv) = c 0 (u) 6= 0, let 0 ∈ S and S ⁰ = {−2c(uv), c(uv)};
    • ii. if c(uv) 6= 0 and c 0 (u) 6= c(uv), let 0 6∈ S and S ⁰ = {c(uv)};
  • (b) if deg(v) is even:
    • i. if c(uv) 6= 0 and c 0 (u) 6= 0, let 0 6∈ S and S ⁰ = ∅;
    • ii. if c(uv) 6= 0 and c 0 (u) = 0, let 0 ∈ S and S ⁰ = {c(uv)};

Figure 3. A twin 5-edge coloring of a 3-ary tree produced by Algorithm 2

We will prove in the following lemma that, for an odd integer m ≥ 3, Algorithm 2 produces a twin (m + 2)-edge coloring of a tree T that is not a star and with ∆(T) = m.

Lemma 3.1. If m ≥ 3 is odd and T is a tree which is not a star with ∆(T) = m, then Algorithm 2 produces a twin (m + 2)-edge coloring of T. Therefore, χ 0 t (T) ≤ m + 2.

Table 1. Values for c(vw) and c'(v) produced by Algorithm 2

Proof. Let \(c: E(T) \to \mathbb{Z}_{m+2}\) be an (m+2)-edge coloring of T produced by Algorithm 2. Then c is a proper edge coloring from the construction. We need to show that c' is also proper.

In Step 1, \(c'(v_0) = 1\) and if there is a child z of \(v_0\) that is a leaf, then \(c'(z) \neq 1\) and so \(c'(v_0) \neq c'(z)\). Moreover, we obtain the cases (c(uv), c'(u)) = (d, 1), where \(d \in \mathbb{Z}_{m+2}^* \setminus \{m+1\}\) from Step 1 and all these cases are considered in Steps 3 to 5.

Now, in Step 3, by considering all the cases obtained from Step 1, we obtain new cases (c(uv),c'(u))=(0,d), (d,0), (d,e), where \(d\neq 0\), \(e\neq 0\) and \(e\neq -d\). These new cases are also considered in Step 3 and do not produce the cases (c(uv),c'(u))=(0,0) nor \((d,-d), d\neq 0\). Observe that only the cases considered in Step 3 should be considered in Step 4. Moreover, for any vertex v that is a 1-ancestor, the case that c(uv)=0 will not occur. Therefore, all possible cases for the value of (c(uv),c'(u)) are considered in Steps 3 to 5.

In Steps 1, 3, 4, 5, we obtain the values for c(vw) and c'(v) which are presented in Table 3. As shown in the table, for any vertex v of T that is a k-ancestor, \(k \ge 1\), \(c'(v) \ne c'(u)\) if u is the parent of v. Moreover, in Steps 3 to 5, \(c'(z) \ne c'(v)\) whenever z is a child of v that is a leaf. Therefore, \(c'(u) \ne c'(v)\) for any adjacent vertices u and v of T and so c' is proper. Hence, c is a twin (m+2)-edge coloring of T.

Algorithm 3. To construct a twin (m+2)-edge coloring of a tree T with \(\Delta(T)=m\) \((m\geq 4\) is even)

• 1. Let \(c(E_{v_0}) = \mathbb{Z}_{m+2}^* \setminus \{r\}\), where \(r \notin \{0, b\}\), such that \(c(v_0 z) = b r\) for some \(v_0 z \in E(T)\)with \(deg(z) \neq 1\) if \(b - r \in c(E_{v_0})\).
• 2. If each edge of T has been assigned a color, then we are done. Else, choose a vertex \(v \in\)V(T) with the parent u such that \(c(E_u)\) is completely determined, but not \(c(E_v)\). We define \(c(E_v)\) such that c(uv) will not be changed. We define \(c(E_v)\) to be a set \(S \subset \mathbb{Z}_{m+2}\)with \(|S| = |E_v|\), such that conditions in each case are satisfied. Note that this set may not be unique. If deg(v) = 2, we just define the color of the uncolored edge \(vw \in E_v\). Let \(A = \mathbb{Z}_{m+2}^* \setminus \{b, \frac{b}{2}, \frac{3b}{2}\}\) and suppose v is k-ancestor, \(k \ge 1\). Note that if \(m+2 \not\equiv 0 \pmod{4}\), then \(\frac{b}{2}, \frac{3b}{2} \notin \mathbb{Z}_{m+2}\).
• 3. If k > 3:
  • (a) if deg(v) is odd:
    • i. if \(c(uv) \in \mathbb{Z}_{m+2}^* \setminus \{b\}\) and \(c'(u) \neq c(uv)\), let \(0, b \notin S\) and \(S' = \{c(uv)\}\); ii. if \(c(uv) \in \mathbb{Z}_{m+2}^* \setminus \{b\}\) and c'(u) = c(uv), let \(0, b \notin S\) and \(S' = \{r\}\), for some \(r \notin \{0, b, c(uv), -c(uv)\}\) such that c(vw) = r for some child w of v with \(deg(w) \neq r\)1;
    • iii. if \(c(uv) \in \{0, b\}\) and \(c'(u) \notin \{0, b\}\), let \(b + c(uv) \notin S\) and \(S' = \emptyset\);
  • (b) if deq(v) > 2 is even:
    • i. if \(c(uv) \in A\) and \(c'(u) \neq c(uv)\), let \(b \in S\), \(0 \notin S\), and \(S' = \{c(uv) b\}\);
    • ii. if \(c(uv) \in A\) and c'(u) = c(uv), let \(b \in S\), \(0 \notin S\), and \(S' = \{-c(uv) b\}\), such that c(vw) = -c(uv) for some child w of v with \(deg(w) \neq 1\);
    • iii. if \(c(uv) \in \{0, b\}\) and \(c'(u) \notin \{0, b\}\), let \(b + c(uv) \notin S\) and \(S' = \{-c'(u) c(uv)\}\), such that c(vw) = -c'(u) for some child w of v with \(deg(w) \neq 1\) if \(-c'(u) \in S\);
    • iv. if \(c(uv) \in \{\frac{b}{2}, \frac{3b}{2}\}\) and \(c'(u) \neq c(uv)\), let \(0 \in S\), \(b \notin S\) and \(S' = \{c(uv)\}\), such that c(vy) = 0 for some child y of v that is not 1-ancestor;
    • v. if \(c(uv) \in \{\frac{b}{2}, \frac{3b}{2}\}\) and c'(u) = c(uv), let \(0 \in S\), \(b \notin S\), and \(S' = \{r\} \subset A\), such that c(vy) = 0 and c(vw) = r for some children y and w of v, where y is not 1-ancestor and \(deg(w) \neq 1\);
  • (c) if deg(v) = 2:
    • i. if \(c(uv) \notin \{0, b\}\) and \(c'(u) \neq c(uv)\), let c(vw) = 0;
    • ii. if \(c(uv) = c'(u) \in A\), let c(vw) = b;
    • iii. if \(c(uv) \in \{0, b\}\) and \(c'(u) \notin \{0, b\}\), let c(vw) = -c'(u) c(uv);
    • iv. if \(c(uv) \in \left\{\frac{b}{2}, \frac{3b}{2}\right\}\) and c'(u) = c(uv), let c(vw) = -c(uv);
• 4. If k = 2:
  • (a) if deg(v) is odd, follow #3.a;
  • (b) if deq(v) > 2 is even:
    • i. if \(c(uv) \not\in \{\frac{b}{2}, \frac{3b}{2}\}\), follow #3.b; ii. if \(c(uv) \in \{\frac{b}{2}, \frac{3b}{2}\}\) and \(c'(u) \neq 0\), let \(0, b \not\in S\) and \(S' = \varnothing\); iii. if \(c(uv) \in \{\frac{b}{2}, \frac{3b}{2}\}\) and c'(u) = 0, let \(b \in S\), \(0 \not\in S\) and \(S' = \{c(uv)\}\);
  • (c) if deq(v) = 2:

i. if c(uv) \not\in \{0,b\} and c'(u) \neq 0, let c(vw) = -c(uv); ii. if c(uv) \not\in \{0,b\} and c'(u) = 0, let c(vw) = b; iii. if c(uv) \in \{0,b\} and c'(u) \not\in \{0,b\}, let c(vw) = -c'(u) - c(uv);

5. If k = 1:

(a) if deg(v) is odd:
\ni. if c(uv) = c'(u) \in A, let 0, b \in S, b + c(uv) \not\in S, and S' = \{c(uv)\}; ii. if c(uv) \not\in \{0,b\} and c'(u) \neq c(uv), let 0,b \notin S and S' = \{c(uv)\}; iii. if c(uv) \neq b with c'(u) \notin \{0,b\}, let S' = \emptyset; iv. if c(uv) \in \{\frac{b}{2}, \frac{3b}{2}\} with c'(u) = c(uv), let 0, b \in S and S' = \{c(uv)\};

(b) if deg(v) is even:
\ni. if c(uv) \in A and c'(u) \neq 0, let 0, b \notin S and S' = \{c(uv)\}; iii. if c(uv) \in A and c'(u) = 0, let 0 \in S, b \notin S and S' = \{c(uv)\}; iii. if c(uv) = b and c'(u) \notin \{0,b\}, let 0 \in S and S' = \{c(uv)\}; iv. if c(uv) \in \{\frac{b}{2}, \frac{3b}{2}\} and c'(u) \neq c(uv), let 0 \in S, b \notin S and S' = \{c(uv)\}; v. if c(uv) \in \{\frac{b}{2}, \frac{3b}{2}\} and c'(u) \neq c(uv), let 0 \in S, b \notin S and S' = \{c(uv)\}; v. if c(uv) \in \{\frac{b}{2}, \frac{3b}{2}\} and c'(u) = c(uv), let 0 \in S, 0 \notin S and S' = \{c(uv)\}; v. if c(uv) \in \{\frac{b}{2}, \frac{3b}{2}\} and c'(u) = c(uv), let b \in S, b \notin S and b' = \{c(uv)\};

Figure 4. A twin 6-edge coloring of a 4-ary tree produced by Algorithm 3

We will prove in Lemma 3.2 that Algorithm 3 is valid.

Lemma 3.2. If \(m \ge 4\) is even and T is a tree which is not a star with \(\Delta(T) = m\), then Algorithm 3 produces a twin (m+2)-edge coloring of T. Therefore, \(\chi'_t(T) \le m+2\).

Proof. Let \(c: E(T) \to \mathbb{Z}_{m+2}\) be an (m+2)-edge coloring of T produced by Algorithm 3. Then c is a proper edge coloring from the construction. We need to show that c' is also proper.

In Step 1, \(c'(v_0) = 0\) and if there is a child z of \(v_0\) that is a leaf, then \(c'(z) \neq 0\) and so \(c'(v_0) \neq c'(z)\). Moreover, we obtain the cases (c(uv), c'(u)) = (d, 0), where \(d \in \mathbb{Z}_{m+2}^* \setminus \{b\}\) from #1 and all these cases are considered in Steps 3 to 5.

We will now refer to Table 3 for the possible values of (c(uv), c'(u)) that should be considered in Steps 3, 4 and 5. The only cases that are not covered in Steps 3 and 4 are (c(uv), c'(u)) = (f, b + f) and (f, f) where f = 0 or b. But these cases will not arise in Steps 3 and 4. In case of step 5, the following case is also not covered: \((c(uv), c'(u)) = (0, d), d \neq 0, b\). It can be checked that the case \((c(vw), c'(v)) = (0, d), d \neq 0, b\) will not occur in Steps 1, 3, and 4 if w is 1-ancestor.

Now, Table 3 also shows that for any vertex v of T, where v is k-ancestor, \(k \ge 1\), \(c'(v) \ne c'(u)\) (u is the parent of v). Moreover, in #3 - #5, \(c'(z) \ne c'(v)\) whenever z is a child of v that is a leaf. Therefore, \(c'(u) \ne c'(v)\) for any adjacent vertices u and v of T and so c' is proper. Hence, c is a twin (m + 2)-edge coloring of T.

Theorem 3.3. If T is a tree of order at least 3, then \(\chi'_t(T) \leq \Delta(T) + 2\).

Proof. If T is a path, then by Theorem 1.2.1, \(\chi'_t(T) = 3 = \Delta(T) + 1\). If T is a star, then by Theorem 1.2.4, \(\chi'_t(T) = \Delta(T) + 1\) or \(\Delta(T) + 2\). Moreover, if T is not a path nor a star, then by Lemmas 3.1 and 3.2, \(\chi'_t(T) \leq \Delta(T) + 2\).

Theorem 3.4. Let T be a tree that is not a star with \(\Delta(T) \geq 4\). If there exists \(v \in V(T)\) such that \(\deg(v) = \Delta(T)\) and v is adjacent to a leaf in T, then T has a twin \((\Delta(T) + 1)\)-edge coloring and \(\chi'_t(T) \leq \Delta(T) + 1\).

Proof. Suppose there exist \(u,v\in V(T)\) such that \(\deg(v)=\Delta(T),u\) is a leaf and \(u\in N_T(v)\). Let \(T^*\) be the tree obtained from T by removing the edge uv. We can take \(T^*\) as a full \((\Delta(T)-1)\)-ary tree that is not a star and with root v. By Theorem 3.3, \(\chi'_t(T^*)=(r-1)+2=r+1\). Moreover, by Algorithm 1, \(T^*\) has a twin (r+1)-edge coloring \(c^*\) with induced vertex coloring \(c^*\) such that \(c^{*'}(v)\neq 0\) and \(c^*(vw)\neq 0\) for each \(w\in N_{T^*}(v)\). Define the edge coloring c of c by \(c(e)=c^*(e)\) if \(c\in E(T^*)\) and c(uv)=0. Therefore, c is a twin c at c coloring of c.

Let us now determine the twin chromatic indices of some m-ary trees T that are not full with \(\Delta(T)=m\). We first show in the next theorem that for an even integer \(r\geq 2\), the twin chromatic index of an r-regular tree that is not a star nor a double star is r+1.

Theorem 3.5. If \(r \ge 2\) is even and T is an r-regular tree that is not a star nor a double star, then \(\chi'_t(T) = r + 1\).

Proof. If r=2, then T is a path \(P_n\), \(n\geq 5\) and so by Theorem 1.2, \(\chi'_t(T)=3=r+1\). We now assume that \(r\geq 4\). By Observations 2.1 and 2.2, \(\chi'_t(T)\geq r+1\) and so we just need to show that T has a twin (r+1)-edge coloring. Let \(u,v\in V(T)\) such that u is a leaf and \(u\in N_T(v)\). Then deg(v)=r. Let \(T^*\) be the tree obtained from T by removing the edge uv. We can take \(T^*\) as a full (r-1)-ary tree that is not a star nor a double star and with root v. By Theorem 2.6, \(\chi'_t(T^*)=(r-1)+2=r+1\). Moreover, by Algorithm 1, \(T^*\) has a twin (r+1)-edge coloring

Table 2. Values for c(vw) and \(c^{\prime}(v)\) produced by Algorithm 3

\(c^*\) with induced vertex coloring \(c^{*'}\) such that \(c^{*'}(v) \neq 0\) and \(c^*(vw) \neq 0\) for each \(w \in N_{T^*}(v)\). Define the edge coloring c of T by \(c(e) = c^*(e)\) if \(e \in E(T^*)\) and c(uv) = 0. Therefore, c is a twin (r+1)-edge coloring of T.

Let \(K_{1,m}\) be a star graph with \(V(K_{1,m})=\{v_i:i\in\{0,1,\ldots,m\}\}\) and \(E(K_{1,m})=\{e_i=v_0v_i:1\le i\le m\}\). A generalized star graph \(S(n_1,n_2,\ldots,n_m)\) is a tree obtained from the star graph \(K_{1,m}\) by replacing each edge \(e_i\) of \(K_{1,m}\) with \(P_{n_i},n_i\ge 2\) such that \(V(P_{n_i})=\{v_0^i,\ldots,v_{n_{i-1}}^i\}\), \(E(P_{n_i})=\{e_j^i=v_j^iv_{j+1}^i:0\le j\le n_i-2\}\) and \(v_0=v_0^i,1\le i\le m\). The generalized star graph S(2,4,3,3,5,2) is shown in Figure 5. We determine the chromatic indices of all generalized star graphs that are not paths nor stars.

Figure 5. The generalized star graph

Theorem 3.6. Let \(G = S(n_1, n_2, n_3)\) be a generalized star graph such that \(n_i > 3\) for at least one \(i \in \{1, 2, 3\}\). If \(n_i \not\equiv 0 \pmod{3}\) for some \(n_i > 3\) and \(n_i \not\equiv 1 \pmod{3}\) for at least two \(i \in \{1, 2, 3\}\), then \(\chi'_t(G) = 3\). Otherwise, \(\chi'_t(G) = 4\).

Proof. Case 1. Suppose \(n_i \not\equiv 0 \pmod 3\) for some \(n_i > 3\) and \(n_i \not\equiv 1 \pmod 3\) for at least two \(i \in \{1,2,3\}\). Without loss of generality, let us assume that \(n_1 > 3\) and \(n_1 \not\equiv 0 \pmod 3\). Moreover, we take \(n_1 \equiv 1 \pmod 3\) if such an \(n_i\) exists. Therefore, \(n_2, n_3 \not\equiv 1 \pmod 3\). We will construct a 3-edge coloring \(c: E(G) \to \mathbb{Z}_3\). First, define \(c(E_{v_0}) = \mathbb{Z}_3\) such that \(c(e_0^1) = 0\). Therefore, \(c'(v_0) = 0 \not\equiv c'(v_1^i)\) in each path \(P_{n_i}\) if \(n_i = 2\) and \(c'(v_1^i) \not\equiv c(e_1^i) = c'(v_2^i)\) in each path \(P_{n_i}\) if \(n_i = 3\).

Let \(c(e_j^1) = j \mod 3\) for all \(1 \le j \le n_1 - 2\). Since \(n_1 \not\equiv 0 \pmod 3\), \(c(e_{n_1-3}^1) \not\equiv 0\) and so \(c'(v_{n_1-2}^1) \not\equiv c(e_{n_1-2}^1) = c'(v_{n_1-1}^1)\).

In each path \(P_{n_l}\) with \(n_l > 2\) if any, with \(c(e_0^l) \neq 0\), we let \(c(e_j^l) = c(e_0^l) * (1-j) \mod 3\) for \(1 \leq j \leq n_l - 2\). Note that \(n_l \not\equiv 1 \pmod 3\) and so \(n_l - 3 \not\equiv 1 \pmod 3\). Then \(c(e_{n_l-3}^l) \neq 0\) and so \(c'(v_{n_l-2}^l) \neq c(e_{n_l-2}^l) = c'(v_{n_l-1}^l)\).

From the construction, we observe that c is a proper edge coloring. Now, for each path \(P_{n_i}\), \(i \in \{1, 2, 3\}\), we have \(c'(v_0) \neq c'(v_1^i)\) and \(c'(v_{n_i-2}^i) \neq c'(v_{n_i-1}^i)\). Moreover, for each path \(P_{n_q}\) with

\(n_q \ge 4\) and \(0 \le j \le n_q - 4\), we have \(c(e_j^q) \ne c(e_{j+2}^q)\) and so \(c'(v_{j+1}^q) \ne c'(v_{j+2}^q)\). Hence, c' is also proper and so c is a twin 3-edge coloring of G.

Case 2. Suppose \(n_i \equiv 0 \pmod 3\) for all \(n_i > 3\) or \(n_i \equiv 1 \pmod 3\) for at least two \(i \in \{1,2,3\}\). We will show that \(\chi'_t(G) \neq 3\), that is, G has no twin 3-edge coloring. Suppose on the contrary that G has a twin 3-edge coloring c. Then, we must have \(c(E_{v_0}) = \mathbb{Z}_3\), \(c'(v_0) = 0\) and \(c(e_0^k) = 0\) for some path \(P_{n_k}\), where \(n_k > 3\). If \(n_k \equiv 0 \pmod 3\), then we must have \(c(e_j^k) = (j*a) \mod 3\) where a = 1 or 2, for \(1 \leq j \leq n_k - 2\). Since \(n_k \equiv 0 \pmod 3\), \(n_k - 3 \equiv 0 \pmod 3\). Therefore, \(c(e_{n_k - 3}^k) = 0\) and so \(c'(v_{n_k - 2}^k) = a = c'(v_{n_k - 1}^k)\) which contradicts the assumption that c' is proper. Hence, we must not let \(c(e_0^k) = 0\) for any path \(P_{n_k}\), where \(n_k > 3\) and \(n_k \equiv 0 \pmod 3\); moreover, this implies that \(\chi'_t(G) \neq 3\) whenever \(n_i \equiv 0 \pmod 3\) for all \(n_i > 3\). Now, suppose that \(n_i \equiv 1 \pmod 3\) for at least two \(i \in \{1,2,3\}\). If \(\chi'_t(G) = 3\), then \(c(e_0^l) \neq 0\) for some path \(P_{n_l}\), where \(n_l \equiv 1 \pmod 3\) and so we must have \(c(e_j^l) = c(e_0^l) * (1-j) \mod 3\) for \(1 \leq j \leq n_l - 2\). Since \(n_l \equiv 1 \pmod 3\), \(n_l - 3 \equiv 1 \pmod 3\). Therefore, \(c(e_{n_l - 3}^l) = 0\) and so \(c'(v_{n_l - 2}^l) = -c(e_0^l) = c'(v_{n_l - 1}^l)\) which contradicts the assumption that c' is proper. Hence, \(\chi'_t(G) \neq 3\).

It remains to show that G has a twin 4-edge coloring \(c: E(G) \to \mathbb{Z}_4\). Let \(c(E_{v_0}) = \mathbb{Z}_4^*\), such that \(c(e_0^k) = 2\) for some path \(P_{n_k}\), where \(n_k \neq 2\) so that \(c'(v_0) = 2\) and \(c'(v_1^l) \neq 2\) in each path \(P_{n_l}\) with \(n_l = 2\) (if any). For each path \(P_{n_i}\) (\(n_i \geq 3\)) and for each \(j \in \{1, \ldots, n_i - 2\}\), we let

\[\text{[rumus tidak dapat ditampilkan dengan baik — lihat PDF asli]}\]

where a and b are the two distinct elements of \(\mathbb{Z}_4^*\backslash\{c(e_0^i)\}\). Then c is proper edge coloring. Now, for any path \(P_{n_i}\), \(i\in\{1,2,3\}\), \(c'(v_1^i)\neq 2\) and \(c'(v_{n_i-2}^i)\neq c'(v_{n_i-1}^i)\). Moreover, (using the same argument in Case 1), for each path \(P_{n_q}\) with \(n_q\geq 4\) and \(1\leq j\leq n_q-3\), we have \(c'(v_j^q)\neq c'(v_{j+1}^q)\). Hence, c' is also proper and so c is a twin 4-edge coloring of G.

Theorem 3.7. Let \(m \ge 4\) and \(G = S(n_1, n_2, ..., n_m)\) be a generalized star graph. If \(n_i > 3\) for at least one \(i \in \{1, ..., m\}\), then \(\chi'_t(G) = m\).

Proof. Since \(\Delta(G) = m\), \(\chi'_t(G) \geq m\). We need to show that G has a twin m-edge coloring. We will construct an m-edge coloring \(c: E(G) \to \mathbb{Z}_m\) in G. Let \(c(E_{v_0}) = \mathbb{Z}_m\) such that;

• if m is odd, \(c(e_0^k) = 0\) for some path \(P_{n_k}\), where \(n_k > 3\); and
• if m is even, \(c(e_0^k) = \frac{m}{2}\) for some path \(P_{n_k}\), where \(n_k \neq 2\) and \(c(e_0^l) = 0\) for some path \(P_{n_l}\), where \(n_l \neq 3\);

so that \(c'(v_0) \neq c'(v_1^i)\) for each path \(P_{n_i}\), \(n_i = 2\) (if any). Moreover, this coloring assures us that \(c'(v_1^i) \neq c'(v_2^i)\) whatever the color of \(e_1^i\) for each path \(P_{n_i}\), \(n_i = 3\) (if any).

For the path \(P_{n_i}\) with \(n_i > 3\), \(c(e_0^i) = 0\) and for each \(j \in \{1, \ldots, n_i - 2\}\), we let

\[\text{[rumus tidak dapat ditampilkan dengan baik — lihat PDF asli]}\]

For each path \(P_{n_i}\) with \(n_i \neq 2\) and \(c(e_0^i) \neq 0\) and for each \(j \in \{1, \ldots, n_i - 2\}\), we let

\[\text{[rumus tidak dapat ditampilkan dengan baik — lihat PDF asli]}\]

where a and b are two distinct elements of \(\mathbb{Z}_m^* \setminus \{c(e_0^i)\}\) for which \(c(e_0^i) + a \not\equiv c'(v_0) \pmod{m}\).

In any case, c is a proper edge coloring. Now, for any path \(P_{n_q}\) in G, we have \(c'(v_1^q) \neq c'(v_0^q)\) and if \(n_q \neq 2\), \(c(e_{n_q-3}^q) \neq 0\) and so \(c'(v_{n_q-2}^q) \neq c'(v_{n_q-1}^q)\). Moreover, for any path \(P_{n_q}\) with \(n_q \geq 4\) and \(0 \leq j \leq n_q - 4\), we have \(c(e_j^q) \neq c(e_{j+2}^q)\) and so \(c'(v_{j+1}^q) \neq c'(v_{j+2}^q)\). Hence, c' is also proper and so c is a twin m-edge coloring of G.

Theorem 3.8. Let \(m \geq 3\) and \(G = S(n_1, n_2, ..., n_m)\) be a generalized star graph that is not a star with \(n_i \leq 3\) for all \(i \in \{1, 2, ... m\}\). Then

\[\text{[rumus tidak dapat ditampilkan dengan baik — lihat PDF asli]}\]

Proof. Case 1. Suppose that \(n_j=2\) for some \(j\in\{1,\ldots,m\}\) and m is even. We show that G has a twin m-edge coloring \(c:E(G)\to\mathbb{Z}_m\). Without loss of generality, we suppose that \(n_1=3\) and \(n_2=2\). Let \(c(E_{v_0})=\mathbb{Z}_m\) such that \(c(e_0^1)=\frac{m}{2}\) and \(c(e_0^2)=0\). Then \(c'(v_0)=\frac{m}{2}\) and for each leaf \(z\in N(v_0), c'(z)\neq \frac{m}{2}\). Now, let \(c(e_1^1)=1\) and let \(c(e_1^q)=0\) for each \(q\neq 1\) with \(n_q=3\) so that \(c'(v_0)\neq c'(v_1^i)\) and \(c'(v_1^i)\neq c'(v_2^i)\) for each path \(P_{n_i}, n_i=3\). Hence c is a twin m-edge coloring.

Case 2. Suppose m is odd. Then G has no twin m-edge coloring since whenever 0 is assigned to any of the m adjacent edges, the coloring will induce an improper vertex coloring as shown in Figure 6. We now show that G has twin (m+1)-edge coloring \(c: E(G) \to \mathbb{Z}_{m+1}\). Let \(n_1=3\). Let \(c(E_{v_0})=\mathbb{Z}_{m+1}^*\) such that \(c(e_0^1)=\frac{m+1}{2}\) so that \(c'(v_0)=\frac{m+1}{2}\) and for each leaf \(z\in N(v_0)\), \(c'(z)\neq\frac{m+1}{2}\). Now, let \(c(e_1^1)=1\) and let \(c(e_1^l)=0\) for each path \(P_{n_l}\), \(n_l=3\), \(l\neq 1\), so that \(c'(v_0^i)\neq c'(v_1^i)\) and \(c'(v_1^i)\neq c'(v_2^i)\) for each path \(P_{n_i}\), \(n_i=3\). Hence c is a twin (m+1)-edge coloring.

Figure 6. Some improper vertex colorings in G

Case 3. Suppose m is even and \(n_i = 3\) for all \(i \in \{1, 2, ... m\}\). Using a similar argument in Case 2 shown in Figure 6.a, we conclude that \(\chi'_t(G) \neq m\). To complete the proof, we will construct

a twin (m+1)-edge coloring \(c: E(G) \to \mathbb{Z}_{m+1}\). Define c by \(c(E_{v_0}) = \mathbb{Z}_{m+1}^*\) and for each path \(P_{n_i}\) in G, let \(c(i_1) = 0\). Then, c is a proper edge coloring. Moreover, \(0 = c'(v_0) \neq c'(v_1^i)\) and \(c'(v_1^i) \neq c'(v_2^i) = 0\) for each path \(P_{n_i}\) in G. Hence, c' is also proper and so c is a twin (m+1)-edge coloring of G.

We summarize Theorems 3.6, 3.7, and 3.8 in the following theorem.

Theorem 3.9. Let \(G = S(n_1, \ldots, n_m)\) be a generalized star graph that is not a star.

• 1. Let m=3. Then \(\chi'_t(G)=4\) if any of the following holds:
  • (a) each \(n_i \leq 3\),
  • (b) \(n_i \equiv 1 \pmod{3}\) for at least two i,
  • (c) at least one \(n_i > 3\) and \(n_i \equiv 0 \pmod{3}\) whenever \(n_i > 3\).

Otherwise, \(\chi'_t(G) = 3\).

2. Let \(m \ge 4\). Then \(\chi'_t(G) = m + 1\) if either (m is odd and each \(n_i \le 3\)) or (m is even and each \(n_i = 3\)); otherwise, \(\chi'_t(G) = m\).

Therefore by Theorems 1.2.1, 1.2.4 and the results in sections 2 and 3, Conjecture 1.3 is already verified for all trees. We learned that in Theorem 3.5 that for every r-regular tree T that is not a star nor a double star, \(r \ge 2\) is even, the twin chromatic index of T is r+1. Moreover, in Theorems 3.6, 3.7 and 3.8, we saw that for a generalized star graph \(G = S(n_1, \ldots, n_m)\) that is not a path nor a star, the twin chromatic index of G is either m or m+1.

Acknowledgement

The authors would like to thank the Ateneo de Manila University and Eulogio "Amang" Rodriguez Institute of Science and Technology for supporting us in this publication. Moreover, we would like to express our sincerest gratitude to the referees of this paper for their valuable comments and suggestions.

References

• [1] S. Anantharaman, Twin edge coloring of total graph and graphs with twin chromatic index \(\Delta + 2\), Appl. Appl. Math., 15 (2020), 314 336.
• [2] E. Andrews, L. Helenius, D. Johnston, J. VerWys, and P. Zhang, On twin edge colorings of graphs, Discuss. Math. Graph Theory, 34 (2014), 613 627.
• [3] E. Andrews, D. Johnston, and P. Zhang, A twin edge coloring conjecture, Bull. Inst. Combin. Appl., 70 (2014), 28 44.
• [4] E. Andrews, D. Johnston, and P. Zhang, On twin edge colorings in trees, J. Combin. Math. Combin. Comput., 94 (2015), 115 131.
• [5] S. Lakshmi and V. Kowsalya, Twin edge colourings of wheel graphs, IOSR J. Math., 12 (2016), 71 73.

• [6] R. Rajarajachozhan and R. Sampathkumar, Twin edge colorings of certain square graphs and product graphs, Electron. J. Graph Theory Appl., 4 (1) (2016), 79 – 93.
• [7] J. Tolentino, R. Marcelo, and M.A. Tolentino, Twin chromatic indices of some graphs with maximum degree 3, J. Phys.: Conf. Ser., 1538 (2020).
• [8] H. Yang, S.L. Tian, and L.W.Q. Suo, On twin edge colorings of the direct product of paths, J. Phys.: Conf. Ser., 1087 (2018).
• [9] P. Zhang, Color Induced Graph Colorings, Springer, New York, 2015.