Twin edge colorings of certain square graphs and product graphs

R. Rajarajachozhan^a , R. Sampathkumar^b

^aDepartment of Mathematics, Annamalai University, Annamalainagar 608 002, India

r.rajarajachozhan@gmail.com, sampathmath@gmail.com

A twin edge k-coloring of a graph G is a proper edge k-coloring of G with the elements of Z^k so that the induced vertex k-coloring, in which the color of a vertex v in G is the sum in Z^k of the colors of the edges incident with v, is a proper vertex k-coloring. The minimum k for which G has a twin edge k-coloring is called the twin chromatic index of G. Twin chromatic index of the square P 2 n , n ≥ 4, and the square C 2 n , n ≥ 6, are determined. In fact, the twin chromatic index of the square C 2 7 is ∆ + 2, where ∆ is the maximum degree. Twin chromatic index of C^m ✷ Pⁿ is determined, where ✷ denotes the Cartesian product. C^r and P^r are, respectively, the cycle, and the path on r vertices each.

Keywords: twin edge coloring, twin chromatic index, Cartesian product

Mathematics Subject Classification : 05C15

DOI: 10.5614/ejgta.2016.4.1.7

1. Introduction

Let G be a simple graph. A proper vertex coloring of G is an assignment from a given set of colors to the set of vertices of G, where adjacent vertices are colored differently. The minimum number of colors needed in a proper vertex coloring of G is the chromatic number of G and it is denoted by χ(G). A proper edge coloring of G is an assignment from a given set of colors to the

Received: 26 July 2015, Revised: 25 February 2016, Accepted: 13 March 2016.

^bMathematics Section, Faculty of Engineering and Technology, Annamalai University, Annamalainagar 608 002, India

set of edges of G, where adjacent edges are colored differently. The minimum number of colors needed in a proper edge coloring of G is the chromatic index of G and it is denoted by \(\chi'(G)\).

Recently, a related coloring was introduced by Chartrand and studied in [1] and [2]. For a connected graph G of order at least 3, let \(c: E(G) \to \mathbb{Z}_k\) be a proper edge k-coloring of G for some integer \(k \geq 2\). A vertex k-coloring \(\sigma_c: V(G) \to \mathbb{Z}_k\) is then defined by

\[\sigma_c(v) = \sum_{e \in E_v} c(e)\]

in \(\mathbb{Z}_k\), where \(E_v\) is the set of edges of G incident with a vertex v and the indicated sum is computed in \(\mathbb{Z}_k\). If the induced vertex k-coloring \(\sigma_c\) is proper, then c is called a twin edge k-coloring of G. The minimum k for which G has a twin edge k-coloring is called the twin chromatic index of G and it is denoted by \(\chi_t'(G)\). Since a twin edge coloring is not only a proper edge coloring of G but induces a proper vertex coloring of G, it follows that

\[\chi_t'(G) \ge \max\{\chi(G), \chi'(G)\}.\]

For every connected graph G that is neither an odd cycle nor a complete graph, \(\chi(G) \leq \Delta(G) \leq \chi'(G)\); for an odd cycle \(\chi(C_{2n+1}) = 3 = \chi'(C_{2n+1})\); for the complete graph of odd order \(\chi(K_{2n+1}) = \chi'(K_{2n+1})\); and for the complete graph of even order \(\chi(K_{2n}) = 1 + \chi'(K_{2n})\). Hence \(\chi_t'(G) \geq \max\{\chi(G), \chi'(G)\} = \chi'(G)\) except when G is a complete graph of even order. \(\chi_t'(G)\) does not exist if G is the connected graph of order G, and it was observed in [1] that every connected graph of order at least G has a twin edge coloring.

In [1], Andrews et~al. obtained the twin chromatic indexes of paths, complete graphs and complete bipartite graphs. If n,a,b are integers with \(n\geq 3,\,1\leq a\leq b\) and \(b\geq 2\), then \(\chi_t'(P_n)=3,\,\chi_t'(C_n)=3\) if \(n\equiv 0\,(\bmod{3}),\,\chi_t'(C_n)=4\) if \(n\not\equiv 0\,(\bmod{3})\) and \(n\not\equiv 5,\,\chi_t'(C_5)=5,\,\chi_t'(K_n)=n\) if n is odd, \(\chi_t'(K_n)=n+1\) if n is even, \(\chi_t'(K_{1,b})=b+1\) if \(b\not\equiv 1\,(\bmod{4}),\,\chi_t'(K_{1,b})=b+2\) if \(b\equiv 1\,(\bmod{4}),\,\chi_t'(K_{a,a})=a+2=\chi_t'(K_{a,a+1})\) if \(a\geq 2\), and \(\chi_t'(K_{a,b})=b\) if \(b\geq a+2\) and \(a\geq 2\).

The Cartesian product \(G \square H\) of two simple graphs G and H is the simple graph with vertex set \(V(G) \times V(H)\), and two vertices \((u_1, u_2)\) and \((v_1, v_2)\) of \(G \square H\) are adjacent if and only if either \(u_1 = v_1\) and \(u_2v_2 \in E(H)\) or \(u_2 = v_2\) and \(u_1v_1 \in E(G)\).

In [2], Andrews et al. obtained the twin chromatic indexes for grids, prisms and trees with small maximum degree. If \(n \geq 3\) is an integer with \(n \neq 5\), then \(\chi_t^{'}(C_n \square K_2) = 4\). For n = 5, \(\chi_t^{'}(C_5 \square K_2) = 5\). If \(n \geq 2\) is an integer, then \(\chi_t^{'}(P_n \square K_2) = 4\). If n and q are integers with \(n, q \geq 3\), then \(\chi_t^{'}(P_n \square P_q) = 5\). Every tree T having maximum degree at most q has q having q having maximum degree at most q has q had q had q had q had q had q had q had q had q had q had q had q had q had q had q had q had q had q had q had q had q had q had q had q had q had q had q had q had q had q had q had q had q had q had q had q had q had q had q had q had q had q had q had q had q had q had q had q had q had q had q had q had q had q had q had q had q had q had q had q had q had q had q had q had q had q had q had q had q had q had q had q had q had q had q had q had q had q had q had q had q had q had q had q had q had q had q had q had q had q had q had q had q had q had q had q had q had q had q had q had q had q had q had q had q had q had q had q had q had q had q had q had q had q had q had q had q had q had q had q had q had q had q had q had q had q had q had q had q had q had q had q had q had q had q had q had q had q had q had q had q had q had q had q had q had q had q had q had q had q had q had q had q had q had q had q had q had q had q had q had q had q had q had q had q had q had q had q had q had q had q had q had q had q had q had q had q had q had q had q had q had q had q had q had q had q had q had q had q had q had q had q had q had q had q had q had q had q h

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

Observation 1.1. If a connected graph G contains two adjacent vertices of degree \(\Delta(G)\), then \(\chi_t'(G) \geq 1 + \Delta(G)\).

The k-th power of a simple graph G is the simple graph \(G^k\) with vertex set V(G) and edge set \(\{uv \mid d_G(u,v) \leq k\}\). Notation and terminalogy not mentioned here can be found in [3].

2. \(\chi'_{\star}(P_{\pi}^{2})\)

Let \(P_n := x_1 x_2 x_3 \dots x_n\). Consider \(P_n^2\). For \(i \in \{1, 2, \dots, n-1\}\), let \(e_i = x_i x_{i+1}\) and for \(i \in \{1, 2, \dots, n-2\}, \text{ let } f_i = x_i x_{i+2}.\)

Define \(c: E(P_4^2) \to \mathbb{Z}_4\) as follows: \(c(e_1) = 3\), \(c(e_2) = 2\), \(c(e_3) = 3\), \(c(f_1) = 0\), \(c(f_2) = 1\). The induced vertex coloring is: \(\sigma_c(x_1) = 3\), \(\sigma_c(x_2) = 2\), \(\sigma_c(x_3) = 1\), \(\sigma_c(x_4) = 0\), and it is proper. Hence \(\chi'_t(P_4^2) \leq 4\). By Observation 1.1, \(\chi'_t(P_4^2) \geq 4\) and so \(\chi'_t(P_4^2) = 4\).

Define \(c: E(P_5^2) \to \mathbb{Z}_4\) as follows: \(c(e_1) = 1\), \(c(e_2) = 2\), \(c(e_3) = 3\), \(c(e_4) = 2\), \(c(f_1) = 2\)\(c(f_2) = 0\), \(c(f_3) = 1\). The induced vertex coloring is: \(\sigma_c(x_1) = 1\), \(\sigma_c(x_2) = 3\), \(\sigma_c(x_3) = 2\), \(\sigma_c(x_4) = 1, \, \sigma_c(x_5) = 3, \, \text{and it is proper. Hence } \chi_t'(P_5^2) \leq 4. \, \text{As } \chi_t'(P_5^2) \geq \Delta(P_5^2) = 4, \, \text{we}\)have \(\chi'_{t}(P_{5}^{2}) = 4\).

For \(n \geq 6\), define \(c: E(P_n^2) \to \mathbb{Z}_5\) as follows:

\[c(e_1) = 3,\]

\[c(e_i) = i \pmod{5} \text{ if } 2 \le i \le n-2,\]

\[c(e_{n-1}) = \begin{cases} 2 \text{ if } n \equiv 0 \pmod{5}, \\ 3 \text{ if } n \equiv 1, \ 4 \pmod{5}, \\ 4 \text{ if } n \equiv 2 \pmod{5}, \\ 0 \text{ if } n \equiv 3 \pmod{5}, \end{cases}\]

\[c(f_1) = 0\],

\[c(f_i) = (i-2) \pmod{5} \text{ if } 2 \le i \le n-3\]

\[c(f_1) = 0,\] \[c(f_i) = (i-2) \pmod{5} \text{ if } 2 \le i \le n-3,\] \[c(f_{n-2}) = \begin{cases} (n-4) \pmod{5} \text{ if } n \equiv 1, 2, 4 \pmod{5}, \\ n \pmod{5} \text{ if } n \equiv 0, 3 \pmod{5}. \end{cases}\]

The induced vertex coloring is:

\[\sigma_c(x_1) = c(e_1) + c(f_1) = 3 + 0 \equiv 3;\]

\[\sigma_c(x_2) = c(e_1) + c(e_2) + c(f_2) = 3 + 2 + 0 \equiv 0;\]

\[\sigma_c(x_3) = c(e_2) + c(e_3) + c(f_1) + c(f_3) = 2 + 3 + 0 + 1 \equiv 1;\]

for \[4 \le i \le n-3\],
\(\sigma_c(x_i) = c(e_{i-1}) + c(e_i) + c(f_{i-2}) + c(f_i) = (i-1) + i + (i-4) + (i-2) = 4i-7\) \[\begin{cases} 4 & \text{if } i \equiv 4 \pmod{5}, \\ 3 & \text{if } i \equiv 0 \pmod{5}, \\ 2 & \text{if } i \equiv 1 \pmod{5}, \\ 1 & \text{if } i \equiv 2 \pmod{5}, \\ 0 & \text{otherwise} \end{cases}\]

\[\begin{cases} 0 \text{ if } i \equiv 2 \pmod{5}, \\ 0 \text{ if } i \equiv 3 \pmod{5}; \end{cases}\] \[\sigma_c(x_{n-2}) = c(e_{n-3}) + c(e_{n-2}) + c(f_{n-4}) + c(f_{n-2}) = (n-3) + (n-2) + (n-6) + c(f_{n-2})\] \[= 3n - 11 + c(f_{n-2}) \equiv \begin{cases} 4 \text{ if } n \equiv 0, 1 \pmod{5}, \\ 3 \text{ if } n \equiv 2 \pmod{5}, \\ 1 \text{ if } n \equiv 3, 4 \pmod{5}; \end{cases}\] \[\sigma_c(x_{n-1}) = c(e_{n-2}) + c(e_{n-1}) + c(f_{n-3}) = (n-2) + c(e_{n-1}) + (n-5) = 2n - 7 + c(e_{n-1})\]

\[\sigma_c(x_{n-1}) = c(e_{n-2}) + c(e_{n-1}) + c(f_{n-3}) = (n-2) + c(e_{n-1}) + (n-5) = 2n - 7 + c(e_{n-1})\]

\[\equiv \begin{cases} 0 \text{ if } n \equiv 0 \pmod{5}, \\ 3 \text{ if } n \equiv 1 \pmod{5}, \\ 1 \text{ if } n \equiv 2 \pmod{5}, \\ 4 \text{ if } n \equiv 3, \ 4 \pmod{5}; \end{cases}\] \[\sigma_c(x_n) = c(e_{n-1}) + c(f_{n-2}) \equiv \begin{cases} 2 \text{ if } n \equiv 0, \ 2 \pmod{5}, \\ 0 \text{ if } n \equiv 1 \pmod{5}, \\ 3 \text{ if } n \equiv 3, \ 4 \pmod{5}. \end{cases}\]

The sequence \(\{\sigma_c(x_1),\sigma_c(x_2),\sigma_c(x_3),\dots\}\) is of the form \(\{3,0,1,4,3,2,1,0,4,3,2,1,0,\dots\}\) and its end \(\{\ldots,\sigma_c(x_{n-2}),\sigma_c(x_{n-1}),\sigma_c(x_n)\}\) is of the form \(\{\ldots,4,3,2,1,0,4,3,2,1,4,0,2\}\) if \(n\equiv 0\ (\bmod\ 5),\{\ldots,4,3,2,1,0,4,3,0\}\) if \(n\equiv 1\ (\bmod\ 5),\{\ldots,4,3,2,1,0,4,3,1,2\}\) if \(n\equiv 2\ (\bmod\ 5),\{\ldots,4,3,2,1,0,4,3,1,4,3\}\) if \(n\equiv 3\ (\bmod\ 5)\), and \(\{\ldots,4,3,2,1,0,4,3,2,1,4,3\}\) if \(n\equiv 4\ (\bmod\ 5)\). Hence c is a twin edge 5-coloring of \(P_n^2\) and therefore \(\chi_t'(P_n^2)\le 5\). By Observation \(1.1,\chi_t'(P_n^2)\ge 5\), and so \(\chi_t'(P_n^2)=5\).

Thus, we have the following theorem.

Theorem 2.1. \[\chi'_t(P_4^2) = 4\], \(\chi'_t(P_5^2) = 4\), and for \(n \geq 6\), \(\chi'_t(P_n^2) = 5\).

3. \[\chi_{t}'(C_{n}^{2})\]

Let \(C_n := x_1 x_2 x_3 \dots x_n x_1\). For \(n \geq 6\), consider \(C_n^2\). For \(i \in \{1, 2, \dots, n\}\), \(e_i = x_i x_{i+1}\) and \(f_i = x_i x_{i+2}\), where \(x_{n+1} = x_1\) and \(x_{n+2} = x_2\). By Observation 1.1, \(\chi_t'(C_n^2) \geq 5\).

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

The induced vertex coloring is:

\[\sigma_c(x_i) = c(e_{i-1}) + c(e_i) + c(f_{i-2}) + c(f_i) = \begin{cases} 1 \text{ if } i \equiv 1 \pmod{3}, \\ 3 \text{ if } i \equiv 2 \pmod{3}, \\ 2 \text{ if } i \equiv 0 \pmod{3}. \end{cases}\]

Hence c is a twin edge 5-coloring of \(C_n^2\) and therefore \(\chi_t'(C_n^2) \leq 5\).

• For \(n \equiv 5 \pmod{6}\) and \(n \ge 11\), define \(c : E(C_n^2) \to \mathbb{Z}_5\) as follows: For \(i \in \{1, 2, \dots, n-3\}\), \(c(e_i) = \begin{cases} 0 \text{ if } i \text{ is odd,} \\ 1 \text{ if } i \text{ is even,} \end{cases}\) \(c(e_{n-2}) = 2,\) \(c(e_{n-1}) = 3,\)

\[c(e_n) = 4.\] For \(i \in \{1, 2, \dots, n-3\}\), \(c(f_i) = \begin{cases} 3 \text{ if } i \equiv 1 \pmod{3}, \\ 4 \text{ if } i \equiv 2 \pmod{3}, \\ 2 \text{ if } i \equiv 0 \pmod{3}, \end{cases}\) \[c(f_{n-2}) = 0,\] \[c(f_{n-1}) = 1,\] \[c(f_n) = 2.\]

The induced vertex coloring is:

For \[i \in \{2,3,\ldots,n-3\}\], \(\sigma_c(x_i) = c(e_{i-1}) + c(e_i) + c(f_{i-2}) + c(f_i) = 1 + c(f_{i-2}) + c(f_i)\) \[= \begin{cases} 1+4+3=3 \text{ if } i \equiv 1 \pmod{3}, \\ 1+2+4=2 \text{ if } i \equiv 2 \pmod{3}, \\ 1+3+2=1 \text{ if } i \equiv 0 \pmod{3}. \end{cases}\] \[\sigma_c(x_{n-2}) = c(e_{n-3}) + c(e_{n-2}) + c(f_{n-4}) + c(f_{n-2}) = 1 + 2 + 3 + 0 = 1.\] \[\sigma_c(x_{n-1}) = c(e_{n-2}) + c(e_{n-1}) + c(f_{n-3}) + c(f_{n-1}) = 2 + 3 + 4 + 1 = 0.\] \[\sigma_c(x_n) = c(e_{n-1}) + c(e_n) + c(f_{n-2}) + c(f_n) = 3 + 4 + 0 + 2 = 4.\] \[\sigma_c(x_1) = c(e_n) + c(e_1) + c(f_{n-1}) + c(f_1) = 4 + 0 + 1 + 3 = 3.\] Hence \(c\) is a twin edge 5-coloring of \(C_n^2\) and therefore \(\chi_t'(C_n^2) \leq 5\).

• For n ≡ 4 ( mod 6) and n ≥ 10, define c : E(C 2 n ) → Z⁵ as follows:

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

The induced vertex coloring is:

For \[i \in \{2, 3, ..., n - 8\}\], \(\sigma_c(x_i) = c(e_{i-1}) + c(e_i) + c(f_{i-2}) + c(f_i) = 1 + c(f_{i-2}) + c(f_i)\)

\[= \begin{cases} 1+4+3=3 \text{ if } i \equiv 1 \pmod{3}, \\ 1+2+4=2 \text{ if } i \equiv 2 \pmod{3}, \\ 1+3+2=1 \text{ if } i \equiv 0 \pmod{3}. \end{cases}\] \[\sigma_c(x_{n-7}) = c(e_{n-8}) + c(e_{n-7}) + c(f_{n-9}) + c(f_{n-7}) = 1+2+3+0 = 1.\] \[\sigma_c(x_{n-6}) = c(e_{n-7}) + c(e_{n-6}) + c(f_{n-8}) + c(f_{n-6}) = 2+3+4+1 = 0.\] \[\sigma_c(x_{n-5}) = c(e_{n-6}) + c(e_{n-5}) + c(f_{n-7}) + c(f_{n-5}) = 3+4+0+2 = 4.\] \[\sigma_c(x_{n-4}) = c(e_{n-5}) + c(e_{n-4}) + c(f_{n-6}) + c(f_{n-4}) = 4+0+1+3 = 3.\] \[\sigma_c(x_{n-3}) = c(e_{n-4}) + c(e_{n-3}) + c(f_{n-5}) + c(f_{n-3}) = 0+1+2+4 = 2.\] \[\sigma_c(x_{n-2}) = c(e_{n-3}) + c(e_{n-2}) + c(f_{n-4}) + c(f_{n-2}) = 1+2+3+0 = 1.\] \[\sigma_c(x_{n-1}) = c(e_{n-2}) + c(e_{n-1}) + c(f_{n-3}) + c(f_{n-1}) = 2+3+4+1 = 0.\] \[\sigma_c(x_n) = c(e_{n-1}) + c(e_n) + c(f_{n-2}) + c(f_n) = 3+4+0+2 = 4.\] \[\sigma_c(x_1) = c(e_n) + c(e_1) + c(f_{n-1}) + c(f_1) = 4+0+1+3 = 3.\] Hence \(c\) is a twin edge 5-coloring of \(C_n^2\) and therefore \(\chi_t'(C_n^2) \leq 5.\)

• For n ≡ 3 ( mod 6) and n ≥ 15, define c : E(C 2 n ) → Z⁵ as follows:

\[\begin{aligned} & \text{For } i \in \{1,2,\ldots,n-13\}, \, c(e_i) \, = \, \begin{cases} 0 \text{ if } i \text{ is odd,} \\ 1 \text{ if } i \text{ is even,} \end{cases} \\ & c(e_{n-12}) \, = \, c(e_{n-7}) \, = \, c(e_{n-2}) \, = \, 2, \\ & c(e_{n-11}) \, = \, c(e_{n-6}) \, = \, c(e_{n-1}) \, = \, 3, \\ & c(e_{n-10}) \, = \, c(e_{n-5}) \, = \, c(e_n) \, = \, 4, \\ & c(e_{n-9}) \, = \, c(e_{n-4}) \, = \, 0, \\ & c(e_{n-8}) \, = \, c(e_{n-3}) \, = \, 1. \end{aligned}\] \[\text{[rumus tidak dapat ditampilkan dengan baik — lihat PDF asli]}\] \[\text{[rumus tidak dapat ditampilkan dengan baik — lihat PDF asli]}\]

\[c(f_{n-1}) = c(f_{n-1}) = 1,\] \[c(f_{n-1}) = c(f_{n-1}) = c(f_n) = 2,\] \[c(f_{n-9}) = c(f_{n-4}) = 3,\] \[c(f_{n-8}) = c(f_{n-3}) = 4.\]

The induced vertex coloring is:

For \[i \in \{2, 3, \dots, n-13\}\], \(\sigma_c(x_i) = \begin{cases} 3 \text{ if } i \equiv 1 \pmod{3}, \\ 2 \text{ if } i \equiv 2 \pmod{3}, \\ 1 \text{ if } i \equiv 0 \pmod{3}, \end{cases}\) \[\sigma_c(x_{n-12}) = \sigma_c(x_{n-7}) = \sigma_c(x_{n-2}) = 1.\] \[\sigma_c(x_{n-11}) = \sigma_c(x_{n-6}) = \sigma_c(x_{n-1}) = 0.\] \[\sigma_c(x_{n-10}) = \sigma_c(x_{n-5}) = \sigma_c(x_n) = 4.\] \[\sigma_c(x_{n-9}) = \sigma_c(x_{n-4}) = \sigma_c(x_1) = 3.\] \[\sigma_c(x_{n-8}) = \sigma_c(x_{n-3}) = 2.\]

Hence c is a twin edge 5-coloring of C 2 n and therefore χ 0 t (C 2 n ) ≤ 5.

• For \[n=9\], define \(c: E(C_9^2) \to \mathbb{Z}_5\) as follows: \(c(e_1)=c(e_3)=c(e_5)=c(f_7)=0\), \(c(f_3)=c(f_6)=c(f_9)=1\), \(c(f_2)=c(f_5)=c(f_8)=2\), \(c(e_4)=c(e_6)=c(e_8)=c(f_1)=3\), \(c(e_2)=c(e_7)=c(e_9)=c(f_4)=4\).

The induced vertex coloring is:

\[\sigma_c(x_8) = 0, \, \sigma_c(x_5) = 1, \, \sigma_c(x_2) = 2, \, \sigma_c(x_3) = \sigma_c(x_6) = \sigma_c(x_9) = 3,\]
\(\sigma_c(x_1) = \sigma_c(x_4) = \sigma_c(x_7) = 4.\)

Hence c is a twin edge 5-coloring of C 2 9 and therefore χ 0 t (C 2 9 ) ≤ 5.

• For n ≡ 2 ( mod 6) and n ≥ 20, define c : E(C 2 n ) → Z⁵ as follows:

\[\begin{aligned} &\text{For } i \in \{1,2,\ldots,n-18\}, \, c(e_i) = \begin{cases} 0 \text{ if } i \text{ is odd,} \\ 1 \text{ if } i \text{ is even,} \end{cases} \\ &c(e_{n-17}) = c(e_{n-12}) = c(e_{n-7}) = c(e_{n-2}) = 2, \\ &c(e_{n-16}) = c(e_{n-11}) = c(e_{n-6}) = c(e_{n-1}) = 3, \\ &c(e_{n-15}) = c(e_{n-10}) = c(e_{n-5}) = c(e_n) = 4, \\ &c(e_{n-14}) = c(e_{n-9}) = c(e_{n-4}) = 0, \\ &c(e_{n-13}) = c(e_{n-8}) = c(e_{n-3}) = 1. \end{aligned}\] \[\begin{cases} 3 \text{ if } i \equiv 1 \pmod{3}, \\ 4 \text{ if } i \equiv 2 \pmod{3}, \\ 2 \text{ if } i \equiv 0 \pmod{3}, \end{cases}\] \[\text{[rumus tidak dapat ditampilkan dengan baik — lihat PDF asli]}\]

The induced vertex coloring is:

For \[i \in \{2, 3, \dots, n-18\}\], \(\sigma_c(x_i) = \begin{cases} 3 \text{ if } i \equiv 1 \pmod{3}, \\ 2 \text{ if } i \equiv 2 \pmod{3}, \\ 1 \text{ if } i \equiv 0 \pmod{3}, \end{cases}\) \[\sigma_c(x_{n-17}) = \sigma_c(x_{n-12}) = \sigma_c(x_{n-7}) = \sigma_c(x_{n-2}) = 1.\] \[\sigma_c(x_{n-16}) = \sigma_c(x_{n-11}) = \sigma_c(x_{n-6}) = \sigma_c(x_{n-1}) = 0.\] \[\sigma_c(x_{n-15}) = \sigma_c(x_{n-10}) = \sigma_c(x_{n-5}) = \sigma_c(x_n) = 4.\] \[\sigma_c(x_{n-14}) = \sigma_c(x_{n-9}) = \sigma_c(x_{n-4}) = \sigma_c(x_1) = 3.\] \[\sigma_c(x_{n-13}) = \sigma_c(x_{n-8}) = \sigma_c(x_{n-3}) = 2.\] Hence \(c\) is a twin edge 5-coloring of \(C_n^2\) and therefore \(\chi_t'(C_n^2) \leq 5\).

• For n = 8, define c : E(C 2 8 ) → Z⁵ as follows:

\[c(e_5) = c(f_2) = c(f_7) = 0, c(e_7) = c(f_1) = c(f_4) = 1, c(e_1) = c(f_3) = c(f_6) = 2,\]
\(c(e_3) = c(f_5) = c(f_8) = 3, c(e_2) = c(e_4) = c(e_6) = c(e_8) = 4.\)

The induced vertex coloring is:

\[\sigma_c(x_3) = \sigma_c(x_8) = 0, \ \sigma_c(x_1) = \sigma_c(x_6) = 2, \ \sigma_c(x_4) = \sigma_c(x_7) = 3, \ \sigma_c(x_2) = \sigma_c(x_5) = 4.\] Hence \(c\) is a twin edge 5-coloring of \(C_8^2\) and therefore \(\chi_t'(C_8^2) \leq 5\).

• For n = 14, define c : E(C 2 ¹⁴) → Z⁵ as follows: c(e5) = c(e7) = c(e9) = c(e11) = c(f2) = c(f13) = 0, c(e13) = c(f1) = c(f4) = c(f7) = c(f10) = 1, c(e1) = c(f3) = c(f6) = c(f9) = c(f12) = 2, c(e3) = c(f5) = c(f8) = c(f11) = c(f14) = 3, c(e2) = c(e4) = c(e6) = c(e8) = c(e10) = c(e12) = c(e14) = 4.

The induced vertex coloring is:

\[\sigma_c(x_3) = \sigma_c(x_{14}) = 0, \ \sigma_c(x_1) = \sigma_c(x_6) = \sigma_c(x_9) = \sigma_c(x_{12}) = 2,\] \(\sigma_c(x_4) = \sigma_c(x_7) = \sigma_c(x_{10}) = \sigma_c(x_{13}) = 3, \ \sigma_c(x_2) = \sigma_c(x_5) = \sigma_c(x_8) = \sigma_c(x_{11}) = 4.\) Hence \(c\) is a twin edge 5-coloring of \(C_{14}^2\) and therefore \(\chi_t'(C_{14}^2) \leq 5\).

• For n ≡ 1 ( mod 6) and n ≥ 25, define c : E(C 2 n ) → Z⁵ as follows:

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

The induced vertex coloring is:

For \[i \in \{2, 3, \dots, n-23\}\], \(\sigma_c(x_i) = \begin{cases} 3 \text{ if } i \equiv 1 \pmod{3}, \\ 2 \text{ if } i \equiv 2 \pmod{3}, \\ 1 \text{ if } i \equiv 0 \pmod{3}. \end{cases}\) \[\sigma_c(x_{n-22}) = \sigma_c(x_{n-17}) = \sigma_c(x_{n-12}) = \sigma_c(x_{n-7}) = \sigma_c(x_{n-2}) = 1.\] \[\sigma_c(x_{n-21}) = \sigma_c(x_{n-16}) = \sigma_c(x_{n-11}) = \sigma_c(x_{n-6}) = \sigma_c(x_{n-1}) = 0.\] \[\sigma_c(x_{n-20}) = \sigma_c(x_{n-15}) = \sigma_c(x_{n-10}) = \sigma_c(x_{n-5}) = \sigma_c(x_n) = 4.\] \[\sigma_c(x_{n-19}) = \sigma_c(x_{n-14}) = \sigma_c(x_{n-9}) = \sigma_c(x_{n-4}) = \sigma_c(x_1) = 3.\]

\[\sigma_c(x_{n-18}) = \sigma_c(x_{n-13}) = \sigma_c(x_{n-8}) = \sigma_c(x_{n-3}) = 2.\] Hence \(c\) is a twin edge 5-coloring of \(C_n^2\) and therefore \(\chi_t'(C_n^2) \leq 5\).

• For n = 19, define c : E(C 2 ¹⁹) → Z⁵ as follows: c(e1) = c(e3) = c(e5) = c(e7) = c(e9) = c(e11) = c(e13) = c(e15) = c(f17) = 0, c(e16) = c(e18) = c(f1) = c(f4) = c(f7) = c(f10) = c(f13) = 1, c(e12) = c(e17) = c(f3) = c(f6) = c(f9) = c(f14) = c(f19) = 2, c(e2) = c(e4) = c(e6) = c(e8) = c(e10) = c(f12) = c(f15) = c(f18) = 3, c(e14) = c(e19) = c(f2) = c(f5) = c(f8) = c(f11) = c(f16) = 4.

The induced vertex coloring is:

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

• For n = 13, define c : E(C 2 ¹³) → Z⁵ as follows: c(e1) = c(e3) = c(e5) = c(e7) = c(e9) = c(f11) = 0, c(e10) = c(e12) = c(f1) = c(f4) = c(f7) = 1, c(e6) = c(e11) = c(f3) = c(f8) = c(f13) = 2, c(e2) = c(e4) = c(f6) = c(f9) = c(f12) = 3, c(e8) = c(e13) = c(f2) = c(f5) = c(f10) = 4.

The induced vertex coloring is:

\[\sigma_c(x_{12}) = 0, \ \sigma_c(x_3) = \sigma_c(x_6) = \sigma_c(x_{11}) = 1, \sigma_c(x_7) = \sigma_c(x_{10}) = \sigma_c(x_{13}) = 2, \ \sigma_c(x_1) = \sigma_c(x_4) = \sigma_c(x_9) = 3, \sigma_c(x_2) = \sigma_c(x_5) = \sigma_c(x_8) = 4.\]

Hence c is a twin edge 5-coloring of C 2 ¹³ and therefore χ 0 t (C 2 ¹³) ≤ 5.

• For n = 7, define c : E(C 2 7 ) → Z⁶ as follows: c(e2) = c(e4) = c(e6) = 0,

\[c(e_1) = 1, c(e_3) = c(e_5) = c(e_7) = 2,\]
\(c(f_1) = c(f_4) = c(f_7) = 3, c(f_2) = c(f_5) = 4, c(f_3) = c(f_6) = 5.\)

The induced vertex coloring is:

\[\sigma_c(x_2)=2,\] \(\sigma_c(x_4)=\sigma_c(x_7)=3,\) \(\sigma_c(x_3)=\sigma_c(x_6)=4,\) \(\sigma_c(x_1)=\sigma_c(x_5)=5.\) Hence \(c\) is a twin edge 6-coloring of \(C_7^2\) and therefore \(\chi_t'(C_7^2)\leq 6.\)

Lemma 3.1. Let G be a k-regular graph of odd order at least k + 2. If for any two nonadjacent vertices u and v, NG(u) ∪ NG(v) = V (G) \ {u, v}, then χ 0 t (G) ≥ k + 2.

Proof. Suppose χ 0 t (G) = k+1. Then there exists a twin edge (k+1)-coloring c : E(G) → Zk+1. As G is k-regular, for any vertex x, some color cⁱ is not represented for the edges incident at x. Since there are k + 1 colors and |V (G)| > k + 1, by pigeonhole principle, some color, say, i is not represented at two vertices. Since σ^c is equal for these two vertices, they are nonadjacent. Let

the two nonadjacent vertices be u and v. By hypothesis, i must be represented at all the vertices of V (G) \ {u, v}. This is clearly impossible, since |V (G) \ {u, v}| is odd.

By Lemma 3.1, χ 0 t (C 2 7 ) ≥ 6.

Thus we have:

Theorem 3.1. Let n ≥ 6. If n 6= 7, then χ 0 t (C 2 n ) = 5. Also, χ 0 t (C 2 7 ) = ∆(C 2 7 ) + 2 = 6.

4. χ 0 t (C^m ✷ Pn)

Let m ≥ 3, n ≥ 3, C^m := x1x2x³ . . . xmx¹ and Pⁿ := y1y2y³ . . . yn. For convenience, assume xm+1 = x1.

By Observation 1.1, χ 0 t (C^m ✷ Pn) ≥ 5.

Theorem 4.1. For m ≥ 3 and n ≥ 3, χ 0 t (C^m ✷ Pn) = 5.

Proof. We consider three cases and in each case, we first define c : V (C^m ✷ Pn) → Z5.

Case 1. m is even.

\[c((x_{i},y_{j})(x_{i+1},y_{j})) = \begin{cases} 0 \text{ if } i \text{ is even,} \\ 1 \text{ if } i \text{ is odd;} \end{cases}\] \[\text{for } j \equiv 1 \pmod{3}, c((x_{i},y_{j})(x_{i},y_{j+1})) = \begin{cases} 3 \text{ if } i \text{ is odd,} \\ 2 \text{ if } i \text{ is even;} \end{cases}\] \[\text{for } j \equiv 2 \pmod{3}, c((x_{i},y_{j})(x_{i},y_{j+1})) = \begin{cases} 4 \text{ if } i \text{ is odd,} \\ 3 \text{ if } i \text{ is even;} \end{cases}\] \[\text{for } j \equiv 0 \pmod{3}, c((x_{i},y_{j})(x_{i},y_{j+1})) = \begin{cases} 2 \text{ if } i \text{ is odd,} \\ 4 \text{ if } i \text{ is even.} \end{cases}\]

Then the induced vertex coloring is:

\[\sigma_c((x_i, y_1)) = \begin{cases} 4 \text{ if } i \text{ is odd,} \\ 3 \text{ if } i \text{ is even.} \end{cases}\] \[\text{For } n \equiv 2 \pmod{3}, \, \sigma_c((x_i, y_n)) = \begin{cases} 4 \text{ if } i \text{ is odd,} \\ 3 \text{ if } i \text{ is even.} \end{cases}\] \[\text{For } n \equiv 0 \pmod{3}, \, \sigma_c((x_i, y_n)) = \begin{cases} 0 \text{ if } i \text{ is odd,} \\ 4 \text{ if } i \text{ is even.} \end{cases}\] \[\text{For } n \equiv 1 \pmod{3}, \, \sigma_c((x_i, y_n)) = \begin{cases} 3 \text{ if } i \text{ is odd,} \\ 0 \text{ otherwise.} \end{cases}\]

4 if i is odd,

For \[j \equiv 2 \pmod{3}\] and for \(j \neq n\), \(\sigma_c((x_i, y_j)) = \begin{cases} 3 \text{ if } i \text{ is odd,} \\ 1 \text{ if } i \text{ is even.} \end{cases}\)
For \(j \equiv 0 \pmod{3}\) and for \(j \neq n\), \(\sigma_c((x_i, y_j)) = \begin{cases} 2 \text{ if } i \text{ is odd,} \\ 3 \text{ if } i \text{ is even.} \end{cases}\)

0 if i is even.

For \[j \equiv 1 \pmod{3}\] and for \(j \notin \{1, n\}\), \(\sigma_c((x_i, y_j)) = \begin{cases} 1 \text{ if } i \text{ is odd,} \\ 2 \text{ if } i \text{ is even.} \end{cases}\)
It can be verified that \(c\) is a twin edge 5-coloring of \(C_m \square P_n\).

Case 2. m is odd and n 6≡ 2 ( mod 3).

For \[i \in \{1, 2, \dots, m-2\}\], \(c((x_i, y_j)(x_{i+1}, y_j)) = \begin{cases} 1 \text{ if } i \text{ is odd,} \\ 0 \text{ if } i \text{ is even;} \end{cases}\) \(c((x_{m-1}, y_j)(x_m, y_j)) = 2;\) \(c((x_m, y_j)(x_1, y_j)) = 0;\) for \(i \in \{1, 2, \dots, m-2\}\) and \(j \equiv 1 \pmod{3}\), \(c((x_i, y_j)(x_i, y_{j+1})) = \begin{cases} 2 \text{ if } i \text{ is odd,} \\ 3 \text{ if } i \text{ is even;} \end{cases}\) for \(j \equiv 1 \pmod{3}\), \(c((x_{m-1}, y_j)(x_{m-1}, y_{j+1})) = 4\), \(c((x_m, y_j)(x_m, y_{j+1})) = 3;\) for \(j \equiv 2 \pmod{3}\), \(c((x_{m-1}, y_j)(x_{m-1}, y_{j+1})) = 3\), \(c((x_m, y_j)(x_m, y_{j+1})) = 1;\) for \(j \equiv 2 \pmod{3}\), \(c((x_{m-1}, y_j)(x_{m-1}, y_{j+1})) = 3\), \(c((x_m, y_j)(x_m, y_{j+1})) = 1;\) for \(j \equiv 0 \pmod{3}\), \(c((x_{m-1}, y_j)(x_{m-1}, y_{j+1})) = 0\), \(c((x_m, y_j)(x_m, y_{j+1})) = 4\).

Then the induced vertex coloring is:

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

= c((xm−2, yn)(xm−1, yn)) + c((xm−1, yn)(xm, yn)) + c((xm−1, yn−1)(xm−1, yn))
= 1 + 2 + c((xm−1, yn−1)(xm−1, yn));
for n ≡ 0 ( mod 3), σc((xm−1, yn)) = 1 + 2 + 3 = 1;
for n ≡ 1 ( mod 3), σc((xm−1, yn)) = 1 + 2 + 0 = 3;
for n ≡ 2 ( mod 3), σc((xm−1, yn)) = 1 + 2 + 4 = 2.
σc((xm, yn)) = c((xm−1, yn)(xm, yn)) + c((xm, yn)(x1, yn)) + c((xm−1, yn)(xm, yn))
             = 2 + 0 + c((xm, yn−1)(xm, yn));
for n ≡ 0 ( mod 3), σc((xm, yn)) = 2 + 0 + 1 = 3;
for n ≡ 1 ( mod 3), σc((xm, yn)) = 2 + 0 + 4 = 1;
for n ≡ 2 ( mod 3), σc((xm, yn)) = 2 + 0 + 3 = 0.
For i ∈ {1, 2, . . . , m − 2},
σc((xi
      , yj ))
= c((xi−1, yj )(xi
                 , yj )) + c((xi
                              , yj )(xi+1, yj )) + c((xi
                                                     , yj−1)(xi
                                                              , yj )) + c((xi
                                                                           , yj )(xi
                                                                                   , yj+1));
for j ≡ 0 ( mod 3) and j 6= n, σc((xi
                                      , yj )) = (
                                                 4 + 3 + 0 + 1 = 3 if i is odd,
                                                 2 + 4 + 1 + 0 = 2 if i is even;
for j ≡ 1 ( mod 3) and j 6∈ {1, n}, σc((xi
                                              , yj )) = (
                                                         3 + 2 + 0 + 1 = 1 if i is odd,
                                                         4 + 3 + 1 + 0 = 3 if i is even;
for j ≡ 2 ( mod 3) and j 6= n, σc((xi
                                         , yj )) = (
                                                     2 + 4 + 0 + 1 = 2 if i is odd,
                                                     3 + 2 + 1 + 0 = 1 if i is even.
σc((xm−1, yj )) = c((xm−2, yj )(xm−1, yj ))+c((xm−1, yj )(xm, yj ))+c((xm−1, yj−1)(xm−1, yj ))
                                                                 +c((xm−1, yj )(xm−1, yj+1));
for j ≡ 0 ( mod 3) and j 6= n, σc((xm−1, yj )) = 3 + 0 + 1 + 2 = 1;
for j ≡ 1 ( mod 3) and j 6∈ {1, n}, σc((xm−1, yj )) = 0 + 4 + 1 + 2 = 2;
for j ≡ 2 ( mod 3) and j 6= n, σc((xm−1, yj )) = 4 + 3 + 1 + 2 = 0.
σc((xm, yj ))
= c((xm−1, yj )(xm, yj ))+c((xm, yj )(x1, yj ))+c((xm, yj−1)(xm, yj ))+c((xm, yj )(xm, yj+1));
for j ≡ 0 ( mod 3) and j 6= n, σc((xm, yj )) = 1 + 4 + 2 + 0 = 2;
for j ≡ 1 ( mod 3) and j 6∈ {1, n}, σc((xm, yj )) = 4 + 3 + 2 + 0 = 4;
for j ≡ 2 ( mod 3) and j 6= n, σc((xm, yj )) = 3 + 1 + 2 + 0 = 1.
   It can be verified that c is a twin edge 5-coloring of Cm ✷ Pn.

Case 3. m is odd and n ≡ 2 ( mod 3).

For \[i \in \{1, 2, \dots, m-1\}\], \(c((x_i, y_j)(x_{i+1}, y_j)) = \begin{cases} 0 \text{ if } i \text{ is odd,} \\ 1 \text{ if } i \text{ is even;} \end{cases}\) \(c((x_m, y_j)(x_1, y_j)) = 2;\) for \(i \in \{1, 2, \dots, m-2\}\) and \(j \equiv 1 \pmod{3}\), \(c((x_i, y_j)(x_i, y_{j+1})) = \begin{cases} 3 \text{ if } i \text{ is odd,} \\ 2 \text{ if } i \text{ is even;} \end{cases}\) for \(j \equiv 1 \pmod{3}\), \(c((x_{m-1}, y_j)(x_{m-1}, y_{j+1})) = 4\), \(c((x_m, y_j)(x_m, y_{j+1})) = 0;\) for \(i \in \{1, 2, \dots, m-2\}\) and \(j \equiv 2 \pmod{3}\), \(c((x_i, y_j)(x_i, y_{j+1})) = \begin{cases} 4 \text{ if } i \text{ is odd,} \\ 3 \text{ if } i \text{ is even;} \end{cases}\)

for \[j \equiv 2 \pmod{3}\], \(c((x_{m-1}, y_j)(x_{m-1}, y_{j+1})) = 2\), \(c((x_m, y_j)(x_m, y_{j+1})) = 3\);
for \(j \equiv 0 \pmod{3}\), \(c((x_1, y_j)(x_1, y_{j+1})) = 1\);
for \(i \in \{2, 3, ..., m-2\}\) and \(j \equiv 0 \pmod{3}\), \(c((x_i, y_j)(x_i, y_{j+1})) = \begin{cases} 2 \text{ if } i \text{ is odd,} \\ 4 \text{ if } i \text{ is even;} \end{cases}\)
for \(j \equiv 0 \pmod{3}\), \(c((x_{m-1}, y_j)(x_{m-1}, y_{j+1})) = 3\), \(c((x_m, y_j)(x_m, y_{j+1})) = 4\).

Then the induced vertex coloring is:

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

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

It can be verified that c is a twin edge 5-coloring of C^m ✷ Pn.

This completes the proof.

5. \[\chi_t^{'}(G) = 2 + \Delta(G)\]

By Section 1, χ 0 t (G) = 2 + ∆(G) for G ∈ {Cⁿ : n ≥ 3, n 6= 5 and n 6≡ 0 ( mod 3)} ∪ {Kⁿ : n is even and n ≥ 4} ∪ {K1,b : b ≡ 1 ( mod 4) and b ≥ 2} ∪ {Ka,a : a ≥ 2} ∪ {C⁵ ✷ K2}.

By Theorem 3.1, χ 0 t (G) = 2 + ∆(G) for G = C 2 7 .

Consider G = K2n+1 − E(H), where H is a triangle-free r-regular spanning subgraph of K2n+1. It is a (2n − r)-regular graph on 2n + 1 vertices. For any two nonadjacent vertices u and v of G, NG(u) ∪ NG(v) = V (G) \ {u, v}. Otherwise, there exist w 6∈ NG(u) ∪ NG(v). But then {u, v, w} is an independent set in G, and therefore it is a triangle in H, a contradiction. So, by Lemma 3.1, χ 0 t (G) ≥ 2 + ∆(G).

In particular, consider K⁹ − E(C9). Let V (K9) = {v0, v1, . . . , v8} and C⁹ = v0v¹ . . . v8v0. The table below yields a twin edge 8-coloring of it. Consequently,

\[\chi_t'(K_9 - E(C_9)) \ge 2 + \Delta(K_9 - E(C_9)).\]

Finally, we propose the following problem:

Problem 1. If possible, find a twin edge (2+∆)-coloring of K2n+1−E(H), where H is a trianglefree 2-factor of K2n+1.

Acknowledgement

The authors are grateful to the referee for useful suggestions. This research was supported for the first author by UGC - Rajiv Gandhi National Fellowship.

References

• [1] 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.
• [2] E. Andrews, D. Johnston and P. Zhang, A twin edge coloring conjecture, Bulletin of the ICA 70 (2014), 28-44.
• [3] R. Balakrishnan and K. Ranganathan, A textbook of graph theory, Second Edition, Springer-Verlag, New York, 2012.