Applied and Computational Mathematics
Volume 5, Issue 3, June 2016, Pages: 133-137

Several Kinds of Chromatic Numbers of Multi-fan Graphs

Shunqin Liu

School of Information Science & Technology, Xiamen University Tan Kah Kee College, Zhangzhou, China

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.

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

1. Chen Xiang-en, Zhang Zhong-fu, " Adjacent-Vertex-Distinguishing Total Chromatic Number of ," Journal of Mathematical Reserch and Exposition, Dalian. vol. A2 6, pp. 489-494, August 2015.
2. Liu Hua, Ye Jian-hua, "Adjacent Vertex-Distinguishing Edges Coloring of ()" Journal of East China Jiaotong University. vol 24. pp. 157-158, October 2007.
3. Liu Shun-qin, Chen Xiang-en. "Smarandachely Adjacent-vert -ex-distinguishing Proper Edge Coloring of ". Journal of Lanzhou University of Technology. vol. 41. pp. 155-158, August 2015.
4. Zhang Dong-han, Zhang Zhong-fu. "The Upper Bound of the Adjacent Vertex Strongly Distinguishing Total Chromatic Number of the Graph". Advances in Mathematics. vol. 40 pp. 168-172. April 2011.
5. Qiang Hui-ying, Li Mu-chun. "A Bound on Vertex Distinguishing Total Coloring of Graphs with Distance Constrant for Recurrent Event Data". Acta Mathematicae Applicatae Sinica. vol. 34. pp. 554-559. May 2011.
6. Tian Jing-jing, Deng Fang-an. "Adjacent Vertex-distinguishing VE-Total Chromatic Number of the Crown Graph and ". Mathematics in Practice and Theory. vol. 41. pp. 189-192. August. 2011.
7. Yao Bing, Cheng Hui. "Behaviors of Vertex Neighbors of Trees Under Some Graph Coloring". AclaMathematica Scientia. vol. 31. pp. 567-576. May 2011
8. Wen Fei, Wang Zhi-wen. "Vertex –distinguishing Total Coloring of Some Complement Double Graphs’. Journal of Shandong University (Natural Science). vol. 46. pp. 45-50 February 2011.
9. Chen Xiang-en, Ma Yan-rong. "Adjacent-Vertex-Distingui -shing Total Chromatic Number of ". Journal of Jilin University (Science Edition). vol. 49. pp. 68-70. January 2011.
10. Tian Jing-jing. "The Smarandachely Adjacent –Vertex –Eege Coloring of Some Mycielski’s Graph". Journal of Math(PRC). vol. 32. pp. 723-728. April 2012.
11. Zhang Zhong-fu, Chen Xiang-en, Li Jing-wen. "On adjacent –vertex-distinguishing total coloring of graphs." Sci.China. Ser vol. 48. pp. 289-299. June 1997.
12. Li Jing-wen, Xu Ban-gen, Li Mu-chun. "On the vertex-distinguishing chromatic number of " Journal of Shan Dong University (Nature Science ). vol. 43. pp. 24-30 August 2008.

 Contents 1. 2. 3. 4. 5.
Article Tools