图的控制染色和完全分配染色

Coloring and domination are two key issues in graph theory, which have positive significance in theoretical and application aspects. Since both problems are in close relationship with graph structure, it is an interesting idea to put forward new restricted coloring problems combining these two issues. Dominator coloring is a young branch in graph coloring field, while thoroughly distributed coloring is a new expatiation of total domatic partition problem by coloring terminology. The research on these two restricted coloring problems is useful to further explore the inner relationship between coloring and domination. Because the two coloring problems belong to NP-hard problem in general graphs, this project focuses on the related parameters of some special classes of graphs as follows: (1)We will investigate the dominator colorings on various kinds of product graphs of paths, cycles and complete graphs, determine the dominator chromatic numbers of some product graphs with small order, and reveal the relationship between dominator chromatic number and other graph parameters on these graphs.(2)We will consider the thoroughly distributed coloring on product graphs of paths and cycles, compute the thoroughly distributed chromatic numberof some product graphs with small order, and provide foundation for the total {k}-domatic problem.(3)We will also study the thoroughly distributed coloring on Halin graphs and snarks graphs, and characterize the classification of some cubic graphs based on the thoroughly distributed chromatic number.

图的染色与控制集问题是图论中两大核心问题，在理论和应用方面均有其积极意义。由于这两类问题都与图结构有密切联系，所以将它们有机融合提出新的限制染色问题是一个非常有趣的研究课题。图的控制染色是图染色领域的一个年轻分支，而图的完全分配染色是从染色的角度重新诠释全控制集划分问题，研究的顺利开展有助于进一步揭示染色与控制集理论的内在联系。这两类染色问题在一般图上都属于NP-困难问题，因此本项目将探索一些特殊图类的相关参数，主要包括（1）研究路、圈、完全图的多种乘积图的控制染色，确定阶数较少的乘积图的控制色数，揭示这些图的控制色数与图其它参数间的关系；（2）研究路、圈乘积图的完全分配染色，确定阶数较少的乘积图的完全分配色数，为这些图上的全{k}-控制划分问题提供基础；（3）研究三正则Halin图、snarks图的完全控制染色，刻画某些三正则图类基于完全控制色数的分类。

图的染色与控制集问题是图论的两大核心问题，将这两类问题有机结合，提出新的限制染色是一个新兴课题。本项目着重研究图的控制染色和完全分配染色，由于上述两类染色问题在一般图上都是NP-困难的，本项目重点研究了Cartesian乘积图、正则图等特殊图类的限制染色参数，讨论其取值范围或精确表达式。. 在控制染色方面，结合最小控制集的特点，我们获得了Cartesian乘积图P3□Pn,P3□Cn(n≡0mod4),Km□Kn的控制色数的精确表达式，以及P3□Cn(n≡3mod4)的控制色数的一个紧的上界；确定了循环图Cn(1,2)的控制色数和全控制色数的精确值。. 在完全分配染色方面，通过分解三正则图snark的结构，完全确定了Flower snark,Goldberg snark, Loupekhine snark以及Blanusa snark的完全分配色数；给出三正则Halin图完全分配色数小于等于2的一个充分条件。. 此外，本项目还研究了一些相关的问题，建立了外1-平面图邻点可区别全色数的一个上界，并给出达到上界的图的刻画；考虑了路、圈各种Carstesian乘积图的半全控制数以及图的半全控制剖分数的性质。