首页 | 本学科首页   官方微博 | 高级检索  
     

平面图线性色数的一个上界
引用本文:王侃. 平面图线性色数的一个上界[J]. 数学研究, 2011, 44(4): 399-410
作者姓名:王侃
作者单位:浙江师范大学数理与信息工程学院,浙江金华,321004
基金项目:基金项目:国家自然科学基金资助项目,浙江省自然科学基金重点项目,浙江省教育厅科研基金项目
摘    要:如果图G的一个正常染色满足染任意两种颜色的顶点集合导出的子图是一些点不交的路的并,则称这个正常染色为图G的线性染色.图G的线性色数用lc(G)表示,是指G的所有线性染色中所用的最少颜色的个数.证明了:若G是一个最大度△(G)≠5,6的平面图,则lc(G)≤2△(G).

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

An Upper Bound of Linear Chromatic Number of Planar Graphs
Wang Kan. An Upper Bound of Linear Chromatic Number of Planar Graphs[J]. Journal of Mathematical Study, 2011, 44(4): 399-410
Authors:Wang Kan
Affiliation:Wang Kan (College of Mathematics,Physics and Information Engineering,Zhejiang Normal University,Jinhua Zhejiang 321004)
Abstract: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) .
Keywords:Planar graph  Linear coloring  Maximum degree
本文献已被 CNKI 维普 万方数据 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号