Research on Topological Aspects of Combinatorics

点击翻译按钮获取中文摘要

As a result on combinatorial property of planar graphs, we have proved that if the maximum degree of a planar graph is sufficiently large, then its cyclic chromatic number is at most the maximum degree plus one. On the coloring of locally planar graphs on surfaces, we have found that the orientability of the surface plays an important role. In particular, we gave a topological characterization of the quadrangulations on the torus and the Klein bottle having chromatic number 3 and 4, respectively. For general nonorientable surfaces, we characterized all graphs having chromatic number 5.There are many researches on triangulations of surfaces. Two triangulations of the same large order can be transformed by a sequence of diagonal transformations. We studied the number of times needed transformation, and proved that it is bounded by a linear function of the order. Also, we obtained some results on transformation of two graphs with the same face size distributions. Related to these researches, we considered the graphs whose edges are all incident with a vertex of degree d. The graph with this property is called d-covered. We gave a constructive characterization of 5-covered and 6-covered triangulations.For locally planar 3-connected graphs on a surface, using a general method to obtain a spanning planar subgraph with good property, we have obtained several properties of such 3-connected graphs which are close to hamiltonicity. As results improving the known results, we have proved the existence of almost 7-coverings, almost 3-trees, and 4-trees with bounded number of vertices of degree at least 3.We have also obtained some results on Ramsey theorem on spatial graphs, graph partition problems, reembedding structure of triangulation, and finite planar coverings.