图的几类(g,f)-染色及其算法研究

本项目主要研究图的f-染色、g-边覆盖染色、均匀边染色等几类(g,f)-染色问题.它们是一般图的边染色和边覆盖染色的推广,在排序问题,计算机文件传输和网络设计中有重要的应用.该问题是计算机科学家首先提出的,有许多新问题和猜想没有解决.申请者和项目组成员已做过相关的研究并获得若干成果.申请者首先提出"关于f-染色的分类问题"、"f-临界图"等概念并对其研究，并首次应用f-染色的方法解决了图的均匀边染色中的一个猜想．本项目主要研究(g,f)-染色中的分类问题，图的f-染色和g-边覆盖染色的色数、色数的界,有关这两种边染色的临界图的性质、两种边染色的分数染色以及有关的算法.力求解决关于f-染色和临界图的两个猜想.同时,我们还研究同上述边染色关系密切的均匀边染色．把染色和因子分解两种方法结合起来进行研究，将得到一些新的理论和算法.

本项目主要研究图的f-染色、g-边覆盖染色、均匀边染色等几类(g,f)-染色问题.它们是图的边染色和边覆盖染色的推广,在时间表问题,计算机文件传输和网络设计中有重要的应用. 在本项目的资助下，项目组在上述问题上取得了一系列的重要成果，解决了两个相关的猜想,在国际权威学术期刊《J. Graph Theory》、《Ars Combinatoria》等发表了14篇SCI和2篇EI论文. 特别的，主持人张霞与刘桂真教授合作解决了A.J.W. Hilton 提出的关于图的均匀边染色问题的一个猜想，并且给出一个比其更强的结果，将图存在k色均匀边染色的充分条件由之前的“无k-核或k-核为孤立点集”直接推广到允许k-核出现圈的“k-可剥离”，此项工作具有突破性意义.