The Origin And Development Of Graph Polynomials Theory

As an important branch of mathematics, graph theory has a long history up to now. Inrecent years, with the concepts and methods of other disciplines of mutual fusion and mutualinfiltration, algebraic graph theory, geometric graph theory, probability graph theory and otherbranches of graph theory emerge in the development process of graph theory. Algebraic graphtheory is a theoretical branch that applys algebraic method to solve the problems of graphtheory. As a core part of algebraic graph theory, graph polynomials theory is the general termfor all kinds of algebraic invariants of graphs which mainly include chromatic polynomial,Tutte polynomial, characteristic polynomial, matching polynomial and F-polynomial and soon.This dissertation is built on studying a large number of original articles and relativehistorical research literatures. According to the chronological order and centering on theorigin and development of graph polynomials theory, the present paper selects several typicalgraph polynomials to study detailedly. From the perspective of historical development, thisarticle tries to analyze comprehensively and study systematically the historical process of theorigin and development of each graph polynomial through the literature analysis. The mainresults are the following four aspects:1. The dissertation describes the origin and development of the chromatic polynomial ofgraphs systematically. It analyzes how Birkhoff put forward the concept of chromaticpolynomial of maps, and how to extend it to general graphs by Whitney. This paper analyzesthe process That Tutte obtained the famous Tutte polynomial comprehensively and elaborateshis main ideas. By discussing Read raise the two new problem of the chromatic polynomials,the paper overviews the progress of the chromaticity of graphs briefly.2. The dissertation explores the origin and development of the characteristic polynomialof graphs deeply. In the process of trying to use the characteristic polynomials to classifygraphs, the thesis analyzes the origin of the same spectrum of graphs which is a new conceptas well as an equivalent relation. Consequently, starting from the characteristic polynomial ofgraphs, the article explores the historical origin and development of spectral theory of graphs.3. The dissertation elaborates the historical origin and development of matching theory of graphs. According to teasing the historical process That Petersen studyed1-factor andK nig studyed the matching of bipartite graphs, the article investigates the furtherdevelopment of matching theory of graphs. Matching polynomial is a new method of studyingmatching problems quantitatively. The thesis describes the process That Farrell obtained thematching polynomial of graphs meticulously.4. The dissertation analyzes the mention and the influence of the F-polynomial of graphscomprehensively. In addition to dissecting the thought process That Farrell obtained theF-polynomial deeply, the article also explores the widespread impact of F-polynomial ongraph theory.