图的调和染色及相关边划分问题研究

Graph coloring theory and edge partition problem are the core research contents of graph theory. It has important applications in optimization theory, task scheduling, and computer networks. Based on current results, the project study the following several aspects: (a) harmonious coloring problem in planar graph, and harmonious coloring of speical graph which given the bound maximum degree or girth; (b) study the harmonious coloring of graphs with special structures, and the combination of harmonious coloring with other coloring methods (such as: equitable colored, fractional coloring, etc.). Put forward some new concepts, thus opening up new research areas; (c) study the adjacent vertex distinguishing coloring problem for some speical planar graphs; (d) research the labelling problem of special structure graphs; (e) application-oriented research on how to reconcile the mathematical results on harmonious coloring, adjacent vertex distinguishing coloring, graph labelling applied to other disciplines such as computer science. Currently, research on harmonious coloring is still stuck on some special graphs, and only obtained small related results. There exist many open problem in edge partition. This study will greatly enrich the research content of harmonious coloring and edge partition.

图的染色理论和边划分问题是图论核心研究内容，在优化理论、任务调度和分配理论、计算机网络等多个方面都有重要的应用。本项目在现有理论的基础上，研究以下几个方面的问题：（一）研究平面图的调和染色问题，以及给定最大度上界或者给定围长范围的基础上图调和染色问题；（二）研究若干结构的图的调和染色问题，同时研究调和着色与其他着色方法（比如：均匀着色、分数着色等）的结合，提出一些新的概念，从而开辟新的研究领域；(三)研究特殊结构平面图的邻点可区别染色问题；（四）研究特殊结构图形的图标号问题；（五）面向应用，研究调和染色、邻点可区别染色、图标号的数学结果如何应用到其他学科，比如计算机科学中。目前，对于调和染色的研究还停留在一些特殊图形上，得到的结果较少。边划分问题也有众多开问题尚未解决。本研究将极大地丰富调和染色和边划分的研究内容。

图的染色理论在图论及组合数学中占有极其重要的地位，在资源调度、网络设计、最优化等方面有重要的应用背景。调和染色作为顶点正常染色的一个特例，要求每条边的二元颜色集各不相同，其本质是对边集合性质的一个刻画，属于边划分问题。本项目主要研究讨论了调和染色以及其他边划分方法在化学指标计算以及分数因子存在性证明中的应用。项目组负责人以及其他成员执行研究计划，得到了以下三个方面的若干结果：1. 设计了对图进行局部调和染色的三类算法，分别为颜色交换算法、分支算法、代价算法，并对每类算法的优缺点进行分析和比较； 2. 利用边集合划分方法对一些在制药、材料、化学等领域有重要实际应用的化学物、材料或药物进行化学指数计算，同时得到双圈图的顶点带权维纳指数的极值以及对应极图； 3. 因子存在性问题是经典的边划分问题之一，我们研究了分数因子存在性的充分条件，得到了分数(g,f,n',m)-临界消去图的邻域并紧条件以及分数(g,f,n)-临界图的孤立韧度条件。项目组负责人以及项目组成员共计发表以该项目为第一资助项目的论文二十余篇，其中SCI检索17篇。本项目所取得的这些结果极大地丰富了调和染色和相关边划分问题的研究内容。