图着色在图论发展中的作用与影响

Graph theory is an important branch of morden mathematics and is of wide application. As a growing point of the discipline, graph coloring profoundly affects the trend of graph theory. By means of comparative and comprehensive study of interdiscipline and conceptual analysis, starting with the four color problem and according to different ways of mathematicians' trying to solve it, this project plans to give a systematic research on the effect of graph coloring on the evolution of graph theory from the following four aspects. Firstly, the origins and developments of graph coloring, graph polynomials, graph factors and factorization, matching theory, graph minor theory and perfect graph theory are researched. Secondly, the background and evolution of some new concepts derived from the old ones is elaborated，including perfect graph, graph minor and matroid, etc. Thirdly, there are some important matematicians,including W.T. Tutte, C. Berge, P. Seymour, etc, whose contributions to graph theory are reviewed. Finally, from the point of view of interdiscipline, such as algebraic graph theory, topological graph theory and matorid theory, the effect of graph coloring on the development of graph theory are analyzed in depth. The results are not only of great academic significance，but also generally use for research on graph theory and even other mathematics for reference.

图论是一门应用广泛的重要数学分支。图着色是图论学科的生长点，深刻影响着图论的发展方向。本项目拟以四色问题为切入点，以数学家攻克它的各种尝试为线索，以问题为导向，采用学科交叉的综合比较研究和概念分析方法，从以下四个方面系统研究图着色在图论发展过程中的作用与影响：（1）研究图着色、图多项式、图因子及其分解理论、匹配理论、缩图理论以及完美图等理论的历史渊源与发展脉络；（2）阐述由老概念派生的一些新概念的产生背景与发展演化，包括完美图、缩图、拟阵等；（3）评述W.T.Tutte, C.Berge和P.Seymour等重要数学家对图论的贡献；（4）从代数图论、拓扑图论、拟阵论等交叉学科的角度深入分析图着色在图论发展中的作用与影响。研究成果具有重要的理论价值，对现代图论乃至数学研究具有普遍借鉴意义。

图论近年来取得若干突破性成就，都是图着色方面的进展，且当今遇到的瓶颈问题Hadwiger猜想也是四着色问题的推广。图着色是图论学科的生长点，深刻影响着图论的发展方向。本项目本着严谨的科学态度、与时俱进的科研视角，重点放在：（1）图着色与图多项式理论、匹配理论、图因子及其分解理论、缩图结构理论以及完美图等理论的历史渊源及发展脉络。我们在追踪最新文献资料的基础上，深入研究了从色多项式到色图论、从匹配多项式到匹配理论的发展演化；对比研究了早期数学家如J. Petersen， D. König， K. Menger，P.Hall以及W.T.Tutte在图因子及其分解理论上的工作；系统研究了缩图结构理论的发展脉络，认真梳理了完美图定理从猜想到获证的历史，指出了强完美图定理与Hadwiger猜想之间的历史渊源关系；（2）核心概念研究，包括完美图、缩图、拟阵等的历史。我们肯定了C.Berge在完美图概念及其理论上的奠基贡献；研究认为缩图是对K. Kuratowski平面图定理推广的结果；最后从理论上分析了拟阵思想的三个主要来源——代数、几何与图论。（3）评述了W.T.Tutte，C. Berge以及P. Seymour等图论专家的传记及其对图论的贡献。（4）研究了代数图论及拟阵论等交叉学科的产生与发展，揭示了交叉应用是图论发展的内在规律。