图的谱特征和色性问题及其关系研究

项目名称： 图的谱特征和色性问题及其关系研究

项目编号： No.11461054

项目类型： 地区科学基金项目

立项/批准年度： 2015

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

项目作者： 王建锋

作者单位： 青海师范大学

项目金额： 38万元

中文摘要： 图的谱特征问题和图的色性问题分别是图谱理论和色多项式理论中的两个难题。Schwank、van Dam、Haemers和Bollobás等关于这两个问题提出了三个著名的猜想， 但至今仍无进展。本项目以这两个问题和三个猜想为核心展开研究，主要研究特殊图类、广义谱特征问题、色等价和色唯一图的构造、一般图和相关专题等五大方面。这两个难题的研究具有重要的理论意义和应用价值，尤其在算法复杂性理论方面。 项目有两方面的创新：一是新的研究内容：包括新的谱理论、推广Schwank的结论、伴随多项式的代数性质、双变量特征多项式和Bartholdi-zeta-函数以及二者之间的关系研究；二是新的研究方法：引入图的Bartholdi-zeta-函数、特征空间和特征向量研究图的谱特征问题；利用新发现的图多项式之间的关系研究图的色性问题。

中文关键词： 图的谱；特征值；谱特征；色性问题；图多项式

英文摘要： The Spectral Characterization Problem and Chromaticity Problem of graphs are the two of most difficult problems in the spectral graph theory and chromatic polynomial theory respectively. Schwank，van Dam，Haemers and Bollobás posed three famous conjectures about them, which haven't made much headway up to now. This funded project will focus on these two problems and three conjectures, and mainly investigate the special graphs, the generalized spectral characterization problem, the constructions of chromatically equivalent and unique graphs, general graphs and related topics. These two problems have important theoretical sense and applications, particllarly in the theory of algorithm complexity. There are two aspects of innovation: one is the novel research contents, including the new spectral graph theory, the generalizations of Schwank's result,the algebraic properties of adjoint polynomial, the characteristic polynomial on two variables, the Bartholdi-zeta-functions and their relations between these two problems. The other one is the novel research methods, containing the use of the Bartholdi-zeta-functions, eigenspace and eigenvector to study the Spectral Characterization Problem, and the new relations among the polynomials of graphs to study the Chromaticity Problem.

英文关键词： Specra of graphs;Eigenvalue;Spectral characterization;Chromaticity Problem;Polynomials of graphs