边着色图中正常着色的欧拉环游和哈密尔顿圈

Properly colored Eulerian circuits and Hamiltonian cycles in edge colored graphs have many important applications in molecular biology, transportation and communication, sociology, VLSI and conflict analysis and other fields, and close relations with directed graph theory, matching theory and algorithm analysis and design. This project mainly concerns with the existence and properties of properly colored Eulerian circuits and Hamiltonian cycles in edge colored graphs. For properly colored Eulerian circuits, we will mainly study the problem of counting properly colored Eulerian circuits and the existence of properly colored spanning Eulerian subgraphs and Eulerian circuits. For properly colored Hamiltonian cycles, we mainly study the color number condition, the minimum color degree condition, the maximum monochromatic degree condition and the minimum monochromatic color degree condition for the existence of properly colored Hamiltonian and long cycles. We will use structural analysis, algebraic, probabilistic and algorithmic methods, apply the regularity lemma, the local lemma and the Combinatorial Nullstellensatz to solve some existing problems and conjectures on the existence of properly colored Eulerian circuits and Hamiltonian cycles in this field and introduce some new problems in the study of properly colored Eulerian circuits and Hamiltonian cycles, which will be the counterparts of some research problems in the study of Eulerian circuits and Hamiltonian cycles in uncolored graphs.

边着色图中正常着色的欧拉环游和哈密尔顿圈在分子生物学、交通与通讯、社会科学、大规模集成电路设计和冲突分析等诸多领域都有着非常重要的应用，同时又与有向图理论、匹配理论和算法理论有着密切的联系。本项目主要围绕正常着色的欧拉环游和哈密尔顿圈以及相关结构的存在性与性质开展研究工作。对于正常着色的欧拉环游，将主要研究正常着色欧拉环游的计数问题和正常着色生成欧拉子图和欧拉环游的存在性问题。对于正常着色的哈密尔顿圈，将主要研究存在正常着色的哈密尔顿圈和长圈的颜色数条件、最小色度条件、最大单色度条件和最小单色度条件。本项目将综合运用结构分析、代数、概率和算法理论与方法，以正则性引理、局部引理和组合零点定理为工具，期望在解决本领域一些已有的重要问题和猜想上取得突破性进展，并在正常着色欧拉环游和哈密尔顿圈的研究中引入新的研究问题，把传统的关于一般非着色图中欧拉环游和哈密尔顿圈的一些研究问题扩展到边着色图中。

边着色图中正常着色子图与有向图理论、匹配理论和算法理论存在着非常密切的联系，同时在分子生物学、交通与通讯和社会科学等诸多领域都具有重要的应用。本项目主要围绕边着色图中正常着色欧拉环游和哈密尔顿圈的存在性问题开展研究工作，取得的主要成果包括：得到了具有广义转移系统的欧拉图和欧拉有向图中存在相容欧拉环游的Ore-型充分条件，进一步引入了弱广义转移系统，给出了具有弱广义转移系统的欧拉图中存在相容定向欧拉环游的Ore-型充分条件；作为正常着色哈密尔顿圈存在性的推广，得到了边着色完全图和等部完全多部图中存在经过每个顶点恰好k次的相容生成回路的充分条件以及满足某些度条件和禁用导出子图条件下边着色图中存在经过每个顶点至少指定次数的相容生成回路的充分条件；证明了判定边着色连通图是否存在相容生成回路问题是NP-完备的，并在满足特定条件的边着色完全图中构造了寻找相容生成回路的多项式时间算法；给出了边着色图中存在正常着色圈的最小色度条件以及边着色完全图中包含正常着色三角形的最小色度条件，同时给出了边着色完全二部图中包含经过给定顶点和给定边的正常着色四圈的最小色度和最大单色度条件以及边着色完全图中存在顶点不交长度不同的正常着色圈和通过指定顶点或边的正常着色圈的充分条件；给出了边着色完全图中正常着色圈扩展定理，进一步证明了边着色完全图中每个顶点被包含在长度至少为最小色度的正常着色圈中；刻画了边着色完全图中不包含正常着色偶圈或奇圈的结构以及在边数与颜色数之和较大的条件下不包含彩虹三角形的着色图结构，同时给出了存在彩虹圈的条件以及存在指定数目的顶点不交彩虹圈的充分条件；借助闭包的方法，对Yeo的关于边着色图中正常着色圈的存在性定理给出一种新证明；得到了弧着色完全有向图和强连通竞赛图中包含彩虹三角形的颜色数条件。这些成果丰富了关于边着色图中正常着色子图存在性的研究。