关于具有一个或多个可区分约束条件的图着色研究

摘要

图的着色问题是图论的重要问题之一。它产生于计算机科学,有很强的理论意义和实际意义.目前,随着图的着色问题在现实中被广泛应用,它逐渐成为众多学者研究的重要领域之一.对图的不同着色问题的研究,已有了较为丰富的结果,并且这些结果仍在进一步完善之中.
　　本文在图的邻点可区别全着色的基础上,创新性提出图在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)给出两个猜想（公式略）。

目录

封面

声明

目录

英文摘要

中文摘要

Chapter 1 Introduction

1.1 Notations and Terminologies

1.2 Results on Graph Colorings

1.3 Main Results

Chapter 2 Graph Colorings Having One Distinguishing Constraints

2.1 Adjacent Vertex Distinguishing Total Colorings of Graphs with Smaller Degrees

2.2 Adjacent Vertex Distinguishing Total Colorings of Compound Intersecting Cycles

Chapter 3 Graph Colorings Having Two or More Distinguishing Constraints

3.1 \(2\)-Vertex Distinguishing Total Colorings

3.2 \(3\)-Adjacent Vertex Distinguishing Total Col- orings

3.3 \(4\)-Adjacent Vertex Distinguishing Total Col- orings

3.4 \(4\)-Vertex Distinguishing Total Colorings

Published and Submitted Papers During Graduate Study Period

读研期间参加的国家科研项目和学术会议活动

致谢