Open Access
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

© Wuhan University 2023

Licence Creative CommonsThis 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, non-directed graphs. Many conclusions have been obtained regarding the vertex-distinguished proper edge coloring[1-3] and vertex-distinguished general edge coloring[4-7] of graphs. In 2008, Zhang et al[8] proposed vertex-distinguished total coloring and related conjectures of graphs. In 2014, Chen et al[9] introduced vertex-distinguished I-total coloring and related conjectures of graphs. Many studies have been made on vertex-distinguished I-(VI-)total colorings of graphs [10-12]. In this study, we consider vertex-distinguished 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 I-total coloring of . If any two adjacent edges of receives different colors, then is called VI-total coloring of . Obviously, I-total coloring is VI-total coloring, and the reverse is uncertain. For an I- total coloring (resp.VI- total coloring) of , if colors are used, then is called -I-total coloring of (resp.-VI-total coloring). Note that when we refer to the -I-total coloring (resp.-VI-total 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 vertex-distinguished by multiple sets. Let

{ has -I-total coloring which is vertex-distinguished by multiple sets}

and

{ has -VI-total coloring which is vertex-distinguished by multiple sets}.

Then, is called the I-total chromatic number of which is vertex-distinguished by multiple sets. Similarly, is called the VI-total chromatic number of which is vertex-distinguished by multiple sets. Let represent the number of vertices of degree . Suppose that

Proposition 1   .

Proof   Obviously, I-total coloring is VI-total coloring. Thus .

Set has -VI-total coloring which are vertex-distinguished 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 I-total coloring of which are vertex-distinguished 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.

thumbnail 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.

thumbnail 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 I-total coloring of which are vertex-distinguished by multiple sets in Fig. 1(a).

Lemma 2   When , and are not , , are the color sets of the vertices under I-total coloring of which are vertex-distinguished by multiple sets in Fig. 1(b).

Lemma 3   If , then for except can be divided into groups, each group has four 3-subsets. These are the color sets of the vertices under I-total coloring of which are vertex-distinguished 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 3-subsets 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 non-empty sets in except for (when ) or (when ) can be divided into groups, and each group has four 3-subsets. These are the color sets of the vertices under I-total coloring of which are vertex-distinguished 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 3-subsets .

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 3-subsets .

Lemma 5   If , then all non-empty sets in except for (when ) or (when ) can be divided into groups, and each group has four 3-subsets. These are the color sets of the vertices under I-total coloring of which are vertex-distinguished 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 3-subsets .

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 3-subsets .

Lemma 6   If , then all non-empty sets in except can be divided into groups, and each group has four 3-subsets. These are the color sets of the vertices under I-total coloring of which are vertex-distinguished 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 3-subset .

Lemma 7   If , then all non-empty sets in except for can be divided into groups, and each group has four 3-subsets. These are the color sets of the vertices under I-total colorings of which are vertex-distinguished 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 3-subsets .

2 Main Results and Their Proofs

Theorem 1   If , then .

Proof   Obviously, there is . Therefore, we can directly give the -I-total coloring of which are vertex-distinguished by multiple sets.

① When . Use , that is, Co1 to color the first . Thus, the multiple 3-subsets remain.

② When . Based on I-total coloring of the first , we start coloring from the second . According to Lemma 1, one can be colored with Co1. Subsequently, the multiple 3-subsets 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 3-subsets of have been used.

thumbnail Fig.3

Vertex-distinguished I-total coloring of

③ When . Based on the previous step, we start coloring from the 5-th . According to Lemmas 1 and 2, can be colored with Co1, Co1, and Co2. Subsequently, the multiple 3-subset remain.

④ When . Based on the I-total coloring of which are vertex-distinguished by multiple sets, we start coloring from the 8-th . 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 3-subsets containing 6 are used up in the above coloring, the remaining 3-subsets are still .

⑤ When . Based on the I-total coloring of which are vertex-distinguished by multiple sets, we color from the 13-th to 19-th . According to Lemmas 1 and 2, can be colored with the Co1, Co1, Co1, Co2, Co2, and Co2. Now, the 3-subsets and ③ remaining are used to color the 19-th with Co6. Due to the above coloring, all multiple 3-subsets containing 7 are used. Thus, the remaining 3-subset is still left.

⑥ When . We start from the 20-th based on the preceding coloring. According to Lemmas 1 and 2, can be colored with Co1, Co1, Co1, Co2, Co2 and Co2. The remaining 3-subsets are . The 3-subsets are used to color the 26-th with Co3. The 27-th is colored with Co4, under which the color sets of four vertices are . The 3-subsets and ③ remaining are used to color the 28-th with Co5. Consequently, all multiple 3-subsets of have been used.

⑦ Let , we recursively proceed as following process.

We have obtained (-I-total coloring of which are vertex-distinguished by multiple sets. On this basis, we will construct the I-total coloring from the -th to -th which are vertex-distinguished by multiple sets.

When . Using Lemma 3, we can obtain the -I-total coloring of , which are vertex-distinguished by multiple sets, and we have used all 3-subsets of .

When . Using Lemma 4, we can obtain the -I-total coloring of , which are vertex-distinguished by multiple sets, and we have used all 3-subsets of except for .

When . Using Lemma 6, we can obtain -I-total coloring of , which are vertex-distinguished by multiple sets. We have used all 3-subsets of except for and the above mentioned .

When . Using Lemma 7, we can obtain the -I-total coloring of , which are vertex-distinguished by multiple sets. We have used all 3-subsets of except for and the above mentioned . The -th is colored with Co2, under which the color sets of four vertices are . The 3-subsets are used to color the -th with Co5. At this time, we obtained the -I-total coloring of , which are vertex-distinguished by multiple sets. Moreover, all multiple 3-subsets of have been used.

When . Using Lemma 4, we can obtain the -I-total coloring of , which are vertex-distinguished by multiple sets. We have used all 3-subsets of except for .

When . Using lemma 3, we can obtain the -I-total coloring of , which are vertex-distinguished by multiple sets. We have used all 3-subsets of except for the above mentioned .

When . Using lemma 5, we can obtain the -I-total coloring of , which are vertex-distinguished by multiple sets. We have used all the 3-subsets of except for and the above mentioned . The 3-subsets are used to color the -th with Co6. Then the 3-subset remains.

When . Using Lemma 5, we can obtain the -I-total coloring of , which are vertex-distinguished by multiple sets. We have used all the 3-subsets of except for and the above mentioned . The -th is colored with the above four 3-subsets, that is, Co5. Thus far, all multiple 3-subsets 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 vertex-distinguished by multiple sets. According to the characteristics of the cycles and multiple sets, the (even number) of the I-(VI-)total chromatic numbers and VI-total 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 vertex-distinguished by multiple sets will be studied at a later stage.

References

  1. Burris A C. Vertex-Distinguishing Edge-Colorings[D]. Memphis: Memphis State University, 1993: 1-15. [Google Scholar]
  2. Burris A C, Schelp R H. Vertex-distinguishing proper edge-colorings[J]. Journal of Graph Theory, 1997, 26(2): 73-82. [CrossRef] [MathSciNet] [Google Scholar]
  3. Balister P N, Riordan O M, Schelp R H. Vertex-distinguishing edge colorings of graphs[J]. Journal of Graph Theory, 2003, 42(2): 95-109. [CrossRef] [MathSciNet] [Google Scholar]
  4. Horňák M, Soták R. The fifth jump of the point-distinguishing chromatic index of Formula [J]. Ars Combinatoria, 1996, 42: 233-242. [MathSciNet] [Google Scholar]
  5. Horňák M, Soták R. Localization of jumps of the point-distinguishing chromatic index of Formula [J]. Discuss Math Graph Theory, 1997, 17(2): 243-251. [CrossRef] [MathSciNet] [Google Scholar]
  6. Horňák M, Salvi N Z. On the point-distinguishing chromatic index of complete bipartite graphs[J]. Ars Combinatoria, 2006, 80: 75-85. [MathSciNet] [Google Scholar]
  7. Salvi N Z. On the value of the point-distinguishing chromatic index of Formula [J]. Ars Combinatoria, 1990, 29B: 235-244. [Google Scholar]
  8. Zhang Z F, Qiu P X, Xu B G, et al. Vertex-distinguishing total coloring of graphs[J]. Ars Combinatoria, 2008, 87: 33-45. [MathSciNet] [Google Scholar]
  9. Chen X E, Li Z P. Vertex-distinguishing I-total colorings of graphs[J]. Utilitas Mathematica, 2014, 95: 319-327. [MathSciNet] [Google Scholar]
  10. Chen X E, Miao T T, Wang Z W. Vertex-distinguishing I-total colorings of the join of two paths[J]. Journal of Shandong University (Science Edition), 2017, 52(4):30-33(Ch). [MathSciNet] [Google Scholar]
  11. Miao T T, Wang Z W, Chen X E. Vertex-distinguishing I-total colorings and vertex-distinguishing VI-total colorings of join-graph of cycle and path[J]. Journal of Dalian University of Technology, 2017, 57(4):430-435(Ch). [Google Scholar]
  12. Yang H, Chen X E. Vertex-distinguishing I-total colorings and vertex-distinguishing VI-total colorings of Formula [J]. Journal of Xiamen University(Natural Science Edition), 2020,59(1):85-89(Ch). [Google Scholar]

All Figures

thumbnail Fig.1

The coloring scheme Co1, Co2, and Co3

In the text
thumbnail Fig.2

The coloring scheme Co4, Co5, and Co6

In the text
thumbnail Fig.3

Vertex-distinguished I-total coloring of

In the text

Current usage metrics show cumulative count of Article Views (full-text 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 48-96 hours after online publication and is updated daily on week days.

Initial download of the metrics may take a while.