一个边着色定理 |
| |
引用本文: | 张忠辅.一个边着色定理[J].科学通报,1984,29(3):139-139. |
| |
作者姓名: | 张忠辅 |
| |
作者单位: | 兰州铁道学院,兰州铁道学院,中国科学院应用数学研究所 北京 |
| |
摘 要: | Berge曾给出一个边着色定理,下面为使用方便起见,我们不妨称它为B定理。著名的Vizing定理和另外一些边着色的结果都可以作为B定理的推论。我们叙述这个定理如下:B定理 设G是一个无环重图,a,b]_0是G的一条边,令G′=G—a,b]_0,若G′是可q-边着色的,且q≥d_G(a),q≥d_G(b);d_(G′)(x) m_(G′)(a,x)≤q,则G也可q-边着色。这里d_G(x)表示顶点x在图G中的次;m_(G′)(x,y)表示在图G′中以x和y为端点的边数;Γ_(G′)(x)表示顶点x在G′中的邻点集合。
|
收稿时间: | 1982-10-25 |
本文献已被 CNKI 等数据库收录! |
| 点击此处可从《科学通报》浏览原始摘要信息 |
| 点击此处可从《科学通报》下载免费的PDF全文 |
|