【作者】 杨超；

【导师】 姚兵；

【作者基本信息】 西北师范大学 ， 运筹学与控制论， 2014， 硕士

【摘要】 图的着色问题是图论的重要问题之一.它产生于计算机科学,有很强的理论意义和实际意义.目前,随着图的着色问题在现实中被广泛应用,它逐渐成为众多学者研究的重要领域之一.对图的不同着色问题的研究,已有了较为丰富的结果,并且这些结果仍在进一步完善之中.本文在图的邻点可区别全着色的基础上,创新性提出图在N(N=2,3,4)种可区分约束下的点可区别全着色概念.通过调查,此类着色方式在国内外尚未被发现和研究.全文共分为四章.第一章,给出图的一些基本的定义和术语,介绍了图着色的一些现状.最后,列举了本文的主要研究结果.第二章,对小度数图和复合交叉圈的邻点可区别全着色问题进行了研究,确定了这两类图的邻点可区别全色数.第三章,确定图在N(N=2,3,4)种可区分约束下的点可区别全着色定义：(i)(2)-点可区别全着色；(ii)(3)-邻点可区别全着色；(iii)(4)-邻点可区别全着色；(iv)(4)-点可区别全着色.基于上述四种新概念,对树,路,圈,完全二部图,P2∨Pn,广义Petersen图,星,扇,轮,双星等图进行了研究,并得到：(a)树的(2)-点可区别全色数;(b)P2∨Pn,完全二部图的(3)-邻点可区别全色数；(c)路,圈,完全二部图,广义Petersen图的(4)-邻点可区别全色数；(d)星,扇,轮,双星的(4)-点可区别全色数.第四章,我们给出了图的可区别着色中的几个可研究课题.本文的创新之处是：(1)提出图在混合点可区别约束下的全着色；(2)给出两个猜想：●x"(3)as(G)≤△(G)+3,●x"(4)as(G)≤△(G)+4.更多还原

【Abstract】 Graph coloring is one of the most important problems in graph theory, it re-sults from computer science, and has a strong theoretical significance and practicalsignificance. Now, graph colorings are widely applied in the world, and will becomean important field where many researchers have concerned with. Up to now, onehave obtained many rich results, and these results are still under improvement.Based on adjacent vertex distinguishing total coloring, this thesis presents sev-eral concepts on graph colorings with N (N=2,3,4) distinguishing constraintsfor the first time. Through investigation, such graph colorings are not found andstudied in domestic and overseas. We have constructed our works in four chapters.In Chapter1, firstly, notations and terminologies of graph theory are introducedand defined. Secondly, we introduce some current states of graph colorings. Lastly,the main results in this thesis are listed.In Chapter2, we consider the problem of adjacent vertex distinguishing totalcoloring of graphs having smaller degrees and compound intersecting cycles, and theadjacent vertex distinguishing total chromatic number of these two kinds of graphshave been obtained.In Chapter3, we present new graph colorings with N (N=2,3,4) distinguishingconstraints as follows:(2)-vertex distinguishing total coloring;(3)-adjacent vertex distinguishing total coloring;(4)-adjacent vertex distinguishing total coloring;(4)-vertex distinguishing total coloring. Based on the above graph colorings, trees, paths, cycles, complete bipartitegraphs, P2∨Pn, generalized Petersen graphs, stars, fans, wheels and double starshave been studied in this thesis. We determine:(2)-vertex distinguishing total chromatic number of trees;(3)-adjacent vertex distinguishing total chromatic number of P2∨Pnandcomplete bipartite graphs;(4)-adjacent vertex distinguishing total chromatic number of paths, cycles,complete bipartite graphs and generalized Petersen graphs;(4)-vertex distinguishing total chromatic number of stars, fans, wheels anddouble stars.In Chapter4, we give some further researching problems of graph coloring.My innovations are to propose:(1) total colorings of graphs with mixed vertex distinguishing constraints;(2) two conjectures:conjecture1: χ′′(3)as(G)≤(G)+3.conjecture2: χ′′(4)as(G)≤(G)+4.更多还原