最大度是5的可平面图是第一类的充分条件

运用Discharge方法以及临界图的一些重要性质证明了:每个最大度为5且不含四圈五圈的简单平面图的边色数等于5,即这样的平面图是第一类的。给出了最大度为5的平面图分类的一个特征刻画。     

临界图性质的探讨

临界图是连通的第二类图,而且对于G的任意一条边e,G-e是第一类图。本文主要证明了满足一定条件的Δ=6的平面图不是临界的,并给出了临界图的一个性质.     

没有任意非零3-流图的一个新下界

在文献[2] 中Tutte介绍了任意非零流并且被广泛的研究.在这篇文章中,给出了图没有处处非零3-流时边数的新极值.     

不含相邻4-圈的1-平面图边染色

利用权转移方法证明最大度为9且不含相邻4-圈的1-平面图是9-边可染的．     

关于双圈图的动态色数

为了研究有公共路时且公共路上有悬挂分支的双圈图的动态色数,利用构造特定结构的路等方法,给出了上述情况下的动态色数。此结论完善了双圈图的动态色数。     

不含3-圈的1-平面图的列表边染色与列表全染色(英文)

一个图称为是1-平面的,当且仅当它可以画在一个平面上,使其任何一条边最多交叉另外一条边.本文证明了最大度△≥15且不含三角形的1-平面图G是△-边可选择的和(△+1)-全可选择的.     

简单图的L(2,1,1)-标号

给出了完全图、完全二分图、路、圈等简单图的L(2,1,1)-标号数。对最大度为Δ 的一般图G,给出了构造L(2,1,1)-标号的一个算法, 证明了λ_2,1,1(G)≤Δ³- Δ²+2Δ。     

图的集合边色数

给出了集合边色数的定义。运用结构图论的方法,给出了集合边色数的下界以及图与其顶点删除子图、边删除子图的集合边色数的关系。     

关于边染色临界图的独立数

1968年,Vizing提出猜想:边染色临界图的独立数不大于其阶数的一半.针对不含2度点的边染色临界图,本文证明当最大度为9,10时,独立数α(G)≤(3△-3)/(5△-3)|V|和当△∈{11,…,46}时,独立数α(G)≤(15△-42)/(23△-42)|V|.     

边染色临界图边数的新下界

Vizing于1968年提出猜想:如果图G是一个点数为n,边数为m的Δ-临界图,那么满足m≥12[(Δ-1)n+3].根据临界图的若干引理,利用差值转移规则给出5-临界图和6-临界图(不含三圈)边数的新下界,改进了已有的结果.