平面图线性色数的一个上界  

An Upper Bound of Linear Chromatic Number of Planar Graphs

作　　者：王侃[1] 

机构地区：[1]浙江师范大学数理与信息工程学院,浙江金华321004

出　　处：《数学研究》2011年第4期399-410,共12页Journal of Mathematical Study

基　　金：国家自然科学基金资助项目(11071223);浙江省自然科学基金重点项目(Z6090150);浙江省教育厅科研基金项目(Y201121311)

摘　　要：如果图G的一个正常染色满足染任意两种颜色的顶点集合导出的子图是一些点不交的路的并,则称这个正常染色为图G的线性染色.图G的线性色数用1c(G)表示,是指G的所有线性染色中所用的最少颜色的个数.证明了:若G是一个最大度△(G)≠5,6的平面图,则1c(G)≤2△(G).A linear coloring of a graph G is a proper vertex coloring, such that the graph induced by the vertices of any two color classes is the union of vertex-disjoint paths. The linear chromatic number lc（G） of the graph G is the smallest number of colors in a linear coloring of G. In this paper, we prove that every planar graph G with maximum degree △（G）≠5,6 has lc（G）≤2△（G） .

关 键 词：平面图 线性染色 最大度 

分 类 号：O157.5[理学—数学]