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

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

平面图线性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-圈的平面图的线性2-荫度

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

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

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

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

图G的线性2-荫度la₂(G)是指可以使G分解为k个边不相交森林的最小整数k, 其中森林的每个分支是长度至多为2的路。 证明了若G是4-圈不共点的平面图,则la₂(G)≤「Δ/2+5。     

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

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

可嵌入到欧拉示性数非负的曲面图的线性荫度

图G的线性荫度是一种非正常的边染色,即它的边集合E(G)可以分割成线性森林的最小数量,用la(G)表示。主要研究最大度Δ(G)≥7且可嵌入到欧拉示性数非负曲面图G上的线性荫度,证明了如果图G中不含相邻的含弦6-圈,则图G的线性荫度为「Δ/2。     

有低最大平均度的图的(2,1)-全标号

图G的最大平均度mad(G)是其所有真子图的平均度的最大值,即mad(G)=max{(2|E(H)|)/(|V(H)|)},H■G.文中证明了:若G为连通图,△(G)≤3,mad(G)9/4,则λ_2~T(G)≤5.若G为连通图,△(G)≤4,mad(G)5/2,则λ_2~T(G)≤7.     

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

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

某些不含5-圈的图的线性2-荫度

线性森林是所有分支都为路的图,图G的线性荫度la(G)也就是把图的边集分解为互不相交的线性森林的最少数量k.本文对将要讨论的不含5-圈的平面图做一些限制,这些图不含3-面与3-面相邻、4-面与4-面共用一条边的情况.设G为不含5-圈的如上述所示的平面图,则la2(G)≤(Δ(G)+1/2)+5.     

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

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

图的最大平均度与线性荫度的关系

设G为一简单图,它的最大平均度mad（G）=max{2｜E（H）｜／｜V（H）｜：H为G的非空子图}．如果△（G）≥7和mad（G）≤4,或者△（G）≥5和mad（G）≤18／5,或者△（G）≥3和mad（G）〈3,则G的线性荫度为[△（c）／2]．     

最大度为5的简单图的2-距离列表染色

通过对极小反例G的结构分析,利用权转移的方法,证明了:对于Δ(G)≤5的图G,若mad(G)20/7,则χl2(G)≤10;若mad(G)19/6,则χl2(G)≤11.这一结果改进了现有的部分结论.     

较大亏格曲面嵌入图的线性荫度

通过度再分配的方法研究嵌入到曲面上图的线性荫度.给定较大亏格曲面∑上嵌入图G,如果最大度Δ(G)≥((45-45ε)^(1/2)+10)且不含4-圈,则其线性荫度为[Δ/2],其中若∑是亏格为h(h>1)的可定向曲面时ε=2-2h,若∑是亏格为k(k>2)的不可定向曲面时ε=2-k.改进了吴建良的结果,作为应用证明了边数较少图的线形荫度.     

Halin图的线性2-荫度

图G的线性2荫度la2(G)是将G分解为k个边不交的森林的最小整数k,其中每个森林的分支树的长度至多为2的路.给出了Halin图G的线性2荫度.     

特殊平面图的线性二荫度

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

平面图平方的最小度

设G是一个没有4-圈的平面图,G的平方图G2定义在V(G)上,使得2个点u和v在G2中是相邻的当且仅当它们在G中的距离为1或2.证明了:δ(G2)≤Δ(G) 33,并且当δ(G)≥4时有δ(G2)≤16.其中,δ(H)和Δ(H)分别表示图H的最小度和最大度.     

稀疏图平方图的染色数上界

图G的平方G2定义为顶点集V(G)=V(G²), 并且uv∈E(G²)当且仅当u和v之间的距离至多为2. G²的色数χ(G²)是指使得G²存在正常k顶点染色的最小整数k. 用权转移的方法证明: 如果mad(G)<4且Δ(G)≥7, 则χ(G²)≤3Δ(G)+1;  如果mad(G)≤4且Δ(G)≥8, 则χ(G²)≤3Δ(G)+5.     

图的点线荫度

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

图的无圈染色

我们证明最大度Δ≥5的图的无圈色数至多是a(G)≤L(Δ-1)2/2」,这个结果比目前公认的最小上界a(G)=Δ(0-1)/2要小。同时得出两个新的结论:对任意Δ=5的图G,有a(G)≤8;对任意Δ=6的图G,有a(G)≤12。