摘要: 图论是近二十年来发展十分迅速,应用比较广泛的一个新兴的学科,它属于离散数学的一个分支.在20世纪50年代,图论作为一门独立的学科开始出现.随着社会的发展需要,图论被广泛应用于诸如:物理学,化学,运筹学,计算机,信息论,控制论,网络理论以及经济管理等... 展开 图论是近二十年来发展十分迅速,应用比较广泛的一个新兴的学科,它属于离散数学的一个分支.在20世纪50年代,图论作为一门独立的学科开始出现.随着社会的发展需要,图论被广泛应用于诸如:物理学,化学,运筹学,计算机,信息论,控制论,网络理论以及经济管理等许多领域.当前图论研究的热门专题有:图染色问题,图的Hamilton性,连通度,因子理论,平面图问题,有向图问题,复杂网络等.本文主要研究Schrijver图SG(2k+2,k)的几种染色以及hamilton性和无相邻3?圈的平面图G的线性染色. 图G的一个k-点染色是用k种颜色对图G的顶点进行染色,使得相邻的顶点都染不同的颜色.图G的点色数是图G的k-点染色中的最小的k值,记为χ(G).G的一个k-边染色是用k种颜色对图G的边进行染色,使得任意相邻的边都染不同的颜色.图G的边色数是图G的k-边染色中的最小的k值,记为χ′(G).图G的一个k-全染色是用k种颜色对图G的顶点和边进行染色,使得任意相邻的边,相邻的顶点和相关联的顶点和边都染不同的颜色.图G的全色数是图G的k-全染色中的最小的k值,记为χ′′(G). Behzad和Vizing分别独立地提出了著名的全染色猜想TCC: ?+1≤χ′′(G)≤?+2, 其中?表示图G的最大度. 通过图G的每个顶点的路称为hamilton路,通过图G的每个顶点的圈称为hamilton圈,具有hamilton圈的图G称为hamilton图. 图G的正常点染色如果满足任意两种颜色的点集导出的子图是一些点不交的路的并称之为图G的线性染色,线性染色数是图G的所有的线性染色中最小的颜色数目,记为:lc(G). 本文主要得到了下面的结果: 1.研究了Schrijver图SG(2k+2,k)的全染色问题,得到了:χ′′(SG(2k+2,k))=?+1=k+3,其中k≥2. 2.研究了Schrijver图SG(2k+2,k)的边染色问题,得到了:χ′(SG(2k+2,k))=k+2=?,k≥2. 3.Schrijver图SG(2k+2,k)具有hamilton性. 4.研究了图SG(2k+2,k)的线性染色问题,得到了:此处为公式省略,?表示图G的最大度. 5.如果平面图G无相邻3?圈,那么: lc(G)≤?+13,其中?表示图G的最大度. 收起