有约束条件的图染色问题研究

项目名称： 有约束条件的图染色问题研究

项目编号： No.11371328

项目类型： 面上项目

立项/批准年度： 2013

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

项目作者： 王维凡

作者单位： 浙江师范大学

项目金额： 62万元

中文摘要： 图的染色是图论研究的重要内容,在现代计算机科学、信息科学、管理科学等领域有着十分广泛的应用，一直得到国内外同行的极大关注。本项目从图的结构性质入手，研究图的各种约束染色问题，如无圈点染色、无圈边染色、线性染色、列表染色、邻点区别边染色、邻点区别全染色等。力争解决或部分解决Borodin等人提出的关于平面图是无圈5-可选的猜想；围绕Alon-Sudakov-Zaks猜想，对一般图改进已知无圈边色数的上界，找到新的图类满足该猜想。特别地，力争给出平面图的无圈边色数紧的上界，刻画有大围长的平面图的无圈边色数。研究图的邻点可区别边染色和全染色，改进一般图邻点可区别边色数和全色数的上界，并对最大度较大的平面图刻画这两个参数。此外，研究图的控制数、图的能量、一些著名网络图的路和圈的嵌入问题等，争取改进已有的结果。拟在四年内完成学术论文30余篇，其中20以上发表在SCI杂志上。

中文关键词： 图；无圈染色；点可区别染色；存活率；荫度

英文摘要： Graph coloring is an important branch of graph theory, which are of wide applications in computer science, information science, management science and other fields. This direction has attracted considerable attention in the latest decades. In this project

英文关键词： graph；acyclic coloring；vertex distinguishing coloring；surviving rate；arboricity