非退化边着色图的刻画、正常连通性和正常着色圈

Properly colored cycles (or PC cycles for short) and related structures in edge-colored graphs have important applications in molecular biology, social science, wireless communication networks and the construction of fault-tolerant networks, and are closely related to directed cycles in digraphs. For each digraph, there exists an edge-colored graph of the same order such that directed cycles in the digraph and PC cycles in the edge-colored graph have a one-to-one corresponding relationship. But the other way may not hold. Based on this point, digraphs can be regarded as degenerate edge-colored graphs. Study suggests that edge-colored graphs containing a degenerate edge-colored subgraph trend to be weak on the proper connectivity or the existence of certain PC cycles. In order to obtain more essential structural properties of edge-colored graphs other than those of digraphs, through this project, we will mainly focus on the so called non-degenerate edge-colored graphs. Properties of non-degenerate edge-colored graphs will be obtained by structural characterizations and the study of the proper walk/trail/path connectivity, color connectivity and cyclic connectivity. Based on the possibly obtained properties, we will study the existence of long PC cycles. This project expects to reacquaint the structrural properties of edge-colored graphs and find new research methods by studying non-degenerate edge-colored graphs, and also expects to make breakthroughs in solving several conjectures on the existence of PC Hamilton cycles.

边着色图中的正常着色圈及相关结构在分子生物学、社会科学、无线电网络通讯和容错网络构建等方面有着重要应用，同时与有向图中的有向圈关系密切。给定一个有向图，可构造一个顶点数相同的边着色图，使得该有向图中的有向圈与边着色图中的正常着色圈一一对应，但反之不一定成立，因此可将有向图看作是一类退化的边着色图。研究发现，退化的边着色图作为子图常常妨碍着母图的正常连通性和正常着色圈的存在。为探求边着色图有别于有向图的结构特征，本项目将重点研究非退化边着色图。具体地，本项目将刻画极小非退化边着色图的结构，研究非退化边着色图的正常途径/迹/路连通性、色连通性和圈连通性，并在此基础上研究正常着色长圈的存在性问题。本项目期望通过非退化边着色图的研究重新认识边着色图的结构性质并获得新的研究方法，同时期望在解决几个关于正常着色哈密尔顿圈的存在性猜想上取得突破性进展。

研究发现，与正常着色闭途径/闭迹/圈相关的定理和猜想所对应的极图常常显示出有向图（退化）特征。本项目主要研究非退化边着色图的刻画、正常着色连通性和正常着色圈。得到了一系列研究成果：从正常着色途径的角度给出了边着色图一个分类刻画定理，并证明了存在多项式时间判断边着色图所属类别；运用该分类定理完全刻画了不含单色三角形的边着色完全图的哈密尔顿性质，作为推论证明了图结构方面的Bollobás-Erdős猜想以及算法复杂性方面的Gutin-Kim猜想在禁止单色三角形条件下是正确的；从正常着色连通的角度我们给出了边着色图中存在正常着色圈的一个充分条件，作为推论得到了不含正常着色圈的边着色图结构刻画定理（Yeo定理，JCTB，1997）；将有向图中的Bermond-Thomasson猜想推广到了边着色完全图中，提出了相应的猜想，并刻画了极小反例的可能结构，得到了边着色完全图存在两个顶点不交正常着色圈的最大单色度条件，阐述了多部竞赛图与边着色完全图之间的关系；完全刻画了边着色完全图不含正常着色偶圈的着色结构以及不含正常着色奇圈的着色结构；给出了正常着色哈密尔顿路存在性的等价刻画定理（Bang-Jensen-Gutin 猜想）一个简短新证明。在本项目的支持下，一共在国际组合数学权威期刊发表学术论文5篇。