|
|||||
|
|
| 一类有向图的星边弧染色 | |
| 引用本文： | 刘信生,孙春虎.一类有向图的星边弧染色[J].西北师范大学学报,2011(6):12-16. |
| 作者姓名： | 刘信生 孙春虎 |
| 摘 要： | 提出了有向图的星边弧染色的概念,并定义了有向图D的星边弧色数,记为(→x)s′(D).运用Lovász局部引理证明了若有向图D=(V,A)的最大出度△+与最大入度A-满足线性关系△+=k△-(△(D)≥7,k＞0),则(→x)s′(D)≤16(√1+k2)/1+k△3/2]*,这里*]*表示上取整. |
| 关 键 词： | 有向图 星边弧染色 星边弧色数 概率方法 Lovász局部引理 |