符号图的圆盘染色及k-染色

The class of signed graphs are a generalization of graphs. Recently, the study on signed graphs gain more and more attentions and become a hot topic. Though the theory on graph coloring is quite rich and plays a central role in discrete Mathematics, there are few results on the coloring of signed graphs. The applicant and Steffen proposed the concept of the circular coloring of signed graphs in 2015, which implies a new definition of the chromatic number of signed graphs. These two new concepts generalize ones of unsigned graphs. Later, The applicant and Steffen did some fundamental work on this topic. .This program is devoted to a further study and considers several major problems on the circular coloring and related r-coloring of signed graphs. These problems include the construction of signed graphs with certain properties, the circular spectrum of signed graphs, the establishment of Hajós-like theorem for the circular chromatic number of signed graphs, the signed version of the four color conjecture, and so on..The k-coloring of signed graphs is strongly related to some other kinds of coloring, such as DP-coloring of graphs, the coloring of generalized signed graphs and so on. Therefore, the study by this program will inspire the reseach on these related topics above.

符号图是图的一种推广。近些年来，对于符号图的研究变得十分热门。尽管图的染色理论目前已非常丰富，并在离散数学中占有中心地位。但人们对于符号图的染色问题却研究甚少。申请人和Steffen于2015年提出符号图的圆盘染色的概念，并由此引入符号图的k-染色的一种新的定义。这两个新的概念分别推广了图的圆盘染色和k-染色。随后，申请人和Steffen证明了一些基础性的结论。. 本项目将进一步研究符号图的圆盘染色及关联的k-染色，探讨几个重要问题，比如：几类特殊符号图的构造问题、符号图的圆盘色谱、符号图圆盘色数意义下的Hajós定理、以及符号图版的四色猜想等等。. 符号图的k-染色与其他一些染色问题密切相关，比如图的DP-染色、广义符号图的染色等等。因此，本项目进行的研究也将有助于对这些不同但互有联系的染色问题的探讨。

符号图是图的推广，本项目的研究计划要点是符号图的圆染色和k-染色及相关染色问题。本项目围绕该方向开展研究，共有4篇论文发表在《European Journal of Combinatorics》等学术期刊上。主要成果有：（1）证明了不含4-圈和6-圈的简单平面图都是(1,0,0)-可染的。该结论改进了数个已知结果，其证明有利于推进对Erdos关于Steinberg猜想的弱化问题以及它的符号图版本的研究。（2）围绕Petersen着色猜想，证明了每一个无桥3-正则图存在正常的5-边着色使得至少E(G)-\mu_3(G)条边为规范边。该结论较为逼近Petersen着色猜想，较大地改进已知结果。（3）研究奇偶符号图及相关的rna数，规范了图的rna数的定义。证明了Acharya和Kureethara关于rna数的猜想是正确的。证明了任意图的rna数的非平凡的统一的紧的上界，并求出所有取到该上界值的图。回答了Acharya，Kureethara和Zaslavsky提出的关于奇偶补图的rna数的一个公开问题。