图的(k,d)*-染色及相关问题的研究

Graph coloring theory has a centural position in graph theory and discrete mathematics. A variety of new definitions of the theory of graph coloring were introduced for their practical applications and theoretical value. In 1979, list coloring and choosability of graphs were introduced independently by Vizing, by Erdos,Rubin and Taylor. In 1985, the concept of defective coloring (also called improper coloring in some papers) was simultaneously introduced by Burr and Jacobson, Cowen, Cowen and Woodall, and Harary and Jones. Then the defnition of defective choosability of graphs was introduced by Skrekovski and by Eaton and Hull independently in 1999. There are so many excellent articles on graph coloring. All plane graphs are (4,0)*-colorable (by Four Color Theory), and all outerplanar graphs are (3,0)*-colorable and (2,2)*-colorable. It was also proved that all plane graphs are (3,2)*-colorable and (5,0)*-choosable. This project is trying to study some problems on (k,d)*-coloring, for example, the (3,1)*-coloring and the (3,1)*-choosability of plane graphs without some special small cycles. Another important interest of this project is the (k,d)*-coloring of some graphs embedded on certain sufaces, such as the (4,1)*-coloring and the (3,2)*-choosability of toroidal graphs. Simultaneously, the relationship between graph coloring and some other graph invariants will also be studied in this project.

图的染色是图论研究甚至离散数学中的一个重要研究方向，随着实际问题的需要，各种各样的图染色问题被广泛推广和深入研究。1979年，Vizing、Erdos等人引进的列表染色和可选性就是经典染色的一个重要推广,1985年,Burr、Cowen和Harary等人独立地引进了(k,d)*-不完全染色,之后此定义被推广到不完全列表染色。现在此领域已有许多深刻的结果，如平面图是(4,0)*-可染的(即四色定理)、(3,2)*-可染的、(5,0)*-可选的(此即著名的平面图的5-可选定理)；外可平面图是(3,0)*-可染的、(2,2)*-可染的等。本项目将致力于研究和(k,d)*-染色相关的许多问题，考虑各种不含小圈的平面图的(3,1)*-染色问题及推广后的(3,1)*-可选问题，还将考虑一些曲面图的(4,1)*-染色问题及(3,2)*-可选问题等。同时，本项目还将深入探讨染色问题与其他图参数之间的关系。

图的染色是图论中非常重要的分支。在图的染色中，常考虑某些特殊结构的存在性。给定图G和H，对完全图的边进行染色时，希望去寻找最小的顶点数，使其或有单色图G或有单色H。现从多角度对其进行推广探讨。第一，将染色推广。若或有单色图G，或有彩虹着色图Ｈ，会如何？第二，考虑完全二分图的边染色会如何？第三，考虑完全图边染色时，在寻找出现单色图G或者H的最小点数N 时，临界图 K_{N-1}有怎样的性质？若在临界图上加一个点让其邻于原图的k个顶点，此即增加一个k-扇，需要多大的k-扇来打破其临界状态？第四，若考虑一般图H和s-边染色呢？围绕这些问题，本项目展开了相应的研究。若要求或有单色图G，或有彩虹着色图H，当考虑边着色的对象为二分图K_{N,N}时，同样希望找到最小的N。在研究中，反过来考虑最大的色数k使得恰用k种颜色对图G进行边染色时，其每个H都不是彩虹着色的。利用此本项目讨论了一些特殊图类，如图G是二分图，H是星图，或G是偶圈，H是星图，或H是星图，G是偶圈，或G、H分别是星图和扫帚图等，都给出了相应的上下界。另一方面，K_{N-1}临界图上一定有某种边染色，使其既无单色G又无单色H。那么，在临界图基础上不断增加k-扇的过程中，何时能使其必重含单色图G或者H呢？此过程中所得到的最小k即星临界值。本项目讨论了一些图类的星临界值。当图G为n阶完全图、图H为mK_2时，或图G 为nK_4、图H为mK_3，或图G为F_n、图Ｈ为K_3，本项目确定了其最小星临界值。若将图推广到一般图H，将2-边染色推广到一般的s-边染色，也希望其中含单色的给定图G_i (i=1,…,s)。在此类问题的研究中，除了考虑图H的阶数最小外，也可考虑图H的最大度条件，希望其最大度最小。若诸G_i为将偶圈C_2n的每个点都吹大后所得图，或诸G_i为某些树类图时，本项目给出了相应H图的最大度条件上界。若颜色数为2，G_i为路图，给出了最大度条件值。上述研究都是基于一般图，如何将一般图的一些理论推广到超图中去，这个也是当前图论研究中的热点。本项目给出了3一致超图具有(2n+3)/9个边不交的完美匹配的1-度条件，并且，该条件是紧的。图的许多性质都用矩阵表示，对应到超图也可把矩阵推广到张量，我们给出了张量乘积的行列式计算公式，并对多个张量乘积给出推广，也讨论了张量行列式的一些基本性质。这些工作都具开创性的科学意义。