图的标号及相关问题研究

项目名称： 图的标号及相关问题研究

项目编号： No.11271334

项目类型： 面上项目

立项/批准年度： 2013

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

项目作者： 卜月华

作者单位： 浙江师范大学

项目金额： 65万元

中文摘要： 图的染色、标号及其应用一直是图论研究的重要内容之一，其研究富有挑战性，在网络优化、网络频率分配、算法设计和大规模集成电路设计等方面有重要应用。本项目主要研究图的染色理论、标号理论及图论在其它学科中的应用等问题。应用权转移技术和多项式理论研究在平均度或短圈限定条件下平面图的结构性质，从而探讨这些图类的3-可染（可选）问题及形如(m,d)*-（列表）染色、BB-（列表）染色、 L(p,q)-标号、对局标号等，以解决或部分解决Wegner关于平面图的L(1,1)-猜想和Steinberg 关于3-染色猜想为主攻目标；用概率方法及矩阵理论构造若干特殊图以确定相应的色数；探讨若干染色的算法复杂性问题。本项目所研究的问题一部分是国际著名学者提出的一些问题， 一部分问题是我们首次提出的，内容涉及到图论、组合优化、算法复杂性等领域。

中文关键词： 平面图；染色；标号；谱半径；指数

英文摘要： Graph coloring, labeling and their applications are important research topics in graph theory. There are many challenging problems and has wide applications to network optimization, channel assignment, algorithm design and VLSI. This project studies graph coloring and labeling and their applications. Using discharging method and polynomial method, we shall analyse the structure of planar graph with forbidden cycle lengths and graphs of bounded maximum average degree, and study colorability and choosability of these graphs. We also study other graph coloring and labeling problems, including (m,d)*-coloring, BB-coloring, BB-list coloring, L(p,q)-labeling and game labeling of graphs. We aim to solve or partially solve Wegner's conjecture concerning L(1,1)-labeling of planar graphs, and Steinberg's conjecture concerning 3-colorability of planar graphs with forbidden short cycles. We use probabilistic method and polynomial method to study graphs with special properties and with given coloring and labeling parameters. We shall investigate the complexity of some coloring problems. Some of the problems in this proposal are raised by well-known mathematicians and some problems are raised by ourselves. The contents of these problems involve graph theory, combinatorial optimization and algorithmic complexity.

英文关键词： planar graph；coloring；labelling；spectral radius；index