摘要: 用G=(V,E)表示一个有限简单无向图,顶点集为V,边集为E.如果G的一个映射φ:V→{1,2,...,k)满足当uv∈E,有φ(u)≠φ(v),则称φ是G的一个正常k-染色.若G有一个正常k-染色,则称G是k-可染的.图G的线性染色是G的一个正常染色使得染任意两种颜色的顶点集合导出子图... 展开 用G=(V,E)表示一个有限简单无向图,顶点集为V,边集为E.如果G的一个映射φ:V→{1,2,...,k)满足当uv∈E,有φ(u)≠φ(v),则称φ是G的一个正常k-染色.若G有一个正常k-染色,则称G是k-可染的.图G的线性染色是G的一个正常染色使得染任意两种颜色的顶点集合导出子图是一些点不交的路的并.图G的所有线性染色中所用的最少颜色的个数称为G的线性色数,用lc(G)表示. 1973年,Grünbaum[1]提出了无圈染色的概念,图G的一个使得染任意两种颜色的顶点集合导出子图是一个森林的正常染色称为G的一个无圈染色.1998年,Yuster[2]提出了图的线性染色概念,并证明了任意图G都有lc(G)=O(△3/2),同时构造出了一类图满足lc(G)=Ω(△3/2).事实上,图的线性染色是无圈染色的一种特殊情形. 本学位论文改进和扩充了关于平面图线性染色的一些已有结果.设△和g(G)分别为图G的最大度和围长.本文的主要结果如下: (1)对一个平面图G,若△≤6,则lc(G)≤2△+1；若△≥7,则lc(G)≤2△； (2)若G是一个g(G)≥6的平面图,则lc(G)≤「△/2()+3；且当△(){4,5,...,12)时,有Ic(G)≤「△/2()+2； (3)若G是一个g(G)≥5的平面图,则lc(G)≤「△/2()+5；且当△(){7,8,...,14)时,有lc(G)≤「△/2()+4； (4)若G是g(G)≥4的平面图,则lc(G)≤「3△/2()+2. 收起