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

项目名称： 图着色在图论发展中的作用与影响

项目编号： No.11201113

项目类型： 青年科学基金项目

立项/批准年度： 2013

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

项目作者： 王献芬

作者单位： 河北师范大学

项目金额： 22万元

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

中文关键词： 图着色；完美图；缩图；拟阵；

英文摘要： 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 gr

英文关键词： graph coloring；perfect graph；minor；matroid；