权益分类	功能权益	普通用户	{{item.name}}会员
{{category.name}}	{{benefitItem.name}}

Research on Topological Aspects of Combinatorics

组合学拓扑方面的研究

基本信息

批准号：
13640134
负责人：
OTA Katsuhiro
金额：
$ 2.05万
依托单位：
Keio University
依托单位国家：
日本
项目类别：
Grant-in-Aid for Scientific Research (C)
财政年份：
2001
资助国家：
日本
起止时间：
2001 至 2002
项目状态：
已结题

来源：
https://kaken.nii.ac.jp/grant/KAKENHI-PROJECT-13640134/
关键词：
Cyclic chromatic number Locally bipartite graph Locally planar graph Triangulation Spanning tree Topological graph theory 四角形分割 chromatic number representativity

项目摘要

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.

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