图的圈k-覆盖及偶圈分解问题研究

The circuit cover of graphs is an important research area in graph theory. The project mainly investigates the circuit k-cover and even circuit decomposition of graphs, with emphasis on the following two topics: 1. Conjecture on the signed circuit 6-cover of signed graphs, aiming for proving that each circuit coverable signed graph has a signed circuit 6-cover; 2. Even circuit decomposition of the line graph of 2-connected cubic graphs, with hopes of proving that the line graph of any 2-connected cubic graph has an even circuit decomposition. The investigation will contribute to the study of signed circuit covers of signed graphs and even circuit decomposition of graphs, and furthermore, contribute to the research of circuit covers of graphs and related problems in graph theory.

图的圈覆盖问题是图论研究的重要课题。本项目主要研究图的圈k-覆盖问题和偶圈分解问题，拟研究的主要内容包括：1. 研究符号图的符号圈6-覆盖猜想，证明任意圈可覆盖的符号图存在符号圈6-覆盖； 2. 探讨2-连通三正则图的线图的偶圈分解猜想，争取证明任意2-连通三正则图的线图存在偶圈分解。本项目的开展将丰富符号图的符号圈覆盖问题和图的偶圈分解问题的研究成果，从而进一步促进图的圈覆盖及其相关问题的发展。

本项目研究了符号图的圈覆盖和染色问题。在符号图的圈覆盖方面，证明了圈6-覆盖猜想对符号欧拉图成立，即任意可覆盖符号欧拉图中存在由4个圈覆盖构成的圈6-覆盖，并证明猜想对于广义符号欧拉图成立, 进而得到广义符号欧拉图G的最短圈覆盖的长度的上界为3/2|E(G)|，推广了符号欧拉图圈覆盖的已知结果。对于负边个数的符号图的圈覆盖问题的探讨结果在进一步改进。在符号图的染色方面，主要研究符号图的圆环染色。在circular chromatic number of signed graph一文中，引进了符号图的圆环色数的概念，研究了该参数的基本性质，改进Narboni-Kardos关于存在不可4-染色符号平面图的结果，构造出圆环色数为14/3的简单符号平面图，得到了一些符号图内的圆环色数的最好上界，在三篇后续的论文中（均在投稿中），进一步发展了这些研究，证明对任意的介于2和14/3之间的有理数r，存在简单符号平面图其圆环色数等于r，得到了所有符号串并联图的可能的袁浩色数值。