球面和射影平面上不可分地图的色和

给出了球面和射影平面上带根不可分地图的色和方程,从色和方程导出了球面和射影平面上带根一般不可分地图、二部地图的计数函数方程. 利用色和理论,研究不同类地图的计数问题,得到了一种研究计数问题的新方法. 此外,还得到了一些计数显示表达式.     

图的上可嵌入性与独立顶点的新度和

Let G be a k(k ≤3)-edge connected simple graph with minimal degree ≥ 3,girth g,r=g12.For any independent set {a1,a2 , . . . , a 6/(4 k)} of G,if,then G is up-embeddable.     

极大平面图在不可定向曲面上强嵌入的一个注记

§ 1　IntroductionA strong embeddingμ( G) of a graph G in a surface S is such an embedding thateachface boundary of the surface is a circuit.( A strong embedding is also sometimes called acircular embedding,see[1 ] orclosed2 -cell embedding[2 ] ) .Graphsconsidered here are sim-ple( that is,they have no loops or multiple edges) .Terminology here follows those in[3] .In[1 ] ,Richter,Seymour and Siran proved that every3-connected planar graph canbe strongly embedded on some non-orientable sur…     

关于点的度在modulo下等值的上可嵌入图类

结合４－边形２－因子条件,确定了一类点的度在ｍｏｄｕｌｏ４下值为０,１的上可嵌入图类,从而综合已有的结果,较完整地刻划了这类图的上可嵌入性情况。     

图的光滑支架分解

设G是一个图,A为其边集的子集。G的一个支架分解是（G－A,A）,其中G－A是去掉A后的连通图,G的一个光滑支架分解是适合下列条件的支架分解：（1）G－A的每一叶具有连通余树;（2）G－B（G－A）割边集为A,其中B（G－A）为G－A的割边集。本文给出了求一个图的光辉支架分解的一个有效算法。     

平面图的理论与四色问题(Ⅲ)——由四色问题引出的理论工作

在§10中讨论了研究平面图的面着色只需考查范平面图。且由定理10.5,将四色问题化为确定如下模3方程是否有全非0(mod3)解的问题:     

ON THE NUMBER OF EULERIAN PLANAR MAPS

This paper presents the number of combinatorially distinct rooted Eulerian planar maps with the number of non-root-vertices and the number of non-root-faces as two parameters. The parametric expressions for determining the number in the loopless Eulerian case are also obtained.     

环面上近三角剖分地图的计数

本文提供了环面上带边数和根面次这两个参数的有根近三角剖分的函数方程及其参数表达式，并给出了根面次为1以边数为参数的有根近三角剖分地图的精确解．     

3,4跳图的平面性

For a graph G of size ε≥1 and its edge-induced subgraphs H1 and H2 of size r(1≤r≤ε), H1 is said to be obtained from H2 by an edge jump if there exist four distinct vertices u,v,w and x in G such that (u,v)∈E(H2), (w,x)∈ E(G)-E(H2) and H1=H2-(u,v)+(w,x). In this article, the r-jump graphs (r≥3) are discussed. A graph H is said to be an r-jump graph of G if its vertices correspond to the edge induced graph of size r in G and two vertices are adjacent if and only if one of the two corresponding subgraphs can be obtained from the other by an edge jump. For k≥2, the k-th iterated r-jump graph Jrk(G) is defined as Jr(Jrk-1(G)), where Jr1(G)=Jr(G).An infinite sequence{Gi} of graphs is planar if every graph Gi is planar. It is shown that there does not exist a graph G for which the sequence {J3k(G)} is planar, where k is any positive integer. Meanwhile,lim gen(J3k(G))=∞,where gen(G) denotes the genus of a graph G, if the sequencek→∞J3k(G) is defined for every positive integer k. As for the 4-jump gra     

SOME CLASSES OF UPPER EMBEDDABLE GRAPHS

1IntroductionSincetheintroductoryinvestigationofmaximumgenusbyNordhaus,Stewart,andWhite[3],theupperembeddabilityofgraphshasreceivedgreatemphasissofar.AlthoughLiu[16]andNebesky[9]haverespectivelyprovideddifferentnecessaryandsufficientconditionsontheupperembeddabilityofgraphs,weknowlessaboutwhatclassesofgraphsareupperembeddable.Jaeger,PayanandXuong[10]provedthateverygraphobtainedbyconnecting(withanynumberofedges)twovertex-disjointupperembeddablegraphswithevenBettinumberisupperembeddable.Skov…