图的点边赋权问题研究

Graph coloring theory has always been an important area in graph theory, and various graph parameters related to graph colorings are important parameters that reflect the structures of graphs. Due to different application background , many different kinds of coloring problems have been studied in the literature. As a variation and generalization of the vertex-edge coloring problems, we study two kinds total weighting of graphs: (k,k′)-total weighting choosability of graphs; neighbor sum distinguishing total coloring of graphs. For (k,k')-total weighting choosability of graphs, we focus on the famous (1,3)-choosable conjecture and (2,2)-choosable conjecture. We intend to gain insights on these two conjectures by verifying them for some families of sparse graphs, such as subcubic graphs, d-degenerate graphs. We would also like to study weaker version of these two conjectures that there is a constant k such that every graph with no-isolated edges is (1,k)-choosable and there is a constant k such that every graph is (k,2)-choosable. For neighbor sum distinguishing total coloring of graphs, we want to improve the upper bound for the neighbor sum distinguishing total coloring number of general graphs, and better bound for planar graphs. The two kinds of problems are different, but closely linked. Both can be transformed into the problems of polynomial assignments. We study such problems from local and global aspects via different tools like as polynomial method, discharging method and probabilistic method.

图的染色理论一直是图论研究中的重要课题，由染色导出的很多图参数是反映图的结构的重要参数。源于不同的应用背景，学者们研究了许多不同的染色问题。作为图的点边染色问题的变形和推广，本项目将研究图的两类点边赋权：图的(k,k′)-点边赋权可选，图的邻和可区别全染色。对于第一类问题，围绕著名的 (1,3)-可选猜想和 (2,2)-可选猜想展开，一方面验证一些稀疏图类是否满足这两个猜想，如subcubic图，d-退化图；另一方面也研究这两个猜想的较弱版本：存在k使得不含孤立边的图是(1,k)-可选的，存在k使得任意图都是(k,2)-可选的。对于第二类问题，改进一般图的邻和可区别全染色数的上界，并研究平面图的邻和可区别全染色数。这两类问题虽不同，但联系紧密，都可以转化为多项式的赋值问题。本项目将通过运用多项式方法、权转移方法与概率方法等工具从局部和整体来研究图的点边赋权问题。

图的染色理论一直是图论研究的重要课题。图的点边赋权问题是图的染色问题的变形和推广。本项目着重研究图的点边赋权问题及其相关图论问题，包括图的(k,k’)-可选问题、图的基于点的离心率的拓扑指标极值问题和图的两类控制数问题等。本项目围绕上述方向，针对提出的问题开展研究。主要结果有：用组合零点定理证明了对于任意不含孤立边的图G，若其最大平均度至多为p-1，则图G是(1,p)-可选的，其中p是素数。这一结果改进了前人的部分研究成果。通过提出一种不同以往而又通用的方法，得到了树、单圈图和双圈图等特殊图类的几类基于离心率的拓扑指标极值排序结果，并刻画了相应的极图。这些结果推广并优化了前人的拓扑指标极值图排序结果。研究了图的半全控制剖分数和Steiner控制数问题，证明了二部图的半全控制剖分数问题是NP-完全问题，并且得到了一些特殊图类的半全控制剖分数的上下界；提出了一个构造树的Steiner控制集的线性算法。本项目组共计发表相关学术论文5篇。本项目研究成果在一定程度上丰富了图论相关问题的研究内容。