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

非负特征图的线性染色
作者姓名:王维凡  李超
作者单位:浙江师范大学数学系, 金华 321004
基金项目:国家自然科学基金(批准号: 10771197)和浙江省自然科学基金(批准号: Y607467)资助项目
摘    要:如果图$G$的一个正常染色满足染任意两种颜色的顶点集合导出的子图是一些点不交的路的并,则称这个正常染色为图$G$ 的线性染色.图$G$的线性色数用lc$(G)$表示,是指$G$的所有线性染色中所用的最少颜色的个数. qquad 证明了: 对于每一个最大度为$Delta(G)$围长为$g(G)$的非负特征图$G$,若存在一个有序对$(Delta,g)in{(13,7),(9,8),(7,9),(5,10), (3,13)}$, 使得$G$满足$Delta(G)geDelta$且$g(G)ge g$,则lc$(G)=lceil frac {Delta(G)}2rceil+1$.

关 键 词:线性染色  非负特征图  围长  最大度
收稿时间:2008-01-28
修稿时间:2008-07-03
本文献已被 CNKI 等数据库收录!
点击此处可从《中国科学A辑》浏览原始摘要信息
点击此处可从《中国科学A辑》下载全文
设为首页 | 免责声明 | 关于勤云 | 加入收藏

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