第二类边临界图的某些结构性质研究

A simple graph, of which the edge chromatic number is the sum of maximum degree and 1, is of class two; A critical graph is a graph such that its edge chromatic number is larger than that of any proper subgraph. A critical graph of class two is usually called ∆-critical graph. This project, that focuses on the conjecture proposed by Vizing on the existence of 2-factor of ∆-critical graphs, studies the existence of 2-factor of 3-critical graphs, the existence of Eulerian factor of ∆-critical graphs with maximum degree at least 4, and the determination of Hamiltonicity of ∆-critical graphs by maximum degree, respectively; This project, that also centers on Vizing’s conjecture on the independence number of ∆-critical graphs, researches on the upper bound of the independence number of ∆-critical graphs with minimum degree ∆-1, called almost regular ∆-critical graphs for brevity, by which we can obtain the upper bound of the independence number of general ∆-critical graphs.. This project combines the coloring problem with factor and independence number problems in the structure of graph theory, respectively, tries to reveal the structure characteristics of ∆-critical graphs, enriches the results of ∆-critical graphs, and applies some theoretical bases to a lot of practical applications.

边色数等于最大度数与1之和的简单图称为第二类图；边临界图为满足其任意真子图的边色数均小于该图边色数的图；第二类边临界图通常称为∆-临界图。本项目围绕Vizing提出的∆-临界图的2-因子猜想，拟分别对3-临界图的2-因子的存在性，最大度数至少为4的∆-临界图的欧拉因子的存在性，以及以最大度数作为∆-临界图Hamilton性判定条件的问题进行研究；本项目围绕Vizing提出的∆-临界图的独立数猜想，拟通过对最小度数为∆-1的∆-临界图（简称几乎正则∆-临界图）的独立数的上界进行研究，以此来获得一般∆-临界图的独立数上界。. 本项目将染色问题分别与因子和独立数这两个结构问题相结合，力求揭示∆-临界图的结构性质，丰富∆-临界图的研究结果，为众多实际应用问题提供理论基础。

本项目给出了Δ-临界图的独立数的上界，证明了Δ-临界图含有2-因子当且仅当其Meredith扩展图含有2-因子；对两个完全独立生成树等特殊生成树的存在性问题进行了研究；研究了图的顶点的划分问题。本项目的研究内容将结构图论的问题与染色问题相结合，将进一步揭示Δ-临界图的特殊结构性质，丰富Δ-临界图的研究结果，为众多实际应用问题提供理论基础。