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
such that no adjacent vertices, edges, and no incident vertices and edges obtain the same color. A
-interval is a set of
consecutive integers. A cyclically interval total
-coloring of a graph G is a total coloring
of G with colors
such that at least one vertex or edge of G is colored by
, and for any
, the set
is a
-interval, or
is a
-interval, where
is the degree of the vertex
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
and
denote the set of vertices and edges of G, respectively. For a vertex
, let
denote the degree of
in G. We denote
the maximum degree of vertices of G.
For an arbitrary finite set A, we denote by
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
. We denote
and
the sets of even and odd integers in
, respectively. An interval D is called a
-interval if
.
A total coloring of a graph G is a function
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
is the smallest number of colors needed for total coloring of G. For a total coloring
of a graph G and for any
, let
.
An interval total
-coloring of a graph G is a total coloring of G with colors
such that at least one vertex or edge of G is colored by
, and for any
, the set
is a
-interval. A graph G is interval total colorable if it has an interval total
-coloring for some positive integer t.
For any
, let
denote the set of graphs which have an interval total
-coloring, and let
. For a graph
, the least and the greatest values of
for which
are denoted by
and
, respectively. Clearly,
for every graph
. For a graph
, let
.
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
-coloring
of a graph G is called a cyclically interval total
-coloring of G, if for any
,
is a
-interval, or
is a
-interval. A graph G is cyclically interval total colorable if it has a cyclically interval total
-coloring for some positive integer t.
For any
, we denote by
the set of graphs for which there exists a cyclically interval total
-coloring. Let
. For any graph
, the minimum and the maximum values of
for which G has a cyclically interval total
-coloring are denoted by
and
, respectively. For a graph
, let
.
It is clear that for any
,
and
. Note that for an arbitrary graph G,
. It is also clear that for any
, the following inequality is true
A middle graph
of a graph G is the graph whose vertex set is
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
, let
and
, where
and
for
. For example, the graphs in Figure 1 are
and
, respectively. Note that in Section 3 we always use the kind of diagram like (c) in Figure 1 to denote
.
(a)
(b)
(c)
Figure 1.
and
. (a)
; (b)
; (c) Another diagram of
.
2. Cn
In this section we study the cyclically interval total colorings of
, show that
, get the exact values of
and
, and determine the set
. In [4] it was proved the following result.
Theorem 1. (H. P. Yap [4] ) For any integer
,
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
, we have
1)
,
2)
3)
.
Now we consider the cyclically interval total colorings of
. In order to define the total coloring of the graph
easily, we denote
by
, where
and
for any
.
Theorem 3. For any integer
, we have
1)
,
2)
3)
.
Proof. Since
, then for any
we have
. So by Theorems 1 and 2, (1) and (2) hold.
Let us prove (3). Now we show that
for any
. Define a total coloring
of the graph
as follows: Let
It is easy to check that
is a cyclically interval total 2n-coloring of
. Thus,
for any integer
. On the other hand, it is easy to see that
. So we have
.
Lemma 4. For any integer
and
,
.
Proof. For any
, we define a total
-coloring
of the graph
as follows:
Case 1.
.
Subcase 1.1.
.
Let
Subcase 1.2.
.
Let
Subcase 1.3.
.
Let
Case 2.
.
Subcase 2.1.
.
Let
Subcase 2.2.
.
Let
Subcase 2.3.
.
Let
Case 3.
.
Subcase 3.1.
.
Let
Subcase 3.2.
.
Let
Subcase 3.3.
.
Let
It is not difficult to check that, in each case,
is always a cyclically interval total
-coloring of
. The proof is complete.
Lemma 5.
.
Proof. We define a total 5-coloring
of the graph
as follows: Let
It is easy to see that
is a cyclically interval total coloring of
.
Lemma 6. For any integer
,
.
Proof. By contradiction. Suppose that, for any integers
,
is a cyclically interval total
-coloring of
. Then there exist different
such that
and for different
,
. Without loss of generality, we may assume that
. Then for each
, there is only one vertex or one edge of
is colored by
.
Case 1. At least one of
and
is even.
Say that
is even. Without loss of generality, suppose that
, i.e.,
. Then we have
. Note that
. Since
is a cyclically interval total
-coloring of
, then we have
and
Because
without loss of generality, we may assume that
and
Since that for each
there is only one vertex or one edge of
is colored by
. Then
or
. On the other hand, since
is a cyclically interval total
-coloring of
, then
weather
is odd or even. A contradiction.
Case 2.
and
are all odd.
Without loss of generality, suppose that
.Then we have
. Note that
and
are all vertices of
. Since
is a cyclically interval total
-coloring of
, then we have
and
Because
without loss of generality, we may assume that
and
say
. Then
. Now we consider the color of
. By the definition of
,
. But
can not be 1, 3 or
obviously. So we have
, and then
. This is a contradiction to that just one vertex or one edge of
is colored by
, where
. Since we already have
before.
Combining Theorem 3, Corollaries 4 - 6, the following result holds.
Theorem 7. For any integer
,
3.
In this section we study the cyclically interval total colorings of
, prove
, get the exact values of
, provide a lower bound of
, and show that for any
between
and the lower bound of
,
.
Theorem 8. For any integer
,
.
Proof. Suppose that integer
. Now we define a total 5-coloring
of the graph
as follows:
Case 1.
is even.
Let
and
where
. See Figure 2.
By the definition of
we have
![]()
Figure 2. A total 5-coloring of
.
and
Case 2.
is odd.
Let
and
See Figure 3.
By the definition of
we have
and
Combining Cases 1 and 2, we know that, for any integer
,
is a cyclically interval total 5-coloring of
. Therefore
![]()
Figure 3. A total 5-coloring of
.
On the other hand,
So we have
Theorem 9. For any integer
,
.
Proof. Now we define a total 4n-coloring
of the graph
as follows: Let
and
where
and
. See Figure 4.
By the definition of
we have
and
This shows that
is a cyclically interval total 4n-coloring of
. So we have
Theorem 10. For any integer
and any
,
.
Proof. Suppose
and for any
. We define a total
-coloring
of
as follows. First we use the colors
to color the vertices and edges of
beginning from
by the way used in the proof of Theorem 9. Now we color the other vertices and edges of
with the colors
.
![]()
Figure 4. A total 16-coloring of
.
Case 1.
.
Let
. Then we have
, where
.
Subcase 1.1.
is even.
Let
and
where
. See Figure 5.
By the definition of
we have
and
Subcase 1.2.
is odd.
Let
![]()
Figure 5. A total 8-coloring of
.
and recolor
and
as
and
, where
. See Figure 6.
By the definition of
we have
and
Case 2.
.
Let
. Then we have
, where
.
Subcase 2.1.
is even.
Let
![]()
Figure 6. A total 8-coloring of
.
and recolor
as
, where
. See Figure 7.
By the definition of
we have
and
Subcase 2.2.
is odd.
Let
![]()
Figure 7. A total 9-coloring of
.
where
. See Figure 8.
By the definition of
we have
and
Case 3.
.
Let
. Then we have
, where
.
Subcase 3.1.
is even.
Let
![]()
Figure 8. A total 9-coloring of
.
and recolor
as
, where
. See Figure 9.
By the definition of
we have
and
Subcase 3.2.
is odd.
Let
![]()
Figure 9. A total 10-coloring of
.
where
. See Figure 10.
By the definition of
we have
and
Case 4.
.
Let
. Then we have
, where
.
Subcase 4.1.
is even.
Let
and recolor
as
, where
. See Figure 11.
![]()
Figure 10. A total 10-coloring of
.
By the definition of
we have
Subcase 4.2.
is odd.
Let
where
. See Figure 12.
By the definition of
we have
and
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
, we show
, prove that
(if
) or 4 (otherwise) and
, and determine the set
as
For any integer
, we have
, prove that
and
and, for any
between 5 and 4n,
. We conjecture that
.
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. Vizing, V.G. (1965) Chromatic Index of Multigraphs. Doctoral Thesis, Novosibirsk. (in Russian)
- 2. Behzad, M. (1965) Graphs and Their Chromatic Numbers. Ph.D. Thesis, Michigan State University, East Lansing, MI.
- 3. Petrosyan, P.A. (2007) Interval Total Colorings of Complete Bipartite Graphs. Proceedings of the CSIT Conference, Yerevan, 84-85.
- 4. Yap, H.P. (1996) Total Colorings of Graphs, Lecture Notes in Mathematics 1623. Springer-Verlag , Berlin.
- 5. Petrosyan, P.A., Torosyan, A.Yu. and Khachatryan, N.A. (2010) Interval Total Colorings of Graphs . arXiv:1010.2989v1.