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

项目名称： 图的(k,d)*-染色及相关问题的研究

项目编号： No.11201342

项目类型： 青年科学基金项目

立项/批准年度： 2013

项目学科： 数理科学和化学

项目作者： 张莉

作者单位： 同济大学

项目金额： 22万元

中文摘要： 图的染色是图论研究甚至离散数学中的一个重要研究方向，随着实际问题的需要，各种各样的图染色问题被广泛推广和深入研究。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)*-可选问题等。同时，本项目还将深入探讨染色问题与其他图参数之间的关系。

中文关键词： 边染色；彩虹染色；星临界；张量；超图

英文摘要： 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 betwe

英文关键词： edge-coloring；rainbow-coloring；star-critical；tensor；hypergraph