Graph Factors And Related Problems

The graph factor theory plays an important role in graph theory. The study of graph factors has been an active research topic for many years. The thesis mainly focus on factor structure theory.Factor problems can be naturally divided into two classes:degree constraint factors and component factors. The first attempt on the study of factors was due to Danish mathematician Petersen (1891). In 1970, Lovasz studied (g,f)-factors and gave the structure theory of (g,f)-factors. Furthermore, general degree constrained factors were studied by Lovasz in 1972. Let H be a set value mapping. He gave a necessary and sufficient condition for a graph to have an H-factor, when H satisfies a certain given property. This theorem generalized the criteria of various kinds of factors, such as 1-factors,k-factors,f-factors, [a, b]-factors and even (g,f)-factors. Although Lovasz achieved these classic results, few people could understand these results, as the process of the proofs is quite complicated and difficult. Our work is to give some simple proofs of these results so that more researchers can well understand them.The thesis consists of three parts. The first part contributes to factor struc-ture theories, which is the most important part of our thesis; the second part is devoted to some sufficient conditions for a graph to have some factors; the third part is to investigate vertex-coloring edge-weighting problem, which is also related to factor problems.The first part of this thesis consists of Chapter 2. Firstly, we study the (g,f)-factor structure theory by using alternating trail and give a structure decomposi-tion. We give a simple proof of Lovasz's (g,f)-Factor Theorem and obtain some nice structure propositions. Moreover, we prove that our decomposition coincides with that of Lovasz's. Next, by defining a kind of new trail, the so-called change-able trail, we give an elegant proof of H-Factor Theorem and also obtain another structure decomposition. Furthermore, we will prove that this decomposition still coincides with that given by Lovasz in 1972. Finally, we give a computing formula of general fractional f-factor number by our structure propositions. It is an extension of fractional matching number.The second part of the thesis consists of Chapters 3 and 4. In Chapter 3, we study component factors. For component factor problems, there exist some characterizations for a few cases, but for most cases characterizations have not been discovered. Our work is to give some sufficient conditions for a graph to have some component factors. In Chapter 4, we investigate the relationship of eigenvalues and regular factors of regular graphs. This relationship was initiated in [15] by Brouwer and Haemers, who gave sufficient conditions for a perfect matching in a graph in terms of its Laplacian eigenvalues and, for a regular graph, gave an improvement in terms of the third largest adjacency eigenvalueλ3. We use a technique of Brouwer and Haemers to give an upper bound on the third largest eigenvalue of a regular graph that is sufficient to guarantee that the graph has some regular factors.Chapter 5 is the third part. In the chapter, we focus on vertex-coloring edge-weighting problem. The H-factor problem has a close relationship with edge-weight coloring problem. For example, the vertex-coloring 2-edge-weighting problem is equivalent to finding a special H-factor. We prove that every 3-connected bipartite graph admits a vertex-coloring 2-edge-weighting. Moreover, we show that every 4-colorable graph admits a vertex-coloring 4-edge-weighting. In particular, every plane graph admits a vertex-coloring 4-edge-weighting.