Open Journal of Discrete Mathematics
Vol.07 No.04(2017), Article ID:80010,18 pages
10.4236/ojdm.2017.74018

Cyclically Interval Total Colorings of Cycles and Middle Graphs of Cycles

Yongqiang Zhao1, Shijun Su2

1School of Science, Shijiazhuang University, Shijiazhuang, China

2School of Science, Hebei University of Technology, Tianjin, China

Copyright © 2017 by authors and Scientific Research Publishing Inc.

This work is licensed under the Creative Commons Attribution International License (CC BY 4.0).

http://creativecommons.org/licenses/by/4.0/

Received: August 10, 2017; Accepted: October 28, 2017; Published: October 31, 2017

ABSTRACT

A total coloring of a graph G is a function α : E ( G ) V ( G ) such that no adjacent vertices, edges, and no incident vertices and edges obtain the same color. A k -interval is a set of k consecutive integers. A cyclically interval total t -coloring of a graph G is a total coloring α of G with colors 1,2, , t such that at least one vertex or edge of G is colored by i , i = 1 , 2 , , t , and for any x V ( G ) , the set S [ α , v ] = { α ( v ) } { α ( e ) | e is incident to v } is a ( d G ( x ) + 1 ) -interval, or { 1,2, , t } \ S [ α , x ] is a ( t d G ( x ) 1 ) -interval, where d G ( x ) is the degree of the vertex x in G. In this paper, we study the cyclically interval total colorings of cycles and middle graphs of cycles.

Keywords:

Total Coloring, Interval Total Coloring, Cyclically Interval Total Coloring, Cycle, Middle Graph

1. Introduction

All graphs considered in this paper are finite undirected simple graphs. For a graph G, let V ( G ) and E ( G ) denote the set of vertices and edges of G, respectively. For a vertex x V ( G ) , let d G ( x ) denote the degree of x in G. We denote Δ ( G ) the maximum degree of vertices of G.

For an arbitrary finite set A, we denote by | A | the number of elements of A. The set of positive integers is denoted by . An arbitrary nonempty subset of consecutive integers is called an interval. An interval with the minimum element p and the maximum element q is denoted by [ p , q ] . We denote [ a , b ] and [ a , b ] the sets of even and odd integers in [ a , b ] , respectively. An interval D is called a h -interval if | D | = h .

A total coloring of a graph G is a function α : E ( G ) V ( G ) such that no adjacent vertices, edges, and no incident vertices and edges obtain the same color. The concept of total coloring was introduced by Vizing [1] and independently by Behzad [2] . The total chromatic number χ ( G ) is the smallest number of colors needed for total coloring of G. For a total coloring α of a graph G and for any v V ( G ) , let S [ α , v ] = { α ( v ) } { α ( e ) | e is incident to v } .

An interval total t -coloring of a graph G is a total coloring of G with colors 1,2, , t such that at least one vertex or edge of G is colored by i , i = 1 , 2 , , t , and for any x V ( G ) , the set S [ α , x ] is a ( d G ( x ) + 1 ) -interval. A graph G is interval total colorable if it has an interval total t -coloring for some positive integer t.

For any t , let T t denote the set of graphs which have an interval total t -coloring, and let T = t 1 T t . For a graph G T , the least and the greatest values of t for which G T t are denoted by w τ ( G ) and W τ ( G ) , respectively. Clearly,

χ ( G ) w τ ( G ) W τ ( G ) | V ( G ) | + | E ( G ) |

for every graph G T . For a graph G T , let θ ¯ ( G ) = { t | G T t } .

The concept of interval total coloring was first introduced by Petrosyan [3] . Now we generalize the concept interval total coloring to the cyclically interval total coloring. A total t -coloring α of a graph G is called a cyclically interval total t -coloring of G, if for any x V ( G ) , S [ α , x ] is a ( d G ( x ) + 1 ) -interval, or [ 1, t ] \ S [ α , x ] is a ( t d G ( x ) 1 ) -interval. A graph G is cyclically interval total colorable if it has a cyclically interval total t -coloring for some positive integer t.

For any t , we denote by F t the set of graphs for which there exists a cyclically interval total t -coloring. Let F = t 1 F t . For any graph G F , the minimum and the maximum values of t for which G has a cyclically interval total t -coloring are denoted by w τ c ( G ) and W τ c ( G ) , respectively. For a graph G F , let Θ ¯ ( G ) = { t | G F t } .

It is clear that for any t , T t F t and T F . Note that for an arbitrary graph G, θ ¯ ( G ) Θ ¯ ( G ) . It is also clear that for any G T , the following inequality is true

χ ( G ) w τ c ( G ) w τ ( G ) W τ ( G ) W τ c ( G ) | V ( G ) | + | E ( G ) | .

A middle graph M ( G ) of a graph G is the graph whose vertex set is V ( G ) E ( G ) and in which two vertices are adjacent whenever either they are adjacent edges of G or one is a vertex of G and other is an edge incident with it.

In this paper, we study the cyclically interval total colorings of cycles and middle graphs of cycles. For a cycle C n , let V ( C n ) = { v 1 , v 2 , , v n } and E ( C n ) = { e 1 , e 2 , , e n } , where e 1 = v 1 v n and e i = v i 1 v i for i = 2 , 3 , , n . For example, the graphs in Figure 1 are C 4 and M ( C 4 ) , respectively. Note that in Section 3 we always use the kind of diagram like (c) in Figure 1 to denote M ( C n ) .

(a) (b) (c)

Figure 1. C 4 and M ( C 4 ) . (a) C 4 ; (b) M ( C 4 ) ; (c) Another diagram of M ( C 4 ) .

2. Cn

In this section we study the cyclically interval total colorings of C n ( n 3 ) , show that C n F , get the exact values of w τ c ( C n ) and W τ c ( C n ) , and determine the set Θ ¯ ( G ) . In [4] it was proved the following result.

Theorem 1. (H. P. Yap [4] ) For any integer n 3 ,

χ ( C n ) = { 3 , if n 0 ( mod 3 ) ; 4 , otherwise .

In [5] Petrosyan et al. studied the interval total colorings of cycles and provided the following result.

Theorem 2. (P. A. Petrosyan et al. [5] ) For any integer n 3 , we have

1) C n T ,

2) w τ ( C n ) = { 3, if n 0 ( m o d 3 ) ; 4, otherwise ,

3) W τ ( C n ) = n + 2 .

Now we consider the cyclically interval total colorings of C n ( n 3 ) . In order to define the total coloring of the graph C n easily, we denote V ( C n ) E ( C n ) by { a 1 , a 2 , , a 2 n } , where a 2 i 1 = v i and a 2 i = e i for any i [ 1, n ] .

Theorem 3. For any integer n 3 , we have

1) C n F ,

2) w τ c ( C n ) = { 3 , if n 0 ( mod 3 ) ; 4 , otherwise,

3) W τ c ( C n ) = 2 n .

Proof. Since T F , then for any G T we have χ ( G ) w τ c ( G ) w τ ( G ) . So by Theorems 1 and 2, (1) and (2) hold.

Let us prove (3). Now we show that W τ c ( C n ) 2 n for any n 3 . Define a total coloring α of the graph C n as follows: Let

α ( a i ) = i , i [ 1 , 2 n ] .

It is easy to check that α is a cyclically interval total 2n-coloring of C n . Thus, W τ c ( C n ) 2 n for any integer n 3 . On the other hand, it is easy to see that W τ c ( C n ) | V ( C n ) | + | E ( C n ) | = 2 n . So we have W τ c ( C n ) = 2 n .

Lemma 4. For any integer n 3 and t [ 4,2 n 2 ] , C n F t .

Proof. For any t [ 4, n 2 ] , we define a total t -coloring α of the graph C n as follows:

Case 1. n = 3 k , k .

Subcase 1.1. t = 3 s , s [ 2 , 2 k 1 ] .

Let

α ( a i ) = { i , if i [ 1 , t ] ] ; 1 , if i [ t + 1 , 2 n ] , i 1 ( mod 3 ) ; 2 , if i [ t + 1 , 2 n ] , i 2 ( mod 3 ) ; 3 , if i [ t + 1 , 2 n ] , i 0 ( mod 3 ) .

Subcase 1.2. t = 3 s + 1 , s [ 1 , 2 k 1 ] .

Let

α ( a i ) = { 4 , if i = 1 ; 3 , if i = 2 ; 2 , if i = 3 ; i , if i [ 4 , t ] ; 1 , if i [ t + 1 , 2 n ] , i 2 ( mod 3 ) ; 2 , if i [ t + 1 , 2 n ] , i 0 ( mod 3 ) ; 3 , if i [ t + 1 , 2 n ] , i 1 ( mod 3 ) .

Subcase 1.3. t = 3 s + 2 , s [ 1 , 2 k 2 ] .

Let

α ( a i ) = { t , if i = 1 ; i , if i [ 2 , t ] ; 1 , if i [ t + 1 , 2 n ] , i 0 ( mod 3 ) ; 2 , if i [ t + 1 , 2 n ] , i 1 ( mod 3 ) ; 3 , if i [ t + 1 , 2 n ] , i 2 ( mod 3 ) .

Case 2. n = 3 k + 1 , k .

Subcase 2.1. t = 3 s , s [ 2 , 2 k ] .

Let

α ( a i ) = { 4 , if i = 1 ; 3 , if i = 2 ; 2 , if i = 3 ; i , if i [ 4 , t ] ; 1 , if i [ t + 1 , 2 n ] , i 1 ( mod 3 ) ; 2 , if i [ t + 1 , 2 n ] , i 2 ( mod 3 ) ; 3 , if i [ t + 1 , 2 n ] , i 3 ( mod 3 ) .

Subcase 2.2. t = 3 s + 1 , s [ 1 , 2 k 1 ] .

Let

α ( a i ) = { 4 , if i = 1 ; i , if i [ 2 , t ] ; 1 , if i [ t + 1 , 2 n ] , i 2 ( mod 3 ) ; 2 , if i [ t + 1 , 2 n ] , i 0 ( mod 3 ) ; 3 , if i [ t + 1 , 2 n ] , i 1 ( mod 3 ) .

Subcase 2.3. t = 3 s + 2 , s [ 1 , 2 k 1 ] .

Let

α ( a i ) = { i , if i [ 1 , t ] ; 1 , if i [ t + 1 , 2 n ] , i 0 ( mod 3 ) ; 2 , if i [ t + 1 , 2 n ] , i 1 ( mod 3 ) ; 3 , if i [ t + 1 , 2 n ] , i 2 ( mod 3 ) .

Case 3. n = 3 k + 2 , k .

Subcase 3.1. t = 3 s , s [ 2 , 2 k ] .

Let

α ( a i ) = { t , if i = 1 ; i , if i [ 2 , t ] ; 1 , if i [ t + 1 , 2 n ] , i 1 ( mod 3 ) ; 2 , if i [ t + 1 , 2 n ] , i 2 ( mod 3 ) ; 3 , if i [ t + 1 , 2 n ] , i 3 ( mod 3 ) .

Subcase 3.2. t = 3 s + 1 , s [ 1 , 2 k ] .

Let

α ( a i ) = { i , if i [ 1 , t ] ; 1 , if i [ t + 1 , 2 n ] , i 2 ( mod 3 ) ; 2 , if i [ t + 1 , 2 n ] , i 0 ( mod 3 ) ; 3 , if i [ t + 1 , 2 n ] , i 1 ( mod 3 ) .

Subcase 3.3. t = 3 s + 2 , s [ 1 , 2 k ] .

Let

α ( a i ) = { 4 , if i = 1 ; 3 , if i = 2 ; 2 , if i = 3 ; i , if i [ 4 , t ] ; 1 , if i [ t + 1 , 2 n ] , i 0 ( mod 3 ) ; 2 , if i [ t + 1 , 2 n ] , i 1 ( mod 3 ) ; 3 , if i [ t + 1 , 2 n ] , i 2 ( mod 3 ) .

It is not difficult to check that, in each case, α is always a cyclically interval total t -coloring of C n . The proof is complete.

Lemma 5. C 3 F 5 .

Proof. We define a total 5-coloring α of the graph C 3 as follows: Let

α ( a i ) = { i , if i [ 1 , 5 ] ; 3 , if i = 6.

It is easy to see that α is a cyclically interval total coloring of C 3 .

Lemma 6. For any integer n 4 , C n F 2 n 1 .

Proof. By contradiction. Suppose that, for any integers n 4 , α is a cyclically interval total ( 2 n 1 ) -coloring of C n . Then there exist different i , j [ 1,2 n ] such that α ( a i ) = α ( a j ) and for different s , t [ 1,2 n ] \ { i , j } , α ( a i ) α ( a j ) . Without loss of generality, we may assume that α ( a i ) = α ( a j ) = 1 . Then for each k [ 2,2 n 1 ] , there is only one vertex or one edge of C n is colored by k .

Case 1. At least one of i and j is even.

Say that i is even. Without loss of generality, suppose that i = 2 n , i.e., α ( a 2 n ) = 1 . Then we have 3 j 2 n 3 . Note that a 2 n = v 1 v n . Since α is a cyclically interval total ( 2 n 1 ) -coloring of C n , then we have

{ α ( v 1 ) , α ( v 1 v 2 ) } = { 2 , 3 } , { 2 , 2 n 1 } or { 2 n 2 , 2 n 1 }

and

{ α ( v n ) , α ( v n 1 v n ) } = { 2 , 3 } , { 2 , 2 n 1 } or { 2 n 2 , 2 n 1 } .

Because

{ α ( v 1 ) , α ( v 1 v 2 ) } { α ( v n ) , α ( v n 1 v n ) } = ,

without loss of generality, we may assume that

{ α ( v 1 ) , α ( v 1 v 2 ) } = { 2 , 3 }

and

{ α ( v n ) , α ( v n 1 v n ) } = { 2 n 2 , 2 n 1 } .

Since that for each k [ 2,2 n 1 ] there is only one vertex or one edge of C n is colored by k . Then α ( a j 1 ) [ 4,2 n 3 ] or α ( a j + 1 ) [ 4,2 n 3 ] . On the other hand, since α is a cyclically interval total ( 2 n 1 ) -coloring of C n , then α ( a j 1 ) , α ( a j + 1 ) { 2 , 3 , 2 n 2 , 2 n 1 } weather j is odd or even. A contradiction.

Case 2. i and j are all odd.

Without loss of generality, suppose that i = 1 .Then we have 3 j n 1 . Note that a i and a j are all vertices of C n . Since α is a cyclically interval total ( 2 n 1 ) -coloring of C n , then we have

{ α ( a 2 ) , α ( a 2 n ) } = { 2,3 } , { 2,2 n 1 } or { 2 n 2,2 n 1 }

and

{ α ( a j 1 ) , α ( a j + 1 ) } = { 2,3 } , { 2,2 n 1 } or { 2 n 2,2 n 1 } .

Because

{ α ( a 2 ) , α ( a 2 n ) } { α ( a j 1 ) , α ( a j + 1 ) } = ,

without loss of generality, we may assume that

{ α ( a 2 ) , α ( a 2 n ) } = { 2 , 3 }

and

{ α ( a j 1 ) , α ( a j + 1 ) } = { 2 n 2 , 2 n 1 } ,

say α ( a 2 ) = 2 . Then α ( a 2 n ) = 3 . Now we consider the color of a 3 . By the definition of α , α ( a 3 ) { 1,3,4,2 n 1 } . But α ( a 3 ) can not be 1, 3 or 2 n 1 obviously. So we have α ( a 3 ) = 4 , and then α ( a 4 ) = 3 . This is a contradiction to that just one vertex or one edge of C n is colored by i , where i [ 2,2 n 1 ] . Since we already have α ( a 2 n ) = 3 before.

Combining Theorem 3, Corollaries 4 - 6, the following result holds.

Theorem 7. For any integer n 3 ,

Θ ¯ ( C n ) = { [ 3 , 2 n ] , if n = 3 ; [ 3 , 2 n ] \ { 2 n 1 } , if n 4 and n 0 ( mod 3 ) ; [ 4 , 2 n ] \ { 2 n 1 } , otherwise .

3. M (Cn)

In this section we study the cyclically interval total colorings of M ( C n ) ( n 3 ) , prove M ( C n ) F , get the exact values of w τ c ( M ( C n ) ) , provide a lower bound of W τ c ( M ( C n ) ) , and show that for any k between w τ c ( M ( C n ) ) and the lower bound of W τ c ( M ( C n ) ) , M ( C n ) F k .

Theorem 8. For any integer n 3 , w τ c ( M ( C n ) ) = 5 .

Proof. Suppose that integer n 3 . Now we define a total 5-coloring α of the graph M ( C n ) as follows:

Case 1. n is even.

Let

α ( v i ) = 3 , i [ 1 , n ] ,

α ( e i ) = { 1, i [ 1, n ] ; 4, i [ 1, n ] ,

α ( e i v i ) = 2, i [ 1, n ] ,

α ( v i e i + 1 ) = { 1, i [ 1, n ] ; 4, i [ 1, n ] ,

and

α ( e i e i + 1 ) = { 3, i [ 1, n ] ; 5, i [ 1, n ] ,

where e n + 1 = e 1 . See Figure 2.

By the definition of α we have

S [ α , v i ] = [ 1,3 ] , i [ 1, n ] ,

S [ α , v i ] = [ 2,4 ] , i [ 1, n ] ,

Figure 2. A total 5-coloring of M ( C 4 ) .

and

S [ α , e i ] = [ 1,5 ] , i [ 1, n ] .

Case 2. n is odd.

Let

α ( v i ) = { 3, i [ 1, n 1 ] ; 4, i = n ,

α ( e i ) = { 1, i [ 1, n 1 ] ; 4, i [ 1, n 1 ] ; 2, i = n ,

α ( e i v i ) = { 2, i [ 1, n 1 ] ; 3, i = n ,

α ( v i e i + 1 ) = { 1, i [ 1, n 2 ] { n 1 } ; 4, i [ 1, n 2 ] ,

α ( v n e 1 ) = 5 ,

α ( e i e i + 1 ) = { 3, i [ 1, n 1 ] ; 5, i [ 1, n 1 ] ,

and

α ( e 1 e n ) = 4.

See Figure 3.

By the definition of α we have

S [ α , v i ] = [ 1,3 ] , i [ 1, n 2 ] { n 1 } ,

S [ α , v i ] = [ 2,4 ] , i [ 1, n 2 ] ,

S [ α , v n ] = [ 3,5 ] ,

and

S [ α , e i ] = [ 1,5 ] , i [ 1, n ] .

Combining Cases 1 and 2, we know that, for any integer n 3 , α is a cyclically interval total 5-coloring of M ( C n ) . Therefore

w τ c ( M ( C n ) ) 5.

Figure 3. A total 5-coloring of M ( C 5 ) .

On the other hand,

w τ c ( M ( C n ) ) Δ ( M ( C n ) ) + 1 = 5.

So we have

w τ c ( M ( C n ) ) = 5.

Theorem 9. For any integer n 3 , W τ c ( M ( C n ) ) 4 n .

Proof. Now we define a total 4n-coloring α of the graph M ( C n ) as follows: Let

α ( v i ) = 4 i 1 ,

α ( e i ) = 4 i 3 ,

α ( e i v i ) = 4 i 2 ,

α ( v i e i + 1 ) = 4 i ,

and

α ( e i e i + 1 ) = 4 i 1 ,

where i [ 1, n ] and e n + 1 = e 1 . See Figure 4.

By the definition of α we have

S [ α , v i ] = [ 4 i 2,4 i ] , i [ 1, n ] ,

S [ α , e i ] = [ 4 i 5,4 i 1 ] , i [ 2, n ] ,

and

S [ α , e 1 ] = [ 1,3 ] [ 4 n 1,4 n ] .

This shows that α is a cyclically interval total 4n-coloring of M ( C n ) . So we have

W τ c ( M ( C n ) ) 4 n .

Theorem 10. For any integer n 3 and any k [ 5,4 n ] , M ( C n ) F k .

Proof. Suppose n 3 and for any k [ 5,4 n ] . We define a total k -coloring α of M ( C n ) as follows. First we use the colors 1,2, , k to color the vertices and edges of M ( C n ) beginning from e 1 by the way used in the proof of Theorem 9. Now we color the other vertices and edges of M ( C n ) with the colors 1,2, , k .

Figure 4. A total 16-coloring of M ( C 4 ) .

Case 1. k 0 ( m o d 4 ) .

Let t = k 4 . Then we have α ( v t e t + 1 ) = k , where 1 t n .

Subcase 1.1. n t is even.

Let

α ( v t + i ) = 3, i [ 1, n t ] ,

α ( e t + i ) = { 1, i [ 1, n t ] ; 4, i [ 1, n t ] ,

α ( e t + i v t + i ) = 2, i [ 1, n t ] ,

α ( v t + i e t + i + 1 ) = { 1, i [ 1, n t ] ; 4, i [ 1, n t ] ,

and

α ( e t + i e t + i + 1 ) = { 3, i [ 1, n t ] ; 5, i [ 1, n t ] ,

where e n + 1 = e 1 . See Figure 5.

By the definition of α we have

S [ α , v i ] = [ 4 i 2,4 i ] , i [ 1, t ] ,

S [ α , v t + i ] = [ 1,3 ] , i [ 1, n t ] ,

S [ α , v t + i ] = [ 2,4 ] , i [ 1, n t ] ,

S [ α , e 1 ] = [ 1,5 ] ,

S [ α , e i ] = [ 4 i 5,4 i 1 ] , i [ 2, t ] ,

S [ α , e t + 1 ] = [ 1,3 ] [ k 1, k ] ,

and

S [ α , e t + i ] = [ 1,5 ] , i [ 2, n t ] .

Subcase 1.2. n t is odd.

Let

α ( v t + i ) = 3, i [ 1, n t 1 ] ,

α ( v n ) = 2 ,

α ( e t + i ) = { 1, i [ 1, n t ] ; 4, i [ 1, n t ] ,

Figure 5. A total 8-coloring of M ( C 6 ) .

α ( e t + i v t + i ) = 2 , i [ 1 , n t 1 ] ,

α ( e n v n ) = 3 ,

α ( v t + i e t + i + 1 ) = { 1, i [ 1, n t ] ; 4, i [ 1, n t ] ,

α ( e t + i e t + i + 1 ) = { 3, i [ 1, n t 1 ] ; 5, i [ 1, n t 1 ] ,

α ( e n e 1 ) = 2 ,

and recolor e 1 and e 1 v 1 as α ( e 1 ) = 4 and α ( e 1 v 1 ) = 5 , where e n + 1 = e 1 . See Figure 6.

By the definition of α we have

S [ α , v 1 ] = [ 3 , 5 ] ,

S [ α , v i ] = [ 4 i 2,4 i ] , i [ 2, t ] ,

S [ α , v t + i ] = [ 1,3 ] , i [ 1, n t ] ,

S [ α , v t + i ] = [ 2,4 ] , i [ 1, n t ] ,

S [ α , e 1 ] = [ 1,5 ] ,

S [ α , e i ] = [ 4 i 5,4 i 1 ] , i [ 2, t ] ,

S [ α , e t + 1 ] = [ 1,3 ] [ k 1, k ] ,

and

S [ α , e t + i ] = [ 1,5 ] , i [ 2, n t ] .

Case 2. k 1 ( m o d 4 ) .

Let t = k + 3 4 . Then we have α ( e t ) = k , where 2 t n .

Subcase 2.1. n t is even.

Let

α ( v t ) = k ,

α ( v t + i ) = 3 , i [ 1 , n t ] ,

α ( e t + i ) = { 1, i [ 1, n t ] ; 4, i [ 1, n t ] ,

Figure 6. A total 8-coloring of M ( C 5 ) .

α ( e t v t ) = 1 ,

α ( e t + i v t + i ) = 2 , i [ 1 , n t ] ,

α ( v t e t + 1 ) = k 1 ,

α ( v t + i e t + i + 1 ) = { 1, i [ 1, n t ] ; 4, i [ 1, n t ] ,

α ( e t e t + 1 ) = k ,

α ( e t + i e t + i + 1 ) = { 3, i [ 1, n t ] ; 5, i [ 1, n t ] ,

and recolor e t as α ( e t ) = 2 , where e n + 1 = e 1 . See Figure 7.

By the definition of α we have

S [ α , v i ] = [ 4 i 2,4 i ] , i [ 1, t 1 ] ,

S [ α , v t ] = { 1, k 1, k } ,

S [ α , v t + i ] = [ 1,3 ] , i [ 1, n t ] ,

S [ α , v t + i ] = [ 2,4 ] , i [ 1, n t ] ,

S [ α , e 1 ] = [ 1 , 5 ] ,

S [ α , e i ] = [ 4 i 5,4 i 1 ] , i [ 2, t 1 ] ,

S [ α , e t ] = [ 1,2 ] [ k 2, k ] ,

S [ α , e t + 1 ] = [ 1,3 ] [ k 1, k ] ,

and

S [ α , e t + i ] = [ 1,5 ] , i [ 2, n t ] .

Subcase 2.2. n t is odd.

Let

α ( v t ) = 1 ,

α ( v t + i ) = 3 , i [ 1 , n t ] ,

α ( e t + i ) = { 4, i [ 1, n t ] ; 1, i [ 1, n t ] ,

α ( e t + i v t + i ) = 2, i [ 0, n t ] ,

Figure 7. A total 9-coloring of M ( C 5 ) .

α ( v t e t + 1 ) = 3 ,

α ( v t + i e t + i + 1 ) = { 4, i [ 1, n t ] ; 1, i [ 1, n t ] ,

α ( e t e t + 1 ) = 1 ,

α ( e t + i e t + i + 1 ) = { 5, i [ 1, n t ] ; 3, i [ 1, n t ] ,

where e n + 1 = e 1 . See Figure 8.

By the definition of α we have

S [ α , v i ] = [ 4 i 2,4 i ] , i [ 1, t 1 ] ,

S [ α , v t + i ] = [ 2,4 ] , i [ 0, n t ] ,

S [ α , v t + i ] = [ 1,3 ] , i [ 0, n t ] ,

S [ α , e 1 ] = [ 1 , 5 ] ,

S [ α , e i ] = [ 4 i 5,4 i 1 ] , i [ 2, t 1 ] ,

S [ α , e t ] = [ 1,2 ] [ k 2, k ] ,

and

S [ α , e t + i ] = [ 1,5 ] , i [ 1, n t ] .

Case 3. k 2 ( m o d 4 ) .

Let t = k + 2 4 . Then we have α ( e t v t ) = k , where 2 t n .

Subcase 3.1. n t is even.

Let

α ( v t ) = k ,

α ( v t + i ) = 3 , i [ 1 , n t ] ,

α ( e t + i ) = { 1, i [ 1, n t ] ; 4, i [ 1, n t ] ,

α ( e t + i v t + i ) = 2, i [ 1, n t ] ,

α ( v t e t + 1 ) = k 1 ,

α ( v t + i e t + i + 1 ) = { 1, i [ 1, n t ] ; 4, i [ 1, n t ] ,

Figure 8. A total 9-coloring of M ( C 6 ) .

α ( e t e t + 1 ) = k ,

α ( e t + i e t + i + 1 ) = { 3, i [ 1, n t ] ; 5, i [ 1, n t ] ,

and recolor e t v t as α ( e t v t ) = 1 , where e n + 1 = e 1 . See Figure 9.

By the definition of α we have

S [ α , v i ] = [ 4 i 2,4 i ] , i [ 1, t 1 ] ,

S [ α , v t ] = { 1, k 1, k } ,

S [ α , v t + i ] = [ 1,3 ] , i [ 1, n t ] ,

S [ α , v t + i ] = [ 2,4 ] , i [ 1, n t ] ,

S [ α , e 1 ] = [ 1 , 5 ] ,

S [ α , e i ] = [ 4 i 5,4 i 1 ] , i [ 2, t 1 ] ,

S [ α , e t ] = { 1 } [ k 3, k ] ,

S [ α , e t + 1 ] = [ 1,3 ] [ k 1, k ] ,

and

S [ α , e t + i ] = [ 1,5 ] , i [ 2, n t ] .

Subcase 3.2. n t is odd.

Let

α ( v t ) = 1 ,

α ( v t + 1 ) = 2 ,

α ( v t + i ) = 3, i [ 2, n t ] ,

α ( e t + i ) = { 4, i [ 1, n t ] ; 1, i [ 1, n t ] ,

α ( e t + 1 v t + 1 ) = 3 ,

α ( e t + i v t + i ) = 2 , i [ 2 , n t ]

α ( v t e t + 1 ) = 2 ,

α ( v t + i e t + i + 1 ) = { 4, i [ 1, n t ] ; 1, i [ 1, n t ] ,

Figure 9. A total 10-coloring of M ( C 5 ) .

α ( e t e t + 1 ) = 1 ,

α ( e t + i e t + i + 1 ) = { 5, i [ 1, n t ] ; 3, i [ 1, n t ] ,

where e n + 1 = e 1 . See Figure 10.

By the definition of α we have

S [ α , v i ] = [ 4 i 2,4 i ] , i [ 1, t 1 ] ,

S [ α , v t ] = { 1,2, k } ,

S [ α , v t + i ] = [ 2,4 ] , i [ 1, n t ] ,

S [ α , v t + i ] = [ 1,3 ] , i [ 1, n t ] ,

S [ α , e 1 ] = [ 1 , 5 ] ,

S [ α , e i ] = [ 4 i 5,4 i 1 ] , i [ 2, t 1 ] ,

S [ α , e t ] = { 1 } [ k 3, k ] ,

and

S [ α , e t + i ] = [ 1,5 ] , i [ 1, n t ] .

Case 4. k 3 ( m o d 4 ) .

Let t = k + 1 4 . Then we have α ( v t ) = k , where 2 t n .

Subcase 4.1. n t is even.

Let

α ( v t + i ) = 3 , i [ 1 , n t ] ,

α ( e t + i ) = { 4, i [ 1, n t ] ; 1, i [ 1, n t ] ,

α ( e t + i v t + i ) = 2, i [ 1, n t ] ,

α ( v t + i e t + i + 1 ) = { 4, i [ 0, n t ] ; 1, i [ 0, n t ] ,

α ( e t + i e t + i + 1 ) = { 3, i [ 1, n t ] ; 5, i [ 1, n t ] ,

and recolor e 1 as α ( e 1 ) = 4 , where e n + 1 = e 1 . See Figure 11.

Figure 10. A total 10-coloring of M ( C 6 ) .

Figure 11. A total 7-coloring of M ( C 6 ) .

By the definition of α we have

S [ α , v i ] = [ 4 i 2,4 i ] , i [ 1, t 1 ] ,

S [ α , v t ] = { 1 , k 1 , k } ,

S [ α , v t + i ] = [ 2,4 ] , i [ 1, n t ] ,

S [ α , v t + i ] = [ 1,3 ] , i [ 1, n t ] ,

S [ α , e 1 ] = [ 1 , 5 ] ,

S [ α , e i ] = [ 4 i 5,4 i 1 ] , i [ 2, t ] ,

S [ α , e t + 1 ] = [ 1,4 ] { k } ,

S [ α , e t + i ] = [ 1,5 ] , i [ 2, n t ] .

Subcase 4.2. n t is odd.

Let

α ( v t + 1 ) = 4 ,

α ( v t + i ) = 3 , i [ 2 , n t ] ,

α ( e t + 1 ) = 2 ,

α ( e t + i ) = { 4, i [ 2, n t ] ; 1, i [ 2, n t ] ,

α ( e t + 1 v t + 1 ) = 3 ,

α ( e t + i v t + i ) = 2 , i [ 2 , n t ] ,

α ( v t e t + 1 ) = 1 ,

α ( v t + 1 e t + 2 ) = 5 ,

α ( v t + i e t + i + 1 ) = { 4, i [ 2, n t ] ; 1, i [ 2, n t ] ,

α ( e t + 1 e t + 2 ) = 4 ,

α ( e t + i e t + i + 1 ) = { 5, i [ 2, n t ] ; 3, i [ 2, n t ] ,

where e n + 1 = e 1 . See Figure 12.

Figure 12. A total 7-coloring of M ( C 5 ) .

By the definition of α we have

S [ α , v i ] = [ 4 i 2,4 i ] , i [ 1, t 1 ] ,

S [ α , v t ] = { 1, k 1, k } ,

S [ α , v t + 1 ] = [ 3,5 ] ,

S [ α , v t + i ] = [ 2,4 ] , i [ 2, n t ] ,

S [ α , v t + i ] = [ 1,3 ] , i [ 2, n t ] ,

S [ α , e 1 ] = [ 1,5 ] ,

S [ α , e i ] = [ 4 i 5,4 i 1 ] , i [ 2, t ] ,

S [ α , e t + 1 ] = [ 1,4 ] { k } ,

and

S [ α , e t + i ] = [ 1,5 ] , i [ 2, n t ] .

Combining Cases 1 - 4, the result follows.

4. Concluding Remarks

In this paper, we study the cyclically interval total colorings of cycles and middle graphs of cycles.

For any integer n 3 , we show C n F , prove that w τ c ( C n ) = 3 (if n 0 ( m o d 3 ) ) or 4 (otherwise) and W τ c ( C n ) = 2 n , and determine the set Θ ¯ ( G ) as

Θ ¯ ( C n ) = { [ 3,2 n ] , if n = 3 ; [ 3,2 n ] \ { 2 n 1 } , if n 4 and n 0 ( m o d 3 ) ; [ 4,2 n ] \ { 2 n 1 } , otherwise .

For any integer n 3 , we have M ( C n ) F , prove that w τ c ( M ( C n ) ) = 5 and W τ c ( M ( C n ) ) 4 n and, for any k between 5 and 4n, M ( C n ) F k . We conjecture that W τ c ( M ( C n ) ) = 4 n .

It would be interesting in future to study the cyclically interval total colorings of graphs related to cycles.

Acknowledgements

We thank the editor and the referee for their valuable comments. The work was supported in part by the Natural Science Foundation of Hebei Province of China under Grant A2015106045, and in part by the Institute of Applied Mathematics of Shijiazhuang University.

Cite this paper

Zhao, Y.Q. and Su, S.J. (2017) Cyclically Interval Total Colorings of Cycles and Middle Graphs of Cycles. Open Journal of Discrete Mathematics, 7, 200-217. https://doi.org/10.4236/ojdm.2017.74018

References

  1. 1. Vizing, V.G. (1965) Chromatic Index of Multigraphs. Doctoral Thesis, Novosibirsk. (in Russian)

  2. 2. Behzad, M. (1965) Graphs and Their Chromatic Numbers. Ph.D. Thesis, Michigan State University, East Lansing, MI.

  3. 3. Petrosyan, P.A. (2007) Interval Total Colorings of Complete Bipartite Graphs. Proceedings of the CSIT Conference, Yerevan, 84-85.

  4. 4. Yap, H.P. (1996) Total Colorings of Graphs, Lecture Notes in Mathematics 1623. Springer-Verlag , Berlin.

  5. 5. Petrosyan, P.A., Torosyan, A.Yu. and Khachatryan, N.A. (2010) Interval Total Colorings of Graphs . arXiv:1010.2989v1.