非负特征图的线性染色 |
| |
引用本文: | 王维凡,李超.非负特征图的线性染色[J].中国科学A辑,2008,38(12):1321-1334. |
| |
作者姓名: | 王维凡 李超 |
| |
作者单位: | 浙江师范大学数学系, 金华 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)\ge\Delta$且$g(G)\ge g$,则lc$(G)=\lceil \frac {\Delta(G)}2\rceil+1$.
|
关 键 词: | 线性染色 非负特征图 围长 最大度 |
收稿时间: | 2008-01-28 |
修稿时间: | 2008-07-03 |
本文献已被 CNKI 等数据库收录! |
| 点击此处可从《中国科学A辑》浏览原始摘要信息 |
| 点击此处可从《中国科学A辑》下载免费的PDF全文 |
|