不含4-圈和5-圈的平面图的线性2-荫度

线性k-森林是每一个连通分支均为长度不超过k的路的图。一个图G的线性k-荫度是将图G的边集合能分解成的线性k-森林的最少数目,用lak(G)来表示。证明了:若G为不含4-圈和5-圈的平面图,则la2(G)≤「Δ(G)+1/2■+4。     

不含4-圈的平面图的线性2-荫度

图G的线性2-荫度la2(G)是将G分解为k个边不交的森林的最小整数k,其中每个森林的分支树是长度至多为2的路.证明了:若G为不含4-圈的平面图,则la2(G)≤「Δ(G) 12﹁ 3,其中Δ(G)表示图G的点最大度.     

不含弦5-圈和弦6-圈的平面图的线性2-荫度

设G是不含弦5-圈和弦6-圈的平面图,证明了若G连通且δ(G)≥2,则G包含一条边xy,使得d(x)+d(y)≤9,或一个2-交错圈。根据这一结果,得到图G的线性2-荫度la2(G)≤Δ(G)2+6。     

特殊平面图的线性二荫度

线性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．     

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

设G是不含相交4-圈的平面图.证明了若G是连通图且最小度δ(G)≥2,则G包含一条边xy使得d(x)+d(y)≤9或一个2-交错圈.由这一结果得到G的线性2-荫度la_2(G)≤「Δ/2┐+6.     

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

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

最大度为6且不含相交4-圈的三类平面图的全染色

设G是一个不含相交4-圈的平面图且Δ(G)≥6,证明了如果G还不含相交3-圈,或不含5-圈,或不含6-圈,则全染色数χ″(G)=Δ(G)+1。     

无4,5,6-圈且无两个相交三角形的平面图的L(p,q)-标号

令λp,q(G)为图G的L(p,q)-标号数,证明了若G是不合4,5,6-圈且不含两个相交三角形的平面图,则λp,q(G)≤(2q-1)△(G)+max｛4p +4q-4,6p +2q-4,8p-4｝.这一结果暗含着对于不合4,5,6-圈且不含两个相交三角形的平面图G,Wegner的猜想成立.     

平面图线性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。     

不含4-,5-圈且无相交3-面的平面图的星边染色

图 G 的星边染色是指 G 的一个正常边染色满足 G 中无长为4的路（或圈）是2-边染色的.使得图 G 有星边染色的最小颜色数 k 称为 G 的星边色数,记为 χ^′_st (G ) .证明了若平面图 G 不含4-5-圈且无相交3-面,则χ^′_st (G )≤ [1.5]Δ + 10     

图的独立数与分数一致性

设G是一个顶点集为V（G）,最小度为δ（G）,独立数为α（G）的图, k≥2是整数。图G的支撑子图F称作是图G的分数k-因子,如果对于每一个x∈V（F）都有dhG（x）＝k。如果对于图G的每条边e,图G都有一个分数k-因子包含它而且同时有一个分数k-因子不包含它,则称图G为分数k一致图。证明了如果δ（ G）≥k＋2,且α（ G）≤4k（δ-k-1）（k＋1）2,则图G是一个分数k一致图。     

Halin图的集染色

对于非平凡连通图G,G的k集染色是指映射c：V（G）→Nk,对任意顶点v∈V（G）,定义邻色集cN（v）={c（u）｜u∈N（v）},若对uv∈E（G）有cN（u）≠cN（v）,则称c为G的一个k集染色.满足上述条件的最小k值称为G的集色数,记为χs（G）.为了更快更有效地给Halin图着色,采用集染色的着色方法,证明了当p≥4时,Halin图G（Cp,Tq）的集色数是3,并且还证明了对任意的Halin图G（Cp,Tq）,有p＋1≤q≤2p-2成立.     

联结数与分数（k，n’）一临界消去图

设G是一个图,若删除G中任意n’个顶点的剩余子图依然是分数k-消去图,则称G为分数（k,n＇）-临界消去图．笔者证明了若k≥2,n,≥0,bind（G）≥^（n＇＋1）且6（G）≥k＋n＇＋1,则G是分数（k,n＇）-临界消去图．     

关于几乎k-可扩图的若干结论

设G是具有奇数个顶点的图,k是非负整数且满足V(G)≥2k+1,若G中任意一个k-匹配都可以扩充为G的一个几乎完美匹配,则称G是几乎k-可扩图.文中证明了连通的几乎1-可扩图与2-连通的几乎k-可扩二部图分别添加一个新边后仍保持原来的可扩性.     

Cartesian积图的最大拉普拉斯特征值

设G=(V(G)),E(G)),H=(V(H),E(H))是两个简单的连通图,定义与的Cartesian积G×H图是:其顶点集为V(G×H)=V(G)×V(H),其中任何两个顶点(u,u’),(v,v’),相邻当且仅当u=v且u’,v’在H中相邻;或u’=v’且u,v在G中相邻,这里u,v∈V(G),u’,v’∈V(H).本文研究两个图的Cartesian图的拉普拉斯矩阵的最大特征值,得到如下结论:设简单图G具有n顶点m条边,图H具有P个顶点q条边,那么G和H的Cartesian积图G×H的拉普拉斯最大特征值p(L(G×H))≤2m/n[1+(n-1)(((n3/4m2)-(1/n-1))～(1/2))]+((2p-1)～(1/2))+1.     

k-连通的强-［k+4,2］图的Hamilton路

如果G的任意s个点的导出子图中至少含有t条独立边,则称图G为强-［s,t］图。本文证明了以下结果：设G是k-连通的强-［k+4,2］图,且δ≥k+1,则G或者有Hamilton路或者同构于(∪^k+2_i=1H_i)∨G_k,其中H_i≌K₂,i=1,2…k+2,G_k是含有k个点的任意图。     

双外平面图的点染色

图染色问题是图论研究中的重要问题之一,本文针对双外平面图G的点色数进行研究,并证明了：（1）不加剖分点时,当顶点数为6n＋k（n=1,2,…）（k=1,2,3）时,xv=4;否则xv=3.（2）xv=4时,当在相同面上两端的顶点标号冲突时,若剖分点加在这个标号相对的边上时,仍然有xv=4;否则xv=3.     

非连通图C4m-1∪C12m-8∪G的优美标号

讨论了非连通图C4m-1∪C12m-8 ∪G的优美性,证明了当m为任意正整数,G是特征为k且缺k＋6m-3标号值的交错图（6m-3≤k＋6m-3≤｜ E（G）｜）时,非连通图C4m-1∪ C12m-8∪G存在缺标号值k＋1的优美标号,其中,G是具有m个顶点的圈.