摘要: 用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=(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. 收起