图的t-色k-染色数的研究

Since the class coloring, coloring has become an eternal topic in graph theory, such as list coloring, t-set coloring, distance coloring, rainbow coloring, etc.. Next, Gary Chartrand introduced t-tone-k coloring. A coloring is called a t-tone k-coloring of G if the coloring assigns to each vertex of G a set of t colors from set [k] such that vertices at distance d share fewer than d common colors. From the concept of t-tone-k coloring, it generalizes and combines the ideal of above colorings. According to the theories of t-tone-k coloring, this project will seek the boundaries of t- tone coloring especially for 2-tone k coloring and 3-tone k-coloring with algorithm and graph structure. The item study t-tone coloring number of random graphs with probabilistic method. According to the structure of dense random graphs and sparse random graphs, the work will try to find the upper bounds for them. Combining the structure of graphs and the theories of t-tone-k coloring, the objective will explore methods for three product operations between graphs and graphs, and search for the bounds of their coloring numbers. The parameters of graph are used to study the number of t-tone-k coloring, and the lower bounds of chromatic number are represented by the parameters. This project can expand the research field of graph coloring and apply to network, electric power, etc.

自从有了经典染色以来，染色成了图论中永恒的话题, 如列表染色，t-子集染色，距离染色，彩虹染色等。接着，Gary Chartrand引入了t-色k-染色的概念。一个图G的t-色k-染色是从k种颜色中选取t种颜色分配到G的每一个点，使得距离为d的点分享少于d种公共颜色。t-色k-染色组合和推广了以上染色的思想。本项目根据t-色k-染色和t-色染色数理论，用算法和图的结构等方法寻找t-色染色数的界，尤其是2-色染色数与3-色染色数的界。将概率的方法用于t-色k-染色数的研究，研究随机图的t-色染色数。根据图的结构找出稀疏随机图和稠密随机图的t-色k-染色数的上界。将图的结构与t-色染色理论结合，寻求图与图之间三种积运算的t-色染色数的方法，分别找出它们的t-色染色数的界。将图参数用于t-色k-染色数的研究，用参数来表示t-色染色数的下界。项目拓展了图染色的研究领域，可应用到网络与电力等方面。

图的染色问题是图理论研究的重要内容，经典染色概念得到了大量的推广，如列表染色，t-子集染色，距离染色等。Gary Chartrand 引进了t-色k-染色的概念，其理论意义在于从概念上推广了染色定义并为染色理论建立了一个应用上的理论框架。 -色色数是一种新的色标，可以较好地定量刻画网络稳定性所蕴含的不确定信息。将 -色染色图与t-色色数应用于染色领域具有重要的理论价值与实践意义。项目主要研究内容包括：(1)根据t-色k-染色和t-色染色数理论，用算法和图的结构等方法寻找t-色染色数的界，尤其是2-色染色数与3-色染色数的界；(2)将概率的方法用于t-色k-染色数的研究，研究随机图的t-色染色数。根据图的结构找出稀疏随机图和稠密随机图的t-色k-染色数的上界；(3)将图的结构与t-色染色理论结合，寻求图与图之间三种积运算的t-色染色数的方法，分别找出它们的t-色染色数的界；(4)将图参数用于t-色k-染色数的研究，用参数来表示t-色染色数的下界。取得的重要结果包括：(1) 令G=(V,E)是一图且t是一正整数。一个图G的t-色k-染色是从{1,2,…,k} 种颜色中选择且t种颜色分配到G 的每一个点，使得距离为d的点分享少于d种公共颜色。使图G具有t-色k-染色的最小k称为图G的t-色k-染色数，记为τt(G)。Cranston, Kim和Kinnersley证明对于每一个有△(G)≤3的图G，则τ2(G)≤8。我们考虑有△(G)≤3的3色染色图G，前人已有的最好结果是τ3(G)≤36，而我们证明了τ3(G)≤21。(2)对于t-色染色，Cranston et al.证明了对每一个整数t和每一个非空图G，有τt(G)≤(t2+t)△(G)。对于t-色染色的图G，我们证明τt(G)≤(t2+t)△(G)-2t, 改善了Cranston et al.的结果τt(G)≤(t2+t)△(G)。(3) 对于t-色染色，我们证明了对每一个整数t和每一个非空图G，有τt(G)≤(t2+t)△(G)-2t。对于t-色染色有△(G)≤3的图G， Cranston et al. 得到的最好的界是τt(G)≤3(t2+t)，而我们证明了τt(G)≤3t2，改善了Cranston et al.的界。研究成果对拓展图的染色领域具有积极的学术意义，能应用在网络、环境、能源、电力、军事等方面。