Several Kinds of Chromatic Numbers of Multi-fan Graphs
Shunqin Liu
School of Information Science & Technology, Xiamen University Tan Kah Kee College, Zhangzhou, China
Email address:
To cite this article:
Shunqin Liu. Several Kinds of Chromatic Numbers of Multi-fan Graphs. Applied and Computational Mathematics. Vol. 5, No. 3, 2016, pp. 133-137. doi: 10.11648/j.acm.20160503.16
Received: June 7, 2016; Accepted: July 8, 2016; Published: July 11, 2016
Abstract: Coloring problem is a classical difficult problem of graph theory. It is a fundamental problem in scientific computation and engineering design. In recent years, a variety of graph coloring problems frequently appeared and solved many problems in production. It is a difficult problem to discuss the chromatic number of a given graph class. In the paper, we introduce several kinds of chromatic numbers of graphs such as adjacent-vertex-distinguishing total chromatic number, adjacent-vertex-distinguishing proper edge chromatic number, smarandachely-adjacent-vertex-distinguishing edge chromatic number, and the multi-fan graphs are considered.
Keywords: Multi-fan Graphs, Adjacent-vertex-distinguishing Total Chromatic Number, Adjacent-vertex-distinguishing Proper Edge Chromatic Number, Smarandachely-adjacent-vertex-distinguishing Edge Chromatic Number
1. Introduction
Graph theory is an important branch of Applied Mathematics. Colouring problems originated in the four colour conjecture 150 years ago. In recent years, many interesting and useful results have been obtained on the study of colouring problems. It is widely used in chemistry, computer, communication and other fields. There for they are widely discussed in graph theory. In this paper, we introduce several kinds of chromatic numbers of graphs such as the adjacent -vertex -distinguishing total chromatic number, the adjacent –vertex-distinguishing proper edge chromatic number, the smarandachely-adjacent-vertex-distinguishing edge chromatic number. And the Multi-fan graphs are considered in this paper. In the end, the paper abtained the chromatic numbers of graphs the paper considered.
The graphs considered in this paper are connected, finite, undirected and simple graphs. The multi-fan graphs are joint graphs that jointed byand, which denotes the path graphs with order(). We denote for all, (), and denotes the graph which has only one vertex . The symbolis the maximum degree of the graph we discussed.
The paper use apagoge, construction method and direct proving method.
2. Adjacent-vertex-distinguishing Proper Total Coloring Number
Defenition 1 [1] A k-proper total colouring of a graph G is a mapping fromtosuch that:
1), if, then;
2),, ifhave a common end vertex, then ;
3), ifis the end vertex of, then .
Letbe a k-proper-total-colouring of .Denote for every , if, we have, thenis called a k-proper-adjacent-vertex-distinguishing proper total coloring, short for k-AVDTC.
The numberhas a k-proper-adjacent vertex-distinguishing total coloring} is called the adjacent –vertex-distinguishing proper total chromatic number and denoted by.
The adjacent –vertex-distinguishing proper total chromatic number was first put forward by Zhang Zhong-fu, and he show a conjecture such that:
Conjecture 1 [11] For every connected graph with order at least 2, we have.
Lemma 1 If two arbitrary distinct vertices of maximum degree inare not adjacent, then; Ifhas two distinct vertices of maximum degree which are adjacent, then
Theorem 1:
Proof. Because there is only one vertexwhose degree(=) is the maximum degree, so concluded by Lemma 1, we get the result such that
.
Then we let be a mapping from
to
as follows :
At this time, we have
As defined in definition 1, obviously, is a-AVDTC.
There for
Corollary 1
The proof of Corollary 1 can be easy done.
3. Adjacent-vertex-distinguishing Proper Edge Chromatic Number
Defenition 2 [2] A k-proper-edge-colouring of a graph G is a mapping fromtosuch that:
1),, ifhave a common end vertex, then;
Letbe a k-proper-edge-colouring of .Denote for every, if, we have, thenis called a k-proper-adjacent- vertex-distinguishing-edge coloring, short for k-AVDPEC.
The numberhas a k-proper-adjacent- vertex-distinguishing edge colouring} is called the adjacent –vertex-distinguishing edge chromatic number and denoted by.
For graphs ,denote the number of the vertex whose degree=, denote the minimum degree and the maximum degree of the graph. Then, define number such that
Then a conjecture was put forward by [12]
Conjecture 2 For graphs without isolated edge and the number of the isolated vertex is no more than one, then
Lemma 2: For all graphs,.
Theorem 2:
Proof. There is only one vertex whose degree(=) is the maximum degree, so concluded by Lemma 2, we get the result such that
Then we let be a mapping from
toas follows :
At this time, we have
As defined in definition 2, obviously, is a-AVDPEC.
There for
.
Corollary 2
.
The proof can be easy copied from the proof of Theorem 2.
4. Smarandachely Adjacent-vertex-distinguishing Proper Edge Chromatic Number
Defenition 3 [3] Let be a k-proper-edge-colouring of.Denote for every, if, we have and,then is called a smarandachely adjacent-vertex-distinguishing proper edge colouring, short for k-SA.
The number has a k smarandachely adjacent- vertex-distinguishing proper edge coloring} is called the smarandachely adjacent –vertex-distinguishing proper edge chromatic number and denoted by .
Lemma 3: If is a graph without one degree vertex, then.
Theorem 3:
i) Ifand ,
Then .
ii) Ifor , then
Proof. i) Obviously, the maximum degree of denotes by, then,
so
.
Then we give the mapping from
to
as below:
By listing of every vertex of the graph, we can see that the mapping we give is a smarandachely adjacent-vertex-distinguishing proper edge coloring of, so
.
ii) First, we must illustrate that there have no
-SA for graph.
Assume that:
Suppose that -SA for graph exist. And, so we denote,,
.
Because for all,
,
, there is times for, but is and odd number, the result is a contradiction to handshaking lemma.
So.
Then we define a mapping fromtolike this:
By listing of every vertex of the graph, we can see that the mapping we give is a smarandachely adjacent-vertex-distinguishing proper edge colouring of.
So .
5. Conclusion
Through the paper’s research, conclusions are follows:
Theorem 1:
Theorem 2:
Theorem 3:
i) Ifand ,
Then .
ii) Ifor , then
Theorem 1 and Theorem 2 are consistent with the Conjecture 1 and Conjecture 2. Then in future we can also study the upper limit of the smarandachely adjacent –vertex-distinguishing proper edge chromatic number.
References