Tashkinov树的结构性质及其在图的边染色问题中的应用

Edge coloring problem is one of the most significant research areas in graph theory. The research in graph edge coloring problem is aimed to determine the chromatic index of a given graph. In this project, firstly, we seek the structures and properties of Tashkinov tree. Then we investigate the structures and properties of △-critical graphs using the above properties of Tashkinov trees. Furthermore, we determine the chromatic indices of some special classes of graphs. Finally, we generalize the Tashkinov tree and use it into some other edge coloring problems of graphs. The main problems we focus on are as follows: give a generalization of Vizing’s adjacency lemma, prove that Vizing’s 2-factor conjecture is true for some △-critical graphs under the constraint conditions of toughness and maximum degree, planar and 1-planar graphs are class one under the conditions of maximum degree, some special classes of graphs satisfy the corresponding conjectures of some constraint edge colorings. The main techniques will be used are combinatorial methods, algebraic methods and probabilistic methods, etc. The results of this project can be used into other problems in graph theory such as graph decomposition, matching theory and related problems. Besides, it can be the foundation of applications of the above problems into algorithms and complex networks.

图的边染色问题是图论研究中非常重要的一个研究方向。对图的边染色问题的研究，旨在确定图的边色数。在本项目中，我们首先研究Tashkinov树的结构性质；接着将这些性质应用到△-临界图中，研究△-临界图的结构性质，进一步确定一些特殊图类的边色数；最后，我们将Tashkinov树进行推广，应用至图的其他一些边染色问题的研究中。本项目拟解决的主要问题包括：推广Vizing邻接引理，证明Vizing 2-因子猜想对一些在韧度及最大度条件限制下的△-临界图是成立的，平面图及1-平面图在最大度条件限制下是第一类的，一些特殊图类满足一些有限制条件的边染色的相应猜想等。项目研究主要用到的方法包括组合方法、代数方法及概率方法等。本项目的研究成果将为图论中的其他一些问题如图分解、匹配相关的问题等提供研究思路，也为这些问题在算法及复杂网络等方向的应用提供理论依据。

图的染色问题及结构性质是图论研究中的热点问题，在分配问题、信号处理等研究中有着重要的作用。本项目中，项目组研究了图的边染色及与图的结构性质相关的一些问题，主要内容包括证得最大度至少为7且不含K5-子式的图的边色数为它的最大度；至少3条边的毛毛虫树是乘积反魔幻的；对虾树存在反魔幻定向；不含禁止对的连通图中所有最长路的交非空；至少3个点、7-坚韧的且不含(P3∪2P1)的图中存在Hamilton圈；最小度至少为3且不含P8的图满足Erdős–Gyárfás猜想。这些结果推进了相关问题的研究进展，具有一定的理论意义。自项目立项以来，项目组在图论领域的专业期刊上发表学术论文8篇。