平面图线性2-荫度的一个上界

设图G为最大度为Δ的平面图。图G的线性2-荫度是将图G的边集合分解成k个线性森林的最小整数k,其中每个分支树为长至多为2的路,记为la2（G）。得到了平面图线性2-荫度的上界：若Δ≡0,3（mod 4）,则la2（G）≤「Δ/2棢＋8;若Δ≡1,2（mod 4）,则la2（G）≤「Δ/2棢＋7。     

关于平面图点荫度的一点改进

一个非平凡图G的点荫度a(G)是一个最小图顶点划分数使得每一个划分集的导出子图是一个森林.近年来对点荫度的研究成为图论的一个焦点并且关于这个问题有更深一步的发展,例如,随机图的点荫度以分式点荫度等.得到一个关于平面图的点荫度的一个上界;如果平面图G是没有3-圈,或是没有4-圈,或是没有5-圈,那么G的点荫度不超过2.研究的起因是一个著名的猜想:任何3-可着色的平面图的点荫度不超过2.四色定理是图论中最著名的一个定理,伴随产生了一个问题,那就是什么样的平面图是3-可着色的.不幸,这是一个难问题,Garev等人证明了判定一个平面图是否3-可着的即使在一个点不超过4的条件下仍然是NP-难问题.因此这个猜想是一个不易解决的,人们开始在一些特殊图上进行验证这个猜想是否正确.我们知道一个著名的定理:不含3-圈的平面图是3-可着色的.结合结果,给出猜想的一个正面的肯定.Havel给出两个反例,如果平面图含有4-圈或有5-圈是不可3-可着色的,因此4-圈和5-圈在证明平面图是3-可着色时必须排除.不过在结论中,如果平面图不含有4-圈或不含有5-圈,那么它的点荫度不超过2.从而可以看出猜想的条件还是很强的.同时我们的结果也拓宽了张忠辅等人的结果:外平图的点荫度不超过2.     

不含相交5-圈的平面图的线性2-荫度

设G是不含相交5-圈的平面图,证明了如果G是连通的并且δ(G)≥2,则G包含一条边xy,使得d(x)+d(y)≤10或者一个2-交错圈。由这个结果可以得到G的线性2-荫度la₂(G)≤「Δ/2+5,改进了不含5-圈的平面图的线性2-荫度的已知上界。     

不含相交三角形的平面图的无圈边色数的新上界

图G的无圈边染色是图论染色的重要研究对象,为得到平面图的无圈边色数的上界,利用差值转移方法和平面图的结构性质,证得了不含相交三角形的平面图的无圈边色数不超过Δ(G)+6。     

平面图的单射染色

利用欧拉公式和权转移规则,证明了:若G为最大度Δ(G)≤6且不含4,5,6,7-圈的平面图,则图G的单射色数的上界为Δ(G)+5.     

特殊平面图的线性二荫度

线性k-森林是指一个图G,它的每个连通分支是长至多为k的路．图G的线性k-荫度是指使得G可以边划分成m个线性k-森林的最小整数m,用lak（G）表示．本文探讨特殊平面图的线性二荫度,得到的结论有：1）每个3-圈不重边的平面图G,有la2（G）≤[△（G）／2]＋10;2）每个3-圈不重点的平面图G,有la2（G）≤[△（G）／2]＋7;3）每点至多关联[△（G）／2]个3-面的平面图G,有la2（G）≤[△（G）／2]＋10．     

无三角形IC-可平面图的线性2-荫度

设G为最大度为Δ的IC-可平面图。图G的线性2-荫度la₂(G)是将G分解为k个边不交森林的最小正整数k，其中森林的每个分支均为长至多为2的路。本文通过权转移方法研究了无三角形IC-可平面图的线性2-荫度，得到la₂(G)≤■     

外平面图的平方图的点荫度

图G的平方图G2是以V(G)作为它的点集，两个点在G2中相邻当且仅当它们在G中的距离至多为2.证明了：若G是一个最大度Δ6的外平面图,则G2的点荫度va(G2)=「Δ+12?;特别地，一棵树T的平方图T2的点荫度va(T2)=「Δ+12?.     

图的点线荫度

图G的顶点集V(G)划分为一些子集,使得每个子集的导出子图是0线森林(即每个分支是路)的最小子集数叫图G的点线荫度,记为v|a(G).Poh K S证明了任何平面图的点线荫度最多是3.Matsumato M给出了图的点线荫度的上界,即v|a(G)≤[△(G)/2].这里△(G)是G的最大度.本文给出了完全n部图的点线荫度计算公式,同时也给出了任意图的点线荫度的精确上下界．     

最大度为6的平面图是13-线性可染的

图G的线性色数lc（G）是指G的所有线性染色中所用的最少颜色的个数．运用Discharging方法，研究了平面图的线性色数问题，证明了最大度为6的平面图是13-线性可染的．     

连通图的色多项式的一次项系数的若干性质

本文讨论了连通图的色多项式的一次项系数ａ１的一些性质。当－│ａ１│＝１，图Ｇ是树；当│ａ１│≥２时，图Ｇ有圈；当│ａ１│＝２时，图Ｇ是含有一个圈且只有含有一个三点圈的图；当│ａ１│＝３时，图Ｇ是含有一个圈且只含一个四点圈的图。     

完全图的两类生成子图是谱唯一确定的

只有与 G 同构的图才有相同的谱, 则称图 G 称为谱唯一确定的. 本文证明了, $K_{n}-E(lP_{2})$ 和 $K_{n}-E(K_{1,l})$ 是谱唯一确定的.     

二分图中度条件与[a,b]-覆盖图

设G是一个图,用V(G)和E(G)表示它的顶点集和边集,并设g和f是定义在V(G)上的两个整数值函数且g相似文献   

一类双圈图拉普拉斯谱刻画

称图是由谱确定的,如果没有非同构的图具有相同的谱。用Cq标记长度为q的圈。圈图Cq的一个顶点与路图Pr的一个悬挂点相连,圈图Cq的一个顶点与Pr的另一个悬挂点相连,所得的图称为G（Cq,Cq,Pr）。本文将证明图G（Cq,Cq,Pr）由它的Laplacian谱确定。     

无向色图的Hamilton性

本文应用群论方法，证明了有限交换群的连通无向色图Ｇ（Ｆ，Ｓ）是Ｈａｍｉｌｔｏｎ图。并由此得到：（ｉ）Ｂｏｏｓｃｈ—Ｔｉｎｄｅｌｌ猜想的另一证明；（ｉｉ）有限交换群Ｆ具有对称色集Ｓ的连通色图Ｄ（Ｆ，Ｓ）是有向Ｈａｍｉｌｔｏｎ图。     

无相邻三角形平面图的(4,1)*-可选性

若对任一顶点给定k种颜色的列表,染色时每个顶点的颜色只能从自身的颜色列表中选择且每个顶点至多有d个邻点染相同的颜色,总存在图G的一个顶点的正常着色,则图G称为(k,d)*-可选色的.文章证明了每个无相邻三角形的平面图是(4,1)*-可选色的.     

最大度为6且不含5圈或6圈的平面图可8全染色

G,G的k 全染色是指用k种颜色给G的点和边进行染色,使G的任意邻接点或邻接边均染不同的颜色,且G的任一点与该点的任一关联边均染不同的颜色．证明了最大度为6且不含5 圈或6 圈的平面图是可8 全染色的．     

A.J.Schwenk猜想的证明

本文证明了偶图G的特征多项式P(G;X)=sum from k=0 to m ((-1)~ka_(2k)x~(n-2k))的系数a_(2k)是单峰的.因为树是偶图,所以A.J.Schwenk关于树的特征多项式的系数具有单峰性的猜想可由本文的结论直接得到验证.     

3连通3正则权图圈权的一个猜想的证明

本文证实了Ｂｏｎｄｙ的猜想．证明了：设 Ｇ为简单 ３连通 ３正则权图，｜Ｖ（Ｇ）｜＝ｎ＞６，则Ｇ含圈Ｃ，使Ｗ（Ｃ）＞４Ｗ（Ｇ）／ｎ．     

系列并行图,4阶完全图与小树宽图

给出了树宽≤2的图也就是系列并行图的几个等价刻画。证明了对有限图G(可以有环有重边)以下四断言彼此等价:(1)G是系列并行图,(2)G的任一个minor至少有一个点的度≤2;(3)G不以4阶完全图为minor;(4)G无子图同胚于4阶完全图。