图的线性染色

来源 :浙江师范大学 | 被引量 : 0次 | 上传用户:luwenfei7782
下载到本地 , 更方便阅读
声明 : 本文档内容版权归属内容提供方 , 如果您对本文有版权争议 , 可与客服联系进行内容授权或下架
论文部分内容阅读
用G=(V, E)表示一个顶点集为V,边集为E的有限、简单无向图,{1,2,…,k)表示k个颜色的集合.G的一个正常k-染色是一个映射φ:V→(1,2…,k)使得相邻的顶点接受不同的色.如果G有一个正常k-染色,则称G是k-可染的.G的色数x(G)是使得G是正常k-可染的最小的非负整数七.如果图G的一个正常染色满足染任意两种颜色的顶点集合导出的子图是一些点不交的路的并,则称这个正常染色为图G的线性染色.图G的线性色数用1c(G)表示,是指G的所有线性染色中所用的最少颜色的个数. 1998年,Yuster[1]首先研究了图的线性染色.证明了任意图G的线性色数满足1c(G)=○(△3/2),且构造出了一类图使得1c(G)=Ω(△3/2).事实上,这个概念是图的无圈染色的一种特殊情形.无斟染色的概念是由Grunbaum[2]提出的,图G的一个无圈染色是G的一个正常染色,使得染任意两种颜色的顶点集合导出的子图是一个森林. 本学位论文主要是对前人的一些研究结果的改进和扩充,对非负特征图、平面图和一些度数较小的图的的研究.设△(G)和g(G)分别表示图G的最大度和围长. 在第一章中,我们给出本文所用到的基本概念,简述了相关领域的研究现状以及呈现了本文的主要结果. 在第二章中,我们证明了下面的结果: (1)对于每一个非负特征图G,若存在一个有序对(△,g)∈{(13,7),(9,8),(7,9),(5,10),(3,13))使得△(G)≥△且g(G)≥g,则1c(G)=[△(G)/2]+1. 在第三章中,我们获得了下而的结果: (1)对于每一个平面图G,若满足△(G)≥3且g(G)≥12或者△(G)≥7且g(G)≥8,则1c(G)=[△(G)/2]+1. 在第四章中,我们又对度数较小的图进行了研究,得到了下面两个结果: (1)若图G的最大度为4,则1c(G)≤8. (2)若图G的最大度为5,则1c(G)≤14.
其他文献
本文利用如下方法构造了一个图,以Fq(2v)中m维全迷向子空间为顶点集,定义邻接关系:设M,N为两个不同的顶点,M~N当且仅当rank(MKNT)=1,dim(M∩N)=m-1,其中M~N表示M与N是邻接的,K是Fq上非
AD HOC网络也称移动自组织网络,它是由一组自主的无线节点或终端相互合作而形成的,它独立于通常意义上的网络基础设施,运行在此网络中的所有节点具有独立自主性、分布式运行
在非寿险精算领域中,人们着重于研究单业务的准备金的估计,在非寿险公司对所有业务的总准备金水平进行评估时,因为不同业务的之间存在着一定的相关关系,所以将单业务的准备金进行简单的相加得到的总准备金往往会大于或小于实际理赔金额。因此,我们研究多业务的赔款准备金是十分必要的。多元未决赔款准备金的一种研究方法是利用多元链梯法模型和多元加法模型,而本文利用的是Copula连接函数,将关于单个业务的赔款变量的一