图的一个强染色问题 |
| |
引用本文: | 康殷殷.图的一个强染色问题[J].漳州师院学报,2000,13(2):31-34. |
| |
作者姓名: | 康殷殷 |
| |
摘 要: | 设G(V,E)是一个图,△(G)为图GK 顶点的最大度,图G的一个K-染色f,若使得任意的两个距离小于等于2的顶点u,v满足f(u)≠f(v),则称f是G的k-强染色,并称Xs(G)=min{k:存在G的一个k-强染色}为强色数,对任意一个图G,是否存在常数C,使得Xs(G)≤C△(G)?该问题是在99全国图论研讨会上提出来的,本文证明了对任意的常数C,都存在偶图G,使Xs(G)≤C△(G)。
|
关 键 词: | 强染色数 偶图 图 点染色 边染色 正常染色 |
本文献已被 维普 等数据库收录! |
|