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

项目名称： 图的几类(g,f)-染色及其算法研究

项目编号： No.10901097

项目类型： 青年科学基金项目

立项/批准年度： 2010

项目学科： 金属学与金属工艺

项目作者： 张霞

作者单位： 山东师范大学

项目金额： 13万元

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

中文关键词： 图；(g;f)-染色；f-染色；g-边覆盖染色；均匀边染色

英文摘要：

英文关键词： graph；(g;f)-coloring；f-coloring；g-edge covering coloring；equitable edge-coloring