Issue 
Wuhan Univ. J. Nat. Sci.
Volume 28, Number 3, June 2023



Page(s)  201  206  
DOI  https://doi.org/10.1051/wujns/2023283201  
Published online  13 July 2023 
Mathematics
CLC number: O157.5
ITotal Coloring and VITotal Coloring of mC_{4} VertexDistinguished by Multiple Sets
College of Mathematics and Statistics, Northwest Normal University, Lanzhou 730070, Gansu, China
^{†} To whom correspondence should be addressed. Email: chenxe@nwnu.edu.cn
Received:
8
December
2022
We give the optimal I(VI)total colorings of which are vertexdistinguished by multiple sets by the use of the method of constructing a matrix whose entries are the suitable multiple sets or empty sets and the method of distributing color set in advance. Thereby we obtain I(VI)total chromatic numbers of which are vertexdistinguished by multiple sets.
Key words: mC_{4} / Itotal coloring / VItotal coloring / multiple sets / vertexdistinguished
Biography: WANG Nana, female, Master candidate, research direction: graph theory and its application. Email: wangnana202106@163.com
Fundation item: Supported by the National Natural Science Foundation of China (11761064)
© Wuhan University 2023
This is an Open Access article distributed under the terms of the Creative Commons Attribution License (https://creativecommons.org/licenses/by/4.0), which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.
0 Introduction
All graphs discussed in this paper are simple, nondirected graphs. Many conclusions have been obtained regarding the vertexdistinguished proper edge coloring^{[13]} and vertexdistinguished general edge coloring^{[47] }of graphs. In 2008, Zhang et al^{[8]} proposed vertexdistinguished total coloring and related conjectures of graphs. In 2014, Chen et al^{[9] } introduced vertexdistinguished Itotal coloring and related conjectures of graphs. Many studies have been made on vertexdistinguished I(VI)total colorings of graphs ^{[1012]}. In this study, we consider vertexdistinguished I(VI)total colorings of by multiple sets.
Let be a simple graph. Suppose a mapping is a general total coloring of (not necessarily proper). If , and are adjacent vertices, we have , and if , we have , then is called the Itotal coloring of . If any two adjacent edges of receives different colors, then is called VItotal coloring of . Obviously, Itotal coloring is VItotal coloring, and the reverse is uncertain. For an I total coloring (resp.VI total coloring) of , if colors are used, then is called Itotal coloring of (resp.VItotal coloring). Note that when we refer to the Itotal coloring (resp.VItotal coloring) of graph, we always assume that the colors used are .
Let be a general total coloring of . For any vertex in , denotes the multiple set of colors of vertex and edges that are incident of vertex . is said to be the color set of under . No confusion arises when using . Obviously, . If for any two distinct vertices and of , then is called vertexdistinguished by multiple sets. Let
{ has Itotal coloring which is vertexdistinguished by multiple sets}
and
{ has VItotal coloring which is vertexdistinguished by multiple sets}.
Then, is called the Itotal chromatic number of which is vertexdistinguished by multiple sets. Similarly, is called the VItotal chromatic number of which is vertexdistinguished by multiple sets. Let represent the number of vertices of degree . Suppose that
Proposition 1 .
Proof Obviously, Itotal coloring is VItotal coloring. Thus .
Set has VItotal coloring which are vertexdistinguished by multiple sets. For . Considering the vertices of the degree , we obtain
Thus, . Therefore, , namely . This completes the proof.
1 Preliminaries
We first define a matrix , for any ,
Let . Submatrix is an matrix. It is comprised by all the elements which are only in or rows but also in or columns of . The following six schemes are presented for the Itotal coloring of which are vertexdistinguished by multiple sets. Note that all lowercase letters represent different colors.
In Fig. 1(a), the color set of each vertex of is . This coloring scheme is Co1.
Fig.1 The coloring scheme Co1, Co2, and Co3 
In Fig. 1(b), the color set of each vertex of is . This coloring scheme is Co2.
In Fig. 1(c), the color set of each vertex of is . This coloring scheme is Co3.
In Fig. 2(a), the color set of each vertex of is . This coloring scheme is Co4.
Fig.2 The coloring scheme Co4, Co5, and Co6 
In Fig. 2(b), the color set of each vertex of is . This coloring scheme is Co5.
In Fig. 2(c), the color set of each vertex of is . This coloring scheme is Co6.
Lemma 1 When ( is an odd number), are the color sets of the vertices under Itotal coloring of which are vertexdistinguished by multiple sets in Fig. 1(a).
Lemma 2 When , and are not , , are the color sets of the vertices under Itotal coloring of which are vertexdistinguished by multiple sets in Fig. 1(b).
Lemma 3 If , then for except can be divided into groups, each group has four 3subsets. These are the color sets of the vertices under Itotal coloring of which are vertexdistinguished by multiple sets.
Proof We use Lemmas 1 and 2, and only consider the remaining entries of .
Case 1: .
For each , considering the remaining entries of the columns: . These four 3subsets are the color sets of the vertices in Co4.
Case 2: .
Ⅰ. The remaining entries in columns can be divided into two groups, . The corresponding coloring schemes are Co3 and Co4, respectively.
Ⅱ. For each , considering the remaining entries of the columns, which can be divided into three groups:
. The corresponding coloring schemes are Co4, Co4, and Co4, respectively.
Lemma 4 If , then all nonempty sets in except for (when ) or (when ) can be divided into groups, and each group has four 3subsets. These are the color sets of the vertices under Itotal coloring of which are vertexdistinguished by multiple sets.
Proof We use Lemmas 1 and 2, and only consider the remaining entries of .
Case 1: .
For the remaining entries in columns, the grouping is obtained and the corresponding coloring scheme is determined using Lemma 3 Case 2 Ⅰ. For , considering the remaining entries of the columns, the grouping is obtained and the corresponding coloring scheme is determined using Lemma 3 Case 2 Ⅱ. For the six remaining entries in columns, there is a group , namely Co4.
This leaves the 3subsets .
Case 2: .
For each , considering the remaining entries in columns, the grouping is obtained and the corresponding coloring scheme is determined using Lemma 3 Case 1.
This leaves the 3subsets .
Lemma 5 If , then all nonempty sets in except for (when ) or (when ) can be divided into groups, and each group has four 3subsets. These are the color sets of the vertices under Itotal coloring of which are vertexdistinguished by multiple sets.
Proof We use Lemmas 1 and 2, and only consider the entries of .
Case 1: .
For each , considering the remaining entries in columns , the grouping is obtained and the corresponding coloring scheme is determined using Lemma 3 Case 1.
This leaves the 3subsets .
Case 2: .
For the remaining entries of columns, the grouping is obtained and the corresponding coloring scheme is determined using Lemma 3 Case 2 Ⅰ. For , considering the remaining entries of the columns, the grouping is obtained and the corresponding coloring scheme is determined using Lemma 3 Case 2.
This leaves the 3subsets .
Lemma 6 If , then all nonempty sets in except can be divided into groups, and each group has four 3subsets. These are the color sets of the vertices under Itotal coloring of which are vertexdistinguished by multiple sets.
Proof We use Lemmas 1 and 2, and only consider the remaining entries of .
For each , considering the remaining entries of the columns, the grouping is obtained and the corresponding coloring scheme is determined using Lemma 3 Case 1.
This leaves 3subset .
Lemma 7 If , then all nonempty sets in except for can be divided into groups, and each group has four 3subsets. These are the color sets of the vertices under Itotal colorings of which are vertexdistinguished by multiple sets.
Proof We use Lemmas 1 and 2, and only consider the remaining entries of .
For the remaining entries in columns, the grouping is obtained and the corresponding coloring scheme is determined using Lemma 3 Case 2 Ⅰ. For , considering the remaining entries in columns , the grouping is obtained and the corresponding coloring scheme is determined using Lemma 3 Case 2. For the remaining in columns, there is a group except for , namely Co4.
This leaves the 3subsets .
2 Main Results and Their Proofs
Theorem 1 If , then .
Proof Obviously, there is . Therefore, we can directly give the Itotal coloring of which are vertexdistinguished by multiple sets.
① When . Use , that is, Co1 to color the first . Thus, the multiple 3subsets remain.
② When . Based on Itotal coloring of the first , we start coloring from the second . According to Lemma 1, one can be colored with Co1. Subsequently, the multiple 3subsets remain. The third is colored with Co1, under which the color sets of four vertices are and ① remaining . The fourth is colored with ① remaining and , as illustrated in Fig.3. Thus far, all multiple 3subsets of have been used.
Fig.3 Vertexdistinguished Itotal coloring of 
③ When . Based on the previous step, we start coloring from the 5th . According to Lemmas 1 and 2, can be colored with Co1, Co1, and Co2. Subsequently, the multiple 3subset remain.
④ When . Based on the Itotal coloring of which are vertexdistinguished by multiple sets, we start coloring from the 8th . According to Lemmas 1 and 2, can be colored with Co1, Co1, and Co2. The remaining entries are , which can be divided into two groups that can color with Co3 and Co4. As all multiple 3subsets containing 6 are used up in the above coloring, the remaining 3subsets are still .
⑤ When . Based on the Itotal coloring of which are vertexdistinguished by multiple sets, we color from the 13th to 19th . According to Lemmas 1 and 2, can be colored with the Co1, Co1, Co1, Co2, Co2, and Co2. Now, the 3subsets and ③ remaining are used to color the 19th with Co6. Due to the above coloring, all multiple 3subsets containing 7 are used. Thus, the remaining 3subset is still left.
⑥ When . We start from the 20th based on the preceding coloring. According to Lemmas 1 and 2, can be colored with Co1, Co1, Co1, Co2, Co2 and Co2. The remaining 3subsets are . The 3subsets are used to color the 26th with Co3. The 27th is colored with Co4, under which the color sets of four vertices are . The 3subsets and ③ remaining are used to color the 28th with Co5. Consequently, all multiple 3subsets of have been used.
⑦ Let , we recursively proceed as following process.
We have obtained (Itotal coloring of which are vertexdistinguished by multiple sets. On this basis, we will construct the Itotal coloring from the th to th which are vertexdistinguished by multiple sets.
When . Using Lemma 3, we can obtain the Itotal coloring of , which are vertexdistinguished by multiple sets, and we have used all 3subsets of .
When . Using Lemma 4, we can obtain the Itotal coloring of , which are vertexdistinguished by multiple sets, and we have used all 3subsets of except for .
When . Using Lemma 6, we can obtain Itotal coloring of , which are vertexdistinguished by multiple sets. We have used all 3subsets of except for and the above mentioned .
When . Using Lemma 7, we can obtain the Itotal coloring of , which are vertexdistinguished by multiple sets. We have used all 3subsets of except for and the above mentioned . The th is colored with Co2, under which the color sets of four vertices are . The 3subsets are used to color the th with Co5. At this time, we obtained the Itotal coloring of , which are vertexdistinguished by multiple sets. Moreover, all multiple 3subsets of have been used.
When . Using Lemma 4, we can obtain the Itotal coloring of , which are vertexdistinguished by multiple sets. We have used all 3subsets of except for .
When . Using lemma 3, we can obtain the Itotal coloring of , which are vertexdistinguished by multiple sets. We have used all 3subsets of except for the above mentioned .
When . Using lemma 5, we can obtain the Itotal coloring of , which are vertexdistinguished by multiple sets. We have used all the 3subsets of except for and the above mentioned . The 3subsets are used to color the th with Co6. Then the 3subset remains.
When . Using Lemma 5, we can obtain the Itotal coloring of , which are vertexdistinguished by multiple sets. We have used all the 3subsets of except for and the above mentioned . The th is colored with the above four 3subsets, that is, Co5. Thus far, all multiple 3subsets of have been used.
The theorem is proven.
Theorem 2 If , .
Proof This conclusion can be obtained by the proof of Proposition 1 and Theorem 1.
3 Conclusion
In this study, the I(VI)total chromatic numbers of have been obtained, which are vertexdistinguished by multiple sets. According to the characteristics of the cycles and multiple sets, the (even number) of the I(VI)total chromatic numbers and VItotal of the multiple sets can be similarly obtained according to the above methods. That is, if is satisfied, then and , and two cases of recursive boundary conditions can be inferred in the proof process: if , then ; if , then . The I(VI)total colorings of odd order cycles which are vertexdistinguished by multiple sets will be studied at a later stage.
References
 Burris A C. VertexDistinguishing EdgeColorings[D]. Memphis: Memphis State University, 1993: 115. [Google Scholar]
 Burris A C, Schelp R H. Vertexdistinguishing proper edgecolorings[J]. Journal of Graph Theory, 1997, 26(2): 7382. [CrossRef] [MathSciNet] [Google Scholar]
 Balister P N, Riordan O M, Schelp R H. Vertexdistinguishing edge colorings of graphs[J]. Journal of Graph Theory, 2003, 42(2): 95109. [CrossRef] [MathSciNet] [Google Scholar]
 Horňák M, Soták R. The fifth jump of the pointdistinguishing chromatic index of [J]. Ars Combinatoria, 1996, 42: 233242. [MathSciNet] [Google Scholar]
 Horňák M, Soták R. Localization of jumps of the pointdistinguishing chromatic index of [J]. Discuss Math Graph Theory, 1997, 17(2): 243251. [CrossRef] [MathSciNet] [Google Scholar]
 Horňák M, Salvi N Z. On the pointdistinguishing chromatic index of complete bipartite graphs[J]. Ars Combinatoria, 2006, 80: 7585. [MathSciNet] [Google Scholar]
 Salvi N Z. On the value of the pointdistinguishing chromatic index of [J]. Ars Combinatoria, 1990, 29B: 235244. [Google Scholar]
 Zhang Z F, Qiu P X, Xu B G, et al. Vertexdistinguishing total coloring of graphs[J]. Ars Combinatoria, 2008, 87: 3345. [MathSciNet] [Google Scholar]
 Chen X E, Li Z P. Vertexdistinguishing Itotal colorings of graphs[J]. Utilitas Mathematica, 2014, 95: 319327. [MathSciNet] [Google Scholar]
 Chen X E, Miao T T, Wang Z W. Vertexdistinguishing Itotal colorings of the join of two paths[J]. Journal of Shandong University (Science Edition), 2017, 52(4):3033(Ch). [MathSciNet] [Google Scholar]
 Miao T T, Wang Z W, Chen X E. Vertexdistinguishing Itotal colorings and vertexdistinguishing VItotal colorings of joingraph of cycle and path[J]. Journal of Dalian University of Technology, 2017, 57(4):430435(Ch). [Google Scholar]
 Yang H, Chen X E. Vertexdistinguishing Itotal colorings and vertexdistinguishing VItotal colorings of [J]. Journal of Xiamen University(Natural Science Edition), 2020,59(1):8589(Ch). [Google Scholar]
All Figures
Fig.1 The coloring scheme Co1, Co2, and Co3 

In the text 
Fig.2 The coloring scheme Co4, Co5, and Co6 

In the text 
Fig.3 Vertexdistinguished Itotal coloring of 

In the text 
Current usage metrics show cumulative count of Article Views (fulltext article views including HTML views, PDF and ePub downloads, according to the available data) and Abstracts Views on Vision4Press platform.
Data correspond to usage on the plateform after 2015. The current usage metrics is available 4896 hours after online publication and is updated daily on week days.
Initial download of the metrics may take a while.