不含短圈平面图的2-距离列表染色

图的染色理论在图论中有着重要的地位.主要运用权转移技巧,通过结构分析,研究了不含4-圈和5-圈的平面图的2-距离列表染色.降低了这类平面图的2-距离(Δ+4)-列表染色的最大度下界,证明了不含4-圈和5-圈且Δ≥12的平面图是2-距离(Δ+4)-列表可染的.

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

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

2-外平面图的L(2,1)-标号数

一个平面图被称为2-外平面图,如果它能嵌入平面使得所有顶点出现在至多2个面的边界上.主要研究了2-外平面图的L(2,1)-标号,得到:若图G是一个2-外平面图,则λ(G)≤Δ(G)+12,其中Δ(G)表示G的最大度.

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

线性2-森林是每个连通分支是长度至多为2的路的图,图的线性2-荫度是将边分解为k个线性2-森林的最小k值,记为la2(G).证明了若G为不含弦6-圈的平面图,则la2(G)≤[△(G)/2]+6.

平面图是(Δ+2)-2-距离着色的充分条件

主要得到了围长至少6,最大度至少12的平面图是(Δ+2)-2-距离着色的1个充分条件.

最大度为5的平面图的2-距离列表染色

讨论了最大度为5的平面图G的2-距离列表染色问题.给出了图G的2-距离列表色数χl2(G)的一些性质:1)若g(G)≥6,则χl2(G)≤11;2)若g(G)≥7,则χl2(G)≤9;3)若g(G)≥8,则χl2(G)≤8.其中,g(G)为图G的围长.

不含5-圈和相邻4-圈的平面图的线性2-荫度的一个上界

图G的一个边分解是指将G分解成子图G_1,G_2,…,G_m使得E(G)=E(G_1)=∪E(G_2)∪…∪E(G_m),且对于i≠j,E(G_i)∩E(G_j)=?.一个线性k-森林是指每个分支都是长度最多为k的路的图.图G的线性k-荫度la_k(G)是使得G可以边分解为m个线性k-森林的最小整数m.显然,la_1(G)是G的边色数χ'(G); la_∞(G)表示每条分支路是无限长度时的情况,即通常所说的G的线性荫度la(G).利用权转移的方法研究平面图的线性2-荫度la_2(G).设G是不含有5-圈和相邻4-圈的平面图,证明了若G连通且δ(G)≥2,则G包含一条边xy使得d(x)+d(y)≤8或包含一个2-交错圈.根据这一结果得到其线性2-荫度的上界为[△/2]+4.

不含相邻三角形的平面图的线性2-荫度

研究了特殊平面图的线性2-荫度问题,运用权转移等方法证明了不含相邻三角形的平面图的线性2-荫度la2(G)≤「Δ(G)2」+8.所得结果改进了现有文献的相关结果.

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

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

最大度为4的平面图的2-距离染色

2-距离染色是使得距离至多为2的顶点染不同色的一种顶点染色.1977年,Wegner猜想9种颜色可以使最大度为4的平面图有一个2-距离染色.本文证明了最大度为4的平面图用13种颜色可以使之有一个2-距离染色,而对不含三角形且最大度为4的平面图用11种颜色就可以了.

三正则二部平面图中2-因子的短圈

给出了猜想存在一个常数k(可能是8)使得每一个平面三正则无桥图存在一个2-因子,其中该2-因子有一个圈的长度最多为k的一部分解,证明了每一个三正则二部平面图都存在一个包含4-圈的2-因子.此外,还证明了三正则二部平面图中每一个4-圈都可以被扩展为一个2-因子.

极大平面图的结构与着色理论(4)σ-运算与Kempe等价类

设G是一个k-色图,若G的所有k-着色是Kempe等价的,则称G为Kempe图。表征色数33的Kempe图特征是一尚待解决难题。该文对极大平面图的Kempe等价性进行了研究,其主要贡献是:(1)发现导致两个4-着色是Kempe等价的关键子图为2-色耳,故对2-色耳的特征进行了深入研究;(2)引入σ-特征图,清晰地刻画了一个图中所有4-着色之间的关联关系,并深入研究了σ-特征图的性质;(3)揭示了4-色非Kempe极大平面图的Kempe等价类可分为树型,圈型和循环圈型,并指出这3种类型可同时存在于一个极大平面图的4-着色集中;(4)研究了Kempe极大平面图特征,给出了该类图的多米诺递推构造法,以及两个Kempe极大平面图猜想。

特殊平面图的线性二荫度

线性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连通图中可去边的一些性质

给出了4连通图中可去边的一些性质.利用4连通图的可去边,给出了4连通图的Kuratowski定理的一个较简单证明.

无4-圈的IC-可平面图的线性2-荫度

设G是最大度为Δ的IC-可平面图.图G的线性k-边染色是指G的一个映射φ:E(G)→{1,2,···,k}满足由染同一种颜色的边集导出的子图的连通分支均是长至多为2的路.图G的线性2-荫度是使G有一个线性k-边染色的最小正整数k.运用权转移方法研究了IC-可平面图的线性2-荫度,得到无4-圈的IC-可平面图的线性2-荫度的上界为[△+1/2]+3.

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

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

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

不含短圈的平面图的2-距离染色

图的2-距离染色是将图中距离不超过2的点对染不同的色.本文证明了g(G)≥5且△(G)≥18的平面图G有(△+6)-2-距离染色.

稀疏平面图的2-距离染色（英文）

图G的k-2-距离染色是指一个映射φ:V(G)→{1,2,…,k},满足对任意距离小于等于2的顶点对u,v,有φ(u)≠φ(v).2-距离色数χ_2(G)是指使得图G是k-2-距离染色的最小的k.本文证明:对于g(G)≥5且△(G)≥44的平面图G,有χ_2(G)≤△(G)+4.

不含3,4,8-圈的平面图的2-距离染色(英文)

图G的k-2-距离染色是指映射c:V(G)→{1,2,…,k},使得对G中满足0<d_G(u,v)≤2的点对u,v,有c(u)≠c(v).称χ_2(G)=min{k|G有一个k-2-距离染色}为G的2-距离色数.本文证明了不含3,4,8-圈,且△≥14的平面图是(△+5)-2-距离可染的.