Open Journal of Discrete Mathematics
Vol.08 No.03(2018), Article ID:84593,8 pages
10.4236/ojdm.2018.83006
Cyclically Interval Total Coloring of the One Point Union of Cycles
Shijun Su1, Wenwei Zhao2, Yongqiang Zhao3*
1School of Science, Hebei University of Technology, Tianjin, China
2School of Instrument Science and Opto-Electronics Engineering, Hefei University of Technology, Hefei, China
3School of Science, Shijiazhuang University, Shijiazhuang, China
Copyright © 2018 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: March 26, 2018; Accepted: May 15, 2018; Published: May 18, 2018
ABSTRACT
A total coloring of a graph G with colors is called a cyclically interval total t-coloring if all colors are used, and the edges incident to each vertex together with v are colored by consecutive colors modulo t, where is the degree of the vertex v in G. The one point union of k-copies of cycle is the graph obtained by taking v as a common vertex such that any two distinct cycles and are edge disjoint and do not have any vertex in common except v. In this paper, we study the cyclically interval total colorings of , where and .
Keywords:
Total Coloring, Interval Total Coloring, Cyclically Interval Total Coloring, Cycle, One Point Union of Cycles
1. Introduction
We denote the sets of vertices and edges in a graph G by and , respectively. For a vertex , we denote the degree of x in G by , and we use to denote the maximum degree of vertices of G.
For an arbitrary finite set A, we denote the number of elements of A by . We use to denote the set of positive integers. 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 . An interval D is called a h-interval if .
A total coloring of a graph G is a function mapping to such that no adjacent vertices, edges, and no incident vertices and edges obtain the same color. The concept of total coloring was introduced by V. Vizing [1] and independently by M. 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 t-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 t-coloring for some positive integer t. The concept of interval total coloring was first introduced by Petrosyan [3] .
Recently, Zhao and Su [4] generalized the concept interval total coloring to the cyclically interval total coloring as follow. A total t-coloring α of a graph G is called a cyclically interval total t-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 t-coloring for some positive integer t.
For any , we denote by the set of graphs for which there exists a cyclically interval total t-coloring. Let . For any graph , the minimum and the maximum values of t for which G has a cyclically interval total t-coloring are denoted by and , respectively.
It is clear that for any , the following inequality is true:
The one point union of k-copies of cycle is the graph obtained by taking v as a common vertex such that any two distinct cycles and are edge disjoint and do not have any vertex in common except v. In this paper, we
study the cyclically interval total colorability of . Let and , where is the i-th copy of and .
Without loss of generality, we may assume that the common vertex v of the k-copies of cycle is the first vertex in each cycle, i.e., . For example, the graphs in Figure 1 are all . Note that in the paper we always use the kind of diagram like (b) in Figure 1 to denote .
All graphs considered in this paper are finite undirected simple graphs.
2. Main Results
Vaidya and Isaac [5] studied the total coloring of and got the following result.
Theorem 1 (Vaidya and Isaac) For any integers and , .
Now we consider the cyclically interval total colorings of , show that , get the exact values of , and provide a lower bound of
(a) (b)
Figure 1. (a) ; (b) Another diagram of .
.
Theorem 2 For any integers and , .
Proof. Suppose that and . Let , where is the i-th copy of . Let , where . Without loss of generality, we may assume that the common vertex v of the k-copies of cycle is the first vertex in each cycle, i.e., . Now we define a total -coloring α of the graph as follows:
Case 1. .
Let
where for any . See Figure 2 for an example.
By the definition of α, we have
This shows that α is a cyclically interval total -coloring of .
Case 2. .
Let
Figure 2. 7-total coloring of .
where for any . Recolor and as and . See Figure 3 for an example.
By the definition of α, we have
This shows that α is a cyclically interval total -coloring of .
Case 3. .
Let
where for any . Recolor and as , , ,
, and . See Figure 4 for
Figure 3. 7-total coloring of .
Figure 4. 7-total coloring of .
an example.
By the definition of α, we have
This shows that α is a cyclically interval total -coloring of .
Combining Cases 1-3, we have . On the other hand, by Theorem 1, . So we have .
Theorem 3 For any integers and ,
Proof. Suppose that and . We consider the following two cases.
Case 1. .
Now we define a total -coloring α of the graph as follows:
Let
where for any . See Figure 5 for an example.
Figure 5. 20-total coloring of .
By the definition of α, we have
This shows that α is a cyclically interval total -coloring of . So we have if .
Case 2. .
Let and . Now we define a total
-coloring α of the graph as follows:
Let
where for any . See Figure 6 for an example.
By the definition of α, we have
This shows that α is a cyclically interval total
Figure 6. 20-total coloring of .
-coloring of . So we have for any
.
3. Generalization
The one point of union of any k cycles is the graph obtained by taking v as a common vertex such that any two distinct cycles and are edge disjoint and do not have any vertex in common except v.
By the proof of Theorem 2, the following definitions are well defined.
Definition 4 A partial -total coloring of is a coloring such that , and is an interval for each . A partial -total coloring of is a coloring such that , and is an interval for each .
Now we consider the cyclically interval total colorings of .
Theorem 5 For any integer , .
Proof. Suppose that graph is the one point of union of cycles . Let , where . Without loss of generality, we may assume that the common vertex v of the k cycles is the first vertex in each cycle, i.e., . Now we define a total
-coloring α of the graph as follows: Let , be a partial -total coloring of for each , and be a partial -total coloring of , respectively. By the definition of α,
is the largest color used in coloring α, and . By Definition 4, is an interval for each . So we have . On the other hand, since and , then .
In this section, we consider the one point of union of k cycles with different length, show that , get the exact values of , and the further research maybe more interesting.
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
Su, S.J., Zhao, W.W. and Zhao, Y.Q. (2018) Cyclically Interval Total Coloring of the One Point Union of Cycles. Open Journal of Discrete Mathematics, 8, 65-72. https://doi.org/10.4236/ojdm.2018.83006
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.
- 3. Petrosyan, P.A. (2007) Interval Total Colorings of Complete Bipartite Graphs. Proceedings of the CSIT Conference, 84-85.
- 4. Zhao, Y. and Su, S. (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
- 5. Vaidya, SK. and Isaac, R.V. (2015) Total Coloring of Some Cycle Related Graphs. IOSR Journal of Mathematics, 11, 51-53.