平面图的理论与四色问题(Ⅱ)——五色定理与四色问题的形式

§6 关于Eulet公式 令ν,ε,φ分别表示一个平面图的节点,边和面(包括无限面)的数目。为方便,自然只讨论连通的平面图。这时,总有如下关系: ν-ε+φ=2.(6.1) 这就是所谓Euler公式。其证明也相当简单,通过对边施行归纳,即可得到。它是研究平面以致多面体有关的很多问题的基础。这里也将会看到它在研究四色问题中的作用。     

地图着色定理与图的曲面嵌入(Ⅲ)

<正> 用Z_(12s+6)(I)带附加条件 d3,若在一个次为3的顶点处有三个字母,如a,b,c,则各边流入的电流只能mod 3余1或2.而且,三个流入电流之和是Z_(12s+6)的由3的倍数形成的子群的生成元. 先构造一个梳图Γ_(2s+1).然后,通过结构变换把它变为Z_(12s+6)(I)的中心部分.最后,添上首尾部分.     

K2,4×Sn的交叉数

Garey和Johnson证明了确定图的交叉数是一个NP-完全问题.确定了笛卡尔积图$K_{2,4}\times S_{n}$的交叉数是$Z(6,n)+4n.$ 当$m\geq 5,$猜想${\rm cr}(K_{2,m}\timesS_{n})={\rm cr}(K_{2,m,n})+n\lfloor\frac{m}{2}\rfloor\lfloor\frac{m-1}{2}\rfloor$.     

与顶点A-划分有关的上可嵌入图类

图G的顶点A-划分是指:G的顶点集划分{V1,V2,···,Vs},其中G[Vi](1≤i≤s)为多重完全图或多重完全二部图.文中结合图的顶点A-划分,顶点度及边连通性等条件确定了一些新的上可嵌入图类,从而将已有类似结果进行了推广,且完整地刻画了这类图的上可嵌入性情况.     

多重圈梯图在射影平面上的嵌入个数

图在不同亏格曲面上的嵌入个数常常有相关关系,因此,分析一些图类在小亏格曲面上的嵌入个数对最终确定图的亏格分布和完全亏格分布有着重要意义,本文利用嵌入的联树模型得出了多重圈梯图在射影平面上的嵌入个数.     

与直径和围长有关的最大亏格的下界的一个注记

改正了文章"与直径和围长有关的最大亏格的下界(数学学报2004,47(6):1201-1204)"中的一个错误结论,并得到了如下结果:设G是直径为d(G)的简单图,若G的围长g(G)■d(G),则ξ(G)■2,从而γM(G)■(1/2)β(G)-1.     

A POLYNOMIAL ALGORITHM FOR FINDING THE MINIMUM FEEDBACK VERTEX SET OF A 3-REGULAR SIMPLE GRAPH

1IntroductionLetG=(VE)beaconnectedsimplegraph.AsubsetFofvertexsetViscalIedafeedbackvertexsetofGifthegraPhGFisaf0rest.ThecardinaIity0faminimumfeedbackvertexset0fGisdenotedbyf(G).AvertexsubsetJofvertexsetViscaJledallonseparatingindependentsetofG,ifJisanilldependentsetofVandGJisconnected.Thema-xiammcardinalityofnollseparatingindependelltsetofGisden0tedbyz(G)andiscalledthenonseparatingindepelldentnumberofG,AgraphGiscalledacactusifGisc0nnectedandanytwocyclesofGaredisjoint.Avertexvofacon…     

循环图C(10,2)与路P_n的笛卡尔积的交叉数

证明了循环图C(10,2)与路P_n的笛卡尔积的交叉数是10n及循环图C(2m,2)的一点悬挂和两点悬挂的交叉数分别是m,2m.     

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

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

直径为4的图的最大亏格

本文证明了如下结果:设G是直径为4的简单囹,若G不含3阶完全子图K3,则G的Betti亏数ξ(G)≤2,因此有G的最大亏格γM(G)≥1/2β(G)-1.而且,在这种意义下,所得到的界是最好的.