Research on Topological Aspects of Combinatorics

作为平面图的组合性质的一个结果，我们证明了：如果平面图的最大度足够大，则其循环色数至多为最大度加1。关于曲面上局部平面图的染色，我们发现曲面的可定向性起着重要的作用。特别地，我们给出了分别具有色数3和4的环面和Klein瓶上四边形的拓扑刻画。对于一般的不可定向曲面，我们刻画了色数为5的所有图。同一高阶的两个三角剖分可以通过一系列对角变换进行变换。研究了变换次数，证明了变换次数由一个阶的线性函数有界。另外，我们还得到了两个具有相同面大小分布的图的变换的一些结果。与这些研究相关的是，我们考虑了边都与d度顶点关联的图。具有这种性质的图称为d-覆盖图。给出了5-覆盖三角剖分和6-覆盖三角剖分的构造性刻画，对于曲面上的局部平面3-连通图，利用一般的方法得到了具有良好性质的生成平面子图，得到了这类3-连通图的几个接近Hamilton性的性质.作为对已有结果的改进，我们证明了几乎7-覆盖、几乎3-树和4-树的存在性，并得到了关于空间图的Ramsey定理、图的划分问题、三角剖分的再嵌入结构和有限平面覆盖的一些结果.

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.