2-连通图过指定边的长圈(英文)

对2 连通非完全图G,令μ(G)=min{max{dG(u),dG(v)}dG(u,v)=2}.一个著名的范定理:每一个2 连通非完全图G包含长至少为min{V(G),2μ(G)}的圈.在这篇论文中我们证明了:若G是2 连通无三角形图,则通过G的任一边存在长至少为min{V(G),2μ(G)}的圈.

P3-支配图哈密尔顿性的两个充分条件

在文献[3]中介绍了一个新的图类—P_3-支配图.这个图类包含所有的拟无爪图,因此也包含所有的无爪图.在本文中,我们证明了每一个点数至少是3的三角形连通的P_3-支配图是哈密尔顿的,但有一个例外图K_(1,1,3),同时,我们也证明了k-连通的(k≥2)的P_3-支配图是哈密尔顿的,如果an(G)≤k,但有两个例外图K_(1,1,3)and K_(2,3).

切实可行的四色定理证明新方法

本文简单介绍用图论的方法证明三角形结构连通图的不可避免构形集,同时用顺序配色的方法证明三角形结构连通图的色数≤4,也就证明平面图的色数≤4.为四色定理证明和应用找到了切实可行的新方法.