Introduction to total dominator edge chromatic number
Nima Ghanbari Saeid Alikhani
math.CO 05C15, 05C69








 Introduction to total dominator edge chromatic  number 
    
Nima Ghanbari Saeid Alikhani^[Corresponding author]

    December 30, 2023
=========================================================





Department of Mathematics, Yazd University, 89195-741, Yazd, Iran

n.ghanbari.math@gmail.com, alikhani@yazd.ac.ir






	We introduce the total dominator edge chromatic number of a graph G. A total dominator edge coloring (briefly TDE-coloring)  of  G is a proper edge coloring of G in which each edge of the graph is adjacent to every edge of some color class. The total dominator edge chromatic number (briefly TDEC-number)  χ'^t_d(G) of G is the minimum number of color classes in a TDE-coloring of G. We obtain some properties of χ'^t_d(G) and  compute this parameter for specific graphs. We   examine the effects on χ'^t_d(G) when G is modified by operations on vertex and  edge of G. Finally, we consider the k-subdivison of G and study TDEC-number of this kind of graphs.  


Keywords: total dominator edge chromatic number; vertex removal; k-subdivision


AMS Subj. Class.: 05C15, 05C69
 









§ INTRODUCTION









Let G=(V,E) be a simple  graph and k ∈ℕ. A mapping f : V (G)⟶{1, 2,...,k} is
called a k-proper  coloring of G, if f(u) ≠ f(v) whenever the vertices u and v are adjacent
in G. A color class of this coloring, is a set consisting of all those vertices
assigned the same color. If f is a proper coloring of G with the coloring classes V_1, V_2,..., V_k such
that every vertex in V_i has color i, then sometimes write simply f = (V_1,V_2,...,V_k).  The chromatic number χ(G) of G is
the minimum number of colors needed in a proper coloring of a graph.



The total dominator coloring, abbreviated TD-coloring studied in <cit.>. Let G be a graph with no
isolated vertex, the total dominator coloring  is a proper coloring of G in which each vertex of the graph is adjacent
to every vertex of some (other) color class. The total dominator chromatic number, abbreviated TDC-number, χ_d^t(G) of G is the minimum number of color classes in a TD-coloring of G.   Computation of the TDC-number is NP-complete (<cit.>).
The TDC-number of some graphs has computed in
<cit.>. Also Henning in <cit.> established the  lower and the upper bounds on the TDC-number
of a graph in terms of its total domination number γ_t(G). He has shown that,  every
graph G with no isolated vertex satisfies γ_t(G) ≤χ_d^t (G)≤γ_t(G) + χ(G).
The properties of TD-colorings in trees has studied in <cit.>. Trees T with γ_t(T) =χ_d^t(T) has characterized
in <cit.>. We have examined the effects on χ_d^t(G) when G is modified by operations on the vertex and the edge of G, and  the TDC-number of some operations on two graphs studied in <cit.>. 

Motivated by TDC-number of a graph, we consider the proper edge coloring of G and introduce the total dominator edge chromatic number (TDEC-number) of G, χ'^t_d(G), obtain some properties of χ'^t_d(G) and   compute this parameter for specific graphs, in the next section. In Section 3, we  examine the effects on χ'^t_d(G) when G is modified by operations on vertex and  edge of G. Finally in Section 4, we study the TDEC-number of k-subdivision of graphs. 




§ INTRODUCTION TO TOTAL DOMINATOR EDGE CHROMATIC NUMBER


In this section, we state the definition of total dominator edge chromatic number and obtain this parameter for some
specific graphs. 


	A total dominator edge coloring, briefly TDE-coloring, of a graph G is a proper edge coloring of G in which each edge of the graph is adjacent to every edge of some color class. The total dominator edge chromatic number (TDEC-number) χ'^t_d(G) of G is the minimum number of color classes in a TDE-coloring  of G. A χ'^t_d(G)-coloring of G is any total dominator edge coloring of G with χ'^t_d(G) colors.




  
For every graph G with maximum degree Δ(G), χ'^t_d (G) ≥Δ(G). This inequality is sharp. As an example, for the star graph K_1,n, χ'^t_d (K_1,n) =n.



The following theorem gives the total dominator edge chromatic number of a path. 





If P_n is  the path graph of order n≥ 9, then

    χ'^t_d(P_n)={[ 2k+2     ; 2k+3     ; 2k+4      ].

Also χ'^t_d(P_3)= χ'^t_d(P_4)=2, χ'^t_d(P_5)=3, χ'^t_d(P_6)=χ'^t_d(P_7)=4 and χ'^t_d(P_8)=5.
	


It is easy to show that χ'^t_d (P_3)=χ'^t_d (P_4)=2, χ'^t_d (P_5)=3, χ'^t_d (P_6)=χ'^t_d (P_7)=4 and χ'^t_d (P_8)=5. Suppose that  n≥ 9. 
First we show that in a TDE-coloring,  for each four consecutive edges we shall  use at least two  new colors. We consider two cases.  If an used  color assign  to edge  e_i+1, then we need to assign a new color to  the edge  e_i+2 and e_i+3 to have a TDE-coloring (see Figure <ref>). If a new color assign to the edge e_i+1, then we have to assign  a new color to e_i+2 or e_i to have a TDE-coloring. So we need at least two new colors in every four consecutive vertices. 

If  n=4k+1, for some k∈ℕ, then we give a TDE-coloring  for P_4k+1 which use only two new colors in every four consecutive edges. Define a function f_0 on E(P_4k) such that for any edge e_i,

  
    f_0(e_i)={[ 1  ; 2  ; 2   ].

where s is a natural number and for any e_i, i ≠ 4s and i≠ 4s+1, f_0(e_i) is a new number. Then this coloring is a TDE-coloring  of P_4k+1 
with the minimum number 2k+2 colors.





If  n=4k+2, for some k∈ℕ, then  we first color the 4k-4 edges using  f_0. Now for the rest of edges we define f_1 as  f_1(e_4k-3)=1, f_1(e_4k-2)=2k+1, f_1(e_4k-1)=2k+2, f_1(e_4k)=2k+3 and f_1(e_4k+1)=2. Since  for every five consecutive edges we have to use at least three  new colors, so this  edge coloring is  a TDE-coloring  of P_4k+1 with the minimum number 2k+3 colors.


If  n=4k+3, for some k∈ℕ, then using f_0  we color the 4k-4 edges. Now for the rest of edges define f_2 as f_2(e_4k-3)=1, f_2(e_4k-2)=2k+1, f_2(e_4k-1)=2k+2, f_2(e_4k)=2k+3, f_2(e_4k+1)=2k+4 and f_2(e_4k+2)=2. Since  for every six consecutive edges we have to use at least four  new colors, so this edge coloring  is a TDE-coloring  of P_4k+2 with the minimum number 2k+4 colors.


If  n=4k+4, for some k∈ℕ, then using f_0  we color  the 4k-4 edges and  for the rest of edges define f_3 as f_3(e_4k-3)=1, f_3(e_4k-2)=2k+1, f_3(e_4k-1)=2k+2, f_3(e_4k)=2, f_3(e_4k+1)=2k+3, f_3(e_4k+2)=2k+4 and f_3(e_4k+2)=2. This coloring is a TDE-coloring  of P_4k+2 with the minimum number 2k+4 colors. So we have the result. 






				
				

				
						

						
						



						

						



If C_n is the cycle graph of order n≥ 8, then

    χ'^t_d(C_n)={[ 2k+2,      ; 2k+3,      ; 2k+4,       ].
	
Also χ'^t_d (C_3)=3, χ'^t_d (C_4)=2, χ'^t_d (C_5)=χ'^t_d (C_6)=4 and χ'^t_d (C_7)=5.

						
						
It is similar to the Proof of Theorem <ref>. 


The following corollry is an immediate consequence of Theorems <ref> and <ref>.



For every n≥6, χ'^t_d(P_n)=χ'^t_d(C_n-1).


												
												
			The following theorem present  a lower bound for TDEC-number of graphs G which have the graph  P_6 as induced subgraph. 	
				

					If  G is a connected graph containing  P_6 as an induced subgraph, then χ'^t_d(G) ≥Δ (G)+2.  More generally, if the path graph P_n is an induced subgraph of G, then χ'^t_d(G) ≥Δ (G)+χ'^t_d(P_n-2).
				
				We assign  Δ (G) colors to the edges which are incident  to the vertex with maximum degree Δ(G). Now we consider P_6 as  induced subgraph of G. 
				As we have seen in the Proof of Theorem <ref>, we need at least two new colors for each four consecutive edges. So we have χ'^t_d(G) ≥Δ (G)+2. The proof of inequality  χ'^t_d(G) ≥Δ (G)+χ'^t_d(P_n-2) is similar. 
					The graph G in Figure <ref> and its coloring shows that the lower bound in Theorem <ref> is sharp.
				 												
				
				
				
				
				
					For every n∈ℕ, 	 2n-1≤χ'^t_d(K_2n)≤4n-2 and 2n≤χ'^t_d(K_2n+1)≤ 4n-1.
				
				
				
				The lower bounds follow from Remark <ref>. To obtain the upper bound, suppose that V(K_2n+1)={ u_1,…,u_2n+1}. By removing the vertex u_2n+1, we have the complete graph K_2n. We know that  χ'(K_2n)=2n-1. So we color the edges of  K_2n with 2n-1 colors. Now we add the vertex u_2n+1 and make K_2n+1 and assign  the new colors 2n,2n+1,…,4n-1 to new  edges. This is a TDE-coloring  for K_2n+1. Therefore χ'^t_d(K_2n+1)≤ 4n-1. By the similar method  we have χ'^t_d(K_2n)≤ 4n-2.
				


												
												
				
	
		
  (i)
 For every  n≠ m,  max { n,m}≤χ'^t_d(K_n,m)≤ m+n-1. 
 
  (ii) 
  For every n∈ℕ, n ≤χ'^t_d(K_n,n)≤ 2n. 
   
					
												
												
												
					
							
  (i)
			The lower bounds follow from Remark <ref>. To obtain the upper bound, suppose that V(K_n,m)=X∪ Y, where X={u_1,…,u_m} and 
			Y={u_m+1,… , u_m+n} and m≥ n. We have the following cases:
						
			Case 1) m=n+1. By removing the vertex u_1, we have the complete bipartite graph K_n,n. We know that  χ'(K_n,n)=n. So we color the edges of  K_n,n with n colors. Now we add the vertex u_1 and make K_n+1,n and assign the new colors n+1,n+2,…,2n to new  edges. This is a TDE-coloring  for K_n,m and we have χ'^t_d(K_n,m)≤ 2n = m+n-1.
			
		Case 2) m>n+1. By removing the vertex u_1, we have the complete bipartite graph K_m-1,n. We know that  χ'(K_m-1,n)=m-1. So we color the edges of  K_m-1,n with m-1 colors. Now we add the vertex u_1 and make K_m,n and assign  the new colors m,m+1,…,m+n-1 to new  edges. This is a TDE-coloring  for K_m,n and we have χ'^t_d(K_m,n)≤ m+n-1.
			
	
  (ii) 	In this part we have m=n.  By removing the vertex u_1, we have the complete bipartite graph K_n-1,n. We know that  χ'(K_n-1,n)=n. So we color the edges of  K_n-1,n with n colors. Now we add the vertex u_1 and make K_n,n and assign the new colors n+1,n+2,…,2n to new  edges. This is a TDE-coloring  for K_n,n and we have χ'^t_d(K_n,n)≤ 2n.	
															



	 The lower bounds in parts (i) and (ii) of Theorem <ref> are sharp. It suffices to consider K_3,2 and  K_2,2=C_4, respectively.  Note that   χ'^t_d(K_3,2)=3 and χ'^t_d(C_4)=2. Also the upper bound of part (i) is sharp. It suffices to consider the star graph K_1,6. Note that  χ'^t_d(K_1,6)=1+6-1=6.
	  							
												
												
												
		 Let n be any positive integer and F_n be the friendship graph with 2n+1 vertices and 3n edges, formed by the join of K_1  with nK_2. 
	By Remark <ref>,  and  TDE-coloring which  has shown in  Figure <ref>,   we have the following result for the wheel of order n, W_n and the friendship graph F_n.											
												



  (i) 
For any n≥ 3, 									
χ'^t_d (W_n)=n-1.


  (ii) 
For  n≥ 2,  χ'^t_d (F_n)=2n.
					

												
			
	
	
	
	
											
												
												




§ TDEC-NUMBER OF SOME OPERATIONS ON A GRAPH



												
The graph G-v is a graph that is made  by deleting the vertex v and all edges incident  to v from the graph G and the graph G-e is a graph that obtained from G by simply removing the  edge e. In this section we  present   bounds for TDEC-number  of G-v and G-e.	We begin with G-e. 											
												
 
If G is  a connected graph, and e∈ E(G) is not a bridge of G, then 

    χ'^t_d (G)-2≤χ'^t_d (G-e)≤χ'^t_d (G)+2 .


												
First we prove the right inequality.  Suppose that the edge e in a TDE-coloring of G has color i. If no edges of G use the color class i, then TDE-coloring of G is  a TDE-coloring of G-e, too. So χ'^t_d (G-e)≤χ'^t_d (G). If some edges of G use the color class i in TDE-coloring, then we have at most two edges with color i.
If  two edges of G have color i, then removing e does not effect on TDE-coloring  and any edge uses the old color class in TDE-coloring of G. So χ'^t_d (G-e)≤χ'^t_d (G). If  only one edge e has the  color i, then we change the color of some edges in G-e to have a TDE-coloring for G-e. In this case the edge e uses some color class, say k, and is adjacent to all color class k. We can not have more than two k in this case. Suppose that we have two k. Then we have only three cases for the graph G as we see in Figure <ref>. In Figure <ref>, the colors l and m are new colors and we only change the color of some edges in G-e and assign  the other edges their old color in G. This coloring is  a TDE-coloring  for G-e. In any case we do not use more than two new colors. Therefore we have χ'^t_d (G-e)≤χ'^t_d (G)+2. 
		
Now suppose that we have only one color k. Then we have only six cases for the graph G as we see in Figure <ref>. In Figure <ref>, the colors l and m are new colors and we only change the color of some edges in G-e and assig the other edges their old color in G. This  kind of coloring is  a TDE-coloring  for G-e. In any case we do not  use more than two new colors. 												
So we have χ'^t_d (G-e)≤χ'^t_d (G)+2.
												
Now we prove that χ'^t_d (G)-2≤χ'^t_d (G-e). To do this,  first we color G-e and then we add edge e. 
We assign new color i to e and new color j to one edge which is adjacent to e. So we have a TDE-coloring for G and χ'^t_d (G)≤χ'^t_d (G-e)+2. Therefore we have the result.
												
												
												
					



												
												

If G is a connected graph, and  v∈ V(G) is not a cut vertex of G, then 

    χ'^t_d (G)-deg(v)≤χ'^t_d (G-v) ≤χ'^t_d (G)+deg(v).


												
							
First we prove the left  inequality. We give a TDE-coloring to G-v,  add v and all the corresponding edges. Then we assign  deg(v) new colors to these 
edges and do not change the color of other edges. So this is a TDE-coloring of G and χ'^t_d (G)≤χ'^t_d (G-v) + deg(v). 
												
For the right   inequality, first we give a TDE-coloring  to G. In this case, since v is not a cut vertex, each edge which is adjacent to an edge with endpoint v has an other adjacent edge too. we change the color of this edge to a new color and do this deg(v) times and do not change the color of the other edges.  So this is a TDE-coloring of G-v and χ'^t_d (G-v) ≤χ'^t_d (G)+deg(v). Therefore we have the result. 	The following theorem is an immediate consequence of  Theorems <ref> and <ref>.											

There is a connected graph G, and a vertex  v∈ V(G) which is not a cut vertex of G such that 	 |χ'^t_d(G)  - χ'^t_d (G-v) | can be arbitrarily large.

								

											
In a graph G, contraction of an edge e with endpoints u,v is the replacement of u and v with a single vertex such that edges incident to the new vertex are the edges other than e that were incident with u or v. The resulting graph G/e has one less edge than G. We denote this graph by G/e. We end this section with the following theorem which
gives bounds for χ'^t_d(G/e). 
												
												
												

If  G is a connected graph and e=uv∈ E(G), then

    χ'^t_d(G)-2 ≤χ'^t_d(G/e) ≤χ'^t_d(G)+min{deg(u),deg(v)}-1 .


First we prove the left inequality. We give a TDE-coloring to G/e,  add e  and assign it a new color, say  i and change the color of one of its adjacent edges to new color j and do not change other colors. This is a TDE-coloring  of G. So we have χ'^t_d(G) ≤χ'^t_d(G/e)+2. 
For the right inequality, we give a TDE-coloring  to G. Suppose that min{deg(u),deg(v)}=deg(u). Now we make G/e and change the color of adjacent edges of  e with the endpoint u to new colors. So we have the result.			
	 The lower bound in Theorem <ref> is sharp. It suffices to consider the cycle graph C_5 as G. Note that  χ'^t_d(C_5)=4 and   χ'^t_d(C_4)=2. 
	  												
			


 

§ TDEC-NUMBER OF K-SUBDIVISION OF A GRAPH

 
 
 The  k-subdivision of G, denoted by G^1/k, is constructed by replacing each edge v_iv_j of G with a path of length k., say P_{v_i,v_j}. These k-paths are called superedges, any new vertex is an internal vertex, and is denoted by x^{v_i,v_j}_l if it belongs to the superedge P_{v_i,v_j}, i<j with  distance l from the vertex v_i, where l ∈{1, 2, … , k-1}.  Note that for k = 1, we have G^1/1= G^1 = G, and if the graph G has v vertices and e edges, then the graph G^1/k has v+(k-1)e vertices and ke edges. The total dominator chromatic number of a graph has studied in <cit.>.  In this section we study TDEC-number of k-subdivision of a graph. In particular, we obtain some  bounds for χ'^t_d(G^1/k) and prove that for any k≥ 2, χ'^t_d(G^1/k) ≤χ'^t_d(G^1/k+1).
 
 
  
  
 	If G is  a graph with m edges, then χ'^t_d(G^1/k) ≥ m, for k≥ 3. 
 
  For k=3, in any superedge P^{v,w} such as {v, x^{v,w}_1,  x^{v,w}_2,   w} ,The edge x^{v,w}_1 x^{v,w}_2 need to use a new color in at least one of its adjacent edges, and we cannot use this color in any other superedges. 
 So we have the result. 
  	If  G is a connected graph with m edges and k≥ 2, then 
  	
    χ'^t_d(P_k+1) ≤χ'^t_d(G^1/k)≤ m χ'^t_d(P_k+1).

  
  First we prove the the right inequality. Suppose that  e=uu_1 be an arbitrary edge of G. This edge is replaced with   the super edge P^{u,u_1}  in G^1/k, with vertices {u, x^{u,u_1}_1, … , x^{u,u_1}_k-1, u_1}. We color this superedge with  χ'^t_d(P_k+1) colors as a total dominator edge coloring of P_k+1. We do this for all superedges. 
  Thus we need  at most m χ'^t_d(P_k+1) new colors for a total dominator edge coloring of G^1/k.
  
  
  For the left inequality, if G is a path then the result is true. So we suppose that G is a connected graph which is not a path. Let  P^{v,w} be an arbitrary superedge of G^1/k with vertex set  {v, x^{v,w}_1, … , x^{v,w}_k-1, w}. Since G is not a path, so at least one of v and w is adjacent to some vertices of G^1/k except x^{v,w}_1 and x^{v,w}_k-1, respectively. Let c' be a total dominator edge coloring of  G^1/k. The two following cases can be occured: either the restriction of c' to edges of P^{v,w} is a total dominator edge coloring and so we have the result, or not. If the restriction of c' to edges of P^{v,w} is not a total dominator coloring then since c' is a total dominator edge coloring  of G^1/k we conclude that at least one of edges vx^{v,w}_1 and wx^{v,w}_k-1, as the edges of the induced subgraph P^{v,w}, are not adjacent to every edge of some color class. Without loss of generality we assume that the edge vx^{v,w}_1, as the edge of the induced subgraph P^{v,w},  is not  adjacent to every vertex of some color class. But c' is a total dominator coloring of G^1/k so the edge vx^{v,w}_1 is adjacent to every edge of some color class, as the edge of  G^1/k. Hence there is a new color for an adjacent edge of vx^{v,w}_1, except the edge x^{v,w}_1x^{v,w}_2. Thus if we use this new color for the edge  x^{v,w}_1x^{v,w}_2 and consider the restriction of c' for the remaining edges of superedge P^{v,w}, then P^{v,w} has a total dominator edge coloring. Therefore the total edge coloring c' has at least  χ'^t_d(P_k+1) colors.The lower bound of Theorem <ref> is sharp for P_2 and by the following Proposition we  show that the upper bound of this Theorem is sharp for G=K_1,n and k=3.



  
  	For every n≥ 3,  χ'^t_d(K_1,n^1/3) = 2n.
  
  
  Let e_1, … , e_n be the pendant edges of K_1,n^1/3. The adjacent edges to e_i is denoted by f_i, and the adjacent edge to f_i  is denoted by g_i for any 1≤ i ≤ n. Since  edge  f_i is the only edge adjacent to e_i, so the color of f_i should not be used for any other edges of graph, where 1≤ i ≤ n. Thus we color the edges f_1, … , f_n with colors 1, … , n, respectively, and do not use these colors any more. For every 1≤ i ≤ n, the edge f_i is adjacent to e_i and g_i, thus we need a new color for at least one of e_i and g_i. So we need at least 2n color to have a TDE-coloring of K_1,n^1/3. Now for every e_i and g_i we use the new color i+n. Obviously this is a TDE-coloring of K_1,n^1/3 and we have the result. Here we improve the  lower bound of Theorem <ref> for  k≥ 10 .
  
  	If  G is a connected graph with m edges and maximum degree Δ(G) and k≥ 10, then 
  	
    m(χ'^t_d(P_k-1)-2) + 2 ≤χ'^t_d(G^1/k).

  
  Let e=vw be an edge of G. We consider the superedge P^{v,w} with vertex set {v, x^{v,w}_1, … , x^{v,w}_k-1, w}. It is clear that P^{v,w}∖{v,w} is the path graph P_k-1. Since we use  repetitious colors for the edges x^{v,w}_1x^{v,w}_2 and x^{v,w}_k-2x^{v,w}_k-1 in the  TDE-coloring  of paths, so we need at least χ'^t_d(P_k-1)-2 colors for each superedges and we cannot use these colors anymore. Also we need two colors for edgesx^{v,w}_1x^{v,w}_2 and x^{v,w}_k-2x^{v,w}_k-1 and some other edges  hence  the result follows.
  	If  G is a connected graph with m edges and maximum degree Δ(G) and k≥ 10, then  
  	
    χ'^t_d(G^1/k)≥{[       m(k/2)+2  k≡ 0  (mod 4);     m(k-1/2)+2  k≡ 1  (mod 4);     m(k-2/2)+2  k≡ 2  (mod 4);     m(k-1/2)+2 k≡ 3  (mod 4). ].

  
  It follows by Theorems <ref> and <ref> .
  	If  G is a connected graph with m edges with maximum degree Δ(G) and k≥ 10  , then 
  	
    χ'^t_d(G^1/k)≤ m(χ'^t_d(P_k+1)-2) +Δ(G).

  
  As we see in the TDE-coloring  of paths, we can use the same color for the pendant edges. So we assign the colors 1,2,…,Δ(G) to all the edges incident  to the vertices belong to G and we color other edges of any superedges with χ'^t_d(P_k+1)-2 colors. This is a TDE-coloring  for G^1/k and hence  the result follows.
  	If  G is  a connected graph with m edges and k≥ 10, then  
  	
    χ'^t_d(G^1/k)≤{[     mk/2+Δ(G),  k≡ 0  (mod 4); m(k+1/2)+Δ(G),  k≡ 1  (mod 4); m(k+2/2)+Δ(G),  k≡ 2  (mod 4); m(k+1/2)+Δ(G), k≡ 3  (mod 4). ].

  
  It follows by Theorems <ref> and <ref> .
  	For any k≥ 4, χ'^t_d(G^1/k) ≤χ'^t_d(G^1/k+1).
  	
  
  
  First we give a TDE-coloring  to the edges of G^1/k+1. Let  P^{v,w} be an arbitrary superedge of G^1/k+1 with vertex set  {v, x^{v,w}_1, … , x^{v,w}_k, w}. We have the following cases:
  
  	
  Case 1)
  	There exists an edge u∈{ x^{v,w}_1x^{v,w}_2, … , x^{v,w}_k-1x^{v,w}_k} such that other edges of graph are not adjacent to all edges with color class of the edge u. Consider the graph in Figure <ref>. Suppose that the edge u has the color i and the edge n has the color α. The edge m is adjacent to all edges with color class j and j≠ i and the edge  n is adjacent to  all edges with color class k and k≠ i. Since k≥ 4, without loss of generality, suppose that m≠ vx^{v,w}_1. We have two subcases:
  	
  	
  	
  		
  Subcase i)
  		The color of the edge m is not α. In this case, we  make G/u   and do not change the color of any edges. So without adding a new color we have a TDE-coloring for this new graph.
  		
  Subcase ii)
  		The color of the edge  m is α. Since the edge u is adjacent to  color class α, so any other edges does not  have color α. In this case, by making G/m and keeping the color of any edges as before, we have a TDE-coloring  for this new graph. Because the edge  t is adjacent to color class which is not α, the color of the edge  t is not i (because if  the color of the edge  t is  i it has contradiction with our assumptions), the edge n is adjacent to  all edges with color class k and  the edge u is adjacent to all edges with color class α.
  	
  	
  	
  Case 2)
  	For every edge u∈{ x^{v,w}_1x^{v,w}_2, … , x^{v,w}_k-1x^{v,w}_k}, there exists an edge such that is adjacent to all edges with color of edge u. Consider  the graph in Figure <ref>. Suppose that the edge u has the color i and the  edge p has the color j and the edge p is adjacent to all edges with color i. We have two subcases:
  	
  		
  Subcase i)
  		The color of the edge q is not i. We make G/r   and do not change the color of any edges. So without adding a new color we have a TDEC for this new graph since there is no other edges with color i.
  		
  Subcase ii)
  		The color of the edge q is  i. In this case the edge r is adjacent to color class of edge s and the color of the edge s does not use for other edges. Now we make G/u   and do not  change the color of any edges. Now we consider the color of edge r. If the color of r is j, then we change it to i and since obviously the edge s was adjacent to a color class except j, so we have a TDE-coloring. If the color of the edge r is not j we do not  change the color of that and we have a TDE-coloring  again. 
  	
  
  Now we do the same algorithm for all superedges.  So we have χ'^t_d(G^1/k) ≤χ'^t_d(G^1/k+1).  
  
  
  
   
 For any graph G, 	χ'^t_d(G^1/3) ≤χ'^t_d(G^1/4).
  
  First we give a TDE-coloring  to the edges of G^1/4. Let  P^{i,j} be an arbitrary superedge of G^1/4 with edge set  {s,v,u, w} (see Figure <ref>) and suppose that  the edge v has the color α. We have the following cases:
 
 	
  Case 1)
 The edges 	u and s are adjacent with an edge with a color class which is not α. we have two subcases:
 	
 		
  Subcase i)
 		The color of edges u and s are different.  In this case, we make G/v and don't change the color of any edges. So we have a TDE-coloring for this new graph. Because  two edges u and s are adjacent with an edge with  color class which is not α.
 		
  Subcase ii)
 		The color of edges u and s are the same. Suppose that u and s have color β. In this case β does not use for any other edges. So w is adjacent with an edge with color class except β. Now we make G/u. So we have a TDE-coloring for this new graph.
 	
 	
 	
  Case 2)
 The edge 	u is adjacent to  all edges with color class α. we have two subcases:
 	
 		
  Subcase i)
 		The color of the edge w is not α. Suppose that the edge u has color γ.  If the edge v is adjacent with all edges with color γ, and if the color of s is  γ, we make G/u. But  if the color of edge s is not γ, then we make G/u and assign  the color γ to the edge w. So we have a TDE-coloring for this new graph. If the edge v is adjacent to  all edges with color except γ (edge s), then we make G/u. So we have  a TDE-coloring for this new graph.
 		
  Subcase ii)
 		The color of the edge  w is α. We have two new cases. First, the edge v is adjacent to an edge with color class γ. Any adjacent edge with w is not adjacent to  edge with color class α (except u). So we make G/u and assign  the color γ to w. This is a TDE-coloring for this new graph.  Second, v is not adjacent with color class γ. So the color of the edge s does not use any more. Also the edge s is not adjacent to edge  with color class α. So we make G/v. This is a TDE-coloring for this new graph.
 	
 	
 	
  Case 3)
 The edge	s is adjacent to  all edges with color class α. We have two subcases:
 	
 		
  Subcase i)
 		If v is the only edge which has color α,  then we make G/u when v is adjacent with color class of edge s and make G/s when v is adjacent with color class of edge u. So this is a TDE-coloring for this new graph.
 		
  Subcase ii)
 		If there exist some edges with color α, then the edge u is adjacent with color class except α. So we make G/v. This is a TDE-coloring for this new graph.
 	
 
 We apply this TDE-coloring for all superedges. So we obtain a TDE-coloring for  G^1/3. Therefore we have χ'^t_d(G^1/3) ≤χ'^t_d(G^1/4).  
  
  
  
   
 For any graph G, 	χ'^t_d(G^1/2) ≤χ'^t_d(G^1/3).
  
  First we give a TDE-coloring  to the edges of G^1/3. Let  P^{i,j} be an arbitrary superedge of G^1/3 with edge set  {s,v,u} (see Figure <ref>) and suppose that  the edge v has the color α. We have the following cases:
 
 	
  Case 1)
 The edges 	u and s are adjacent with an edge with a color class which is not α. we have two subcases:
 	
 		
  Subcase i)
 		The color of edges u and s are different.  In this case, we make G/v and don't change the color of any edges. So we have a TDE-coloring for this new graph. Because  two edges u and s are adjacent with an edge with  color class which is not α.
 		
  Subcase ii)
 		The color of edges u and s are the same. Suppose that u and s have color β. In this case any other edges is not adjacent with color class β, because i and j are not adjacent vertices (Because of the definition of G^1/3). Now we make G/u. So we have a TDE-coloring for this new graph.
 	
 	
 	
  Case 2)
The edge	s is adjacent to  all edges with color class α. We have two subcases:
 	
 		
  Subcase i)
 		If v is the only edge which has color α,  then we make G/u when v is adjacent with color class of edge s and make G/s when v is adjacent with color class of edge u. So this is a TDE-coloring for this new graph.
 		
  Subcase ii)
 		If there exist some edges with color α, then the edge u is adjacent with color class except α. If the edges u and s have the same color then we make G/u and if u and s have different colors, then we make G/v. This is a TDE-coloring for this new graph.
 	
 	
 	
  Case 3)
 The edges u and	s are adjacent to  all edges with color class α. So there is no other edge with color α. We have two subcases:
 	
 		
  Subcase i)
 		The edges u and s have the same color then we make G/u.
 		
  Subcase ii)
 		The edges u and s have different colors, then we make G/u when v is adjacent with color class of edge s and make G/s when v is adjacent with color class of edge u.
 	
 
 We apply this TDE-coloring for all superedges. So we obtain a TDE-coloring for  G^1/2. Therefore we have χ'^t_d(G^1/2) ≤χ'^t_d(G^1/3).  
  
  
 
  
  
  

   
  
  					
99
														 
		
		
		subdivision S. Alikhani, N. Ghanbari and S. Soltani, Total dominator chromatic number of k-subdivision of graphs, submitted. 		Available at 
														
nima2  N. Ghanbari, S. Alikhani, Total dominator chromatic number of some operations on a graph. Submitted. Available at 												
														
GCOM  M.A. Henning, Total dominator colorings and total domination in graphs,  Graphs Combin.  31   (2015) 953-–974.
														
														
Adel A.P. Kazemi,  Total dominator chromatic number of a graph, Trans. Combin. Vol. 4 No. 2 (2015),  57–68.
														
Adel2 A.P. Kazemi, Total dominator coloring in product graphs,  Utilatas Math., 94,  (2014) 329–345. 
														
																										
														
Vij1	A. Vijayalekshmi, Total dominator colorings in Graphs, Int. J. Adv. Research  Tech. 4,   (2012) 1–6.
														
Vij2 A. Vijayalekshmi, Total dominator colorings in Paths,  Int. J. Math. Combin., 2,  (2012) 89–95.
														

