图的边染色与列表边染色

• 作 者: 陈永珠
• 机 构: 浙江师范大学
• 出 处: 浙江师范大学
• 发表日期: 2007年01期
• 关键词: 平面图 边色数 边选择数 最大度 边染色

图的染色理论是图论中最重要的分支之一，在无线通讯频道分配、舰队维护、任务分派、交通定向等诸多领域都有着广泛的应用。本文主要研究图的边染色与列表边染色。
在第二章中，给出第一类平面图的若干充分条件，证明下列两个结论:
(1)△(G)=6，且不含弦5-圈的平面图G是第一类；
(2)△(G)=5且不含相交三角形的平面图G是第一类。
在第三章中，从平面图推广到欧拉特征值非负的一般曲面上，从而改进了卜月华和王维凡在文献[4]中的结论，证明:对于△(G)=6，且χ(∑)≥0的图G满足下列条件之一，则G是第一类：
(1)不含相邻三角形；
(2)不含弦5-圈和弦6-圈。
在第四章中，研究了平面图G的列表边染色，并证明如下两个结论:
(1)若G是一个△(G)≠5，且不含弦5-圈的平面图，那么G是(△(G)+1)-边可选的。
(2)若平面图G满足下列条件之一，则G是(△(G)+1)-边可选的：
(a)不含弦4-圈和弦5-圈；
(b)不含弦5-圈和弦6-圈。