Hadwiger猜想的相关问题研究

Since the well-known Four-Color Conjecture was proposed in 1852, graph coloring and related topics have become a hot theme in graph theory and combinatorial theory. Graph coloring has found numerous applications in many other areas such as information networks, transportation optimization, social networks and molecular biology. In 1943, Hadwiger proposed a conjecture that contains the Four-Color Conjecture as a special case and is widely considered to be one of the deepest unsolved problems in graph theory. This project aims at exploring several important problems regarding Hadwiger conjecture. Specifically, we will investigate: 1. Hadwiger conjecture and perfect graphs; 2. proofs for Hadwiger conjecture on graphs including counterexamples to Hajós conjecture, graphs with independence number two and circulant graphs; 3. Hadwiger conjecture and inflation graphs; 4. computational complexity and algorithms for Hadwiger number problem. By attacking these problems, this research will substantially promote the development of Hadwiger conjecture theory and related subjects.

自从1852年著名的四色猜想被提出以来, 图染色及相关问题逐渐成为图论与组合研究的热点。这是因为图染色在很多学科领域如信息网络，交通优化，社交网络，分子生物学等都有广泛的应用。1943年，Hadwiger提出一个涵盖四色猜想为特殊情况的猜想，即，被广泛认为是当今图论中最深奥的未解问题之一的Hadwiger猜想。本项目将以Hadwiger猜想领域内的几类重要问题为研究目标。本项目瞄准以下四类问题：1. Hadwiger猜想与完美图；2. 证明Hadwiger猜想在Hajós猜想的反例图类、独立数为2的图和循环图上成立；3. Hadwiger猜想和膨胀图；4. Hadwiger数的计算复杂性和算法。力争在这几类问题上取得实质性突破。本项目的研究对推动Hadwiger猜想理论的发展和在相关领域的应用具有重要意义。

本项目主要围绕Hadwiger猜想领域内相关问题展开研究。主要内容有图的结构刻画分析，几类特殊图类上的Hadwiger猜想问题以及张量分析方面的研究。项目对三弧图、小独立数的一般图和对称图以及广义Petersen图的结构性质进行了深入研究。利用所得的图结构性质结果，证明了对于三弧图、几类具有小独立数的图类以及一类非本元对称图都是成立的。同时，鉴于张量分析在组合数学和大数据研究中的重要应用，项目也研究了弹性M-张量，矩形张量以及四阶张量的特征值与正定性问题，得到了弹性M-张量的最小M-特征值的下界以及几类张量正定性的充分和/或必要条件。研究成果共计形成12篇已发表论文。