关于无6-,8-和9-圈平面图的3-选色

图G的选色数，记为ch(G)，定义为最小的自然数k，使得满足：对任一顶点给定k种颜色的列表，且染色时每个顶点的颜色只能从自身的颜色列表中选择时，总存在图G顶点的一个正常着色，文章证明了每个围长至少为4且不含6-圈，8-圈和9-圈的平面图是3-可选色的。     

围长为4的无7-,8-圈和15-圈平面图的3-选色

图G的选色数(记为χ_l(G)), 定义为最小的自然数k, 满足当对任一顶点给定k种颜色的列表, 且染色时每个顶点的颜色只能从自身的颜色列表 中选择时, 存在图G顶点的一个正常着色. 应用Discharging方法对上述问题进行研究, 证明了每个围长至少为4且不含7-圈, 8-圈和15-圈的平面图是3-可选择的.     

围长至少是4的特殊平面图的3-可选择性

图G的选择数定义为最小的自然数k,满足对任一顶点给定k种颜色的列表,且染色时每个顶点的颜色只能从自身的颜色列表中选择,总存在图G顶点的一个正常着色.通过权转移的方法证明了每个围长至少是4且不含6-圈,9-圈和11-圈的平面图是3-可选择的.     

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

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

无指定相交圈的非负特征图的列表点荫度

对于图的任一顶点集的划分,并使每个划分的导出子图均为无圈图的最小的划分基数称为图的顶点荫度.对于图G的每个顶点给定一个列表基数至少为k的颜色集合,对于图的任一染色,若每个顶点的颜色均选择与其关联的颜色集,使得每种颜色类的导出子图是一个无圈图的最小的基数k称为图的列表点荫度.证明了每个无6圈和相交i,j-圈(i,j∈{3,4})的非负特征图的列表顶点荫度为2,即为4列表可选色.     

2-连通外部平面图的平方图的列表染色

图G的平方图,记作G2,是一个以原图的顶点集作为顶点集,若原图中两点的距离不大于2则连以边所成的图.图G的列表染色数,记作lχ(G),定义为最小的自然数k,使得满足:对任一顶点给定k种颜色的列表,且染色时每个顶点的颜色只能从自身的颜色列表中选择时,总存在G顶点的一个正常染色.设G是一个最大度为Δ(G)的2-连通外部平面图,则lχ(G2)≤Δ(G)+2.     

非负特征图的列表不完全染色的研究（英文）

对每一个顶点v∈V(G),若任意给定k种颜色的列表,G都存在一个L-染色,使得G的每个顶点至多有d个邻接点与其染相同的颜色,则称图G为(k,d)~*-可选的,设G为可以嵌入到非负特征曲面的图.本文证明了若图G为2-连通的,且不包含5-圈、邻接的3-面和邻接的4-面时,G是(3,1)~*-可选的.     

不含3圈和4圈的1-平面图是5-可染的

若图G能画到平面上,且允许每条边至多出现一个交叉点,则图G是1-平面图。图G的一个正常点染色是指存在一个顶点集到颜色集的映射φ:V(G)→{1,2,…,k},对于G中的任意两个相邻的点u和v,φ(u)≠φ(v)。图G的一个k染色是指图G能够正常点染色所需的色数至少为k,图G有一个k染色又称图G是k-可染的。通过权转移的方法证明了不含3圈和4圈的1-平面图是5-可染的。     

一些与圈图构成的Corona图的b-染色

图G的一个(k)b-染色是一个正常k染色,且满足在每一个色类中至少存在一个顶点,使得该顶点与其他每个色类中至少一个顶点是邻接的.图G的b-染色数用b(G)来表示,b(G)为最大的正整数k,且用k种颜色能够对G进行b-染色.对于任意的k:χ(G)≤k≤b(G),若用k种颜色能对图G进行b-染色,称图G是b-连续.通过设计具体b-染色方案,研究了Corona图CnoPm、CnoK1,m以及CnoWm+1的m-度与b-染色数,且证明这些图都是b-连续的.     

Halin-图的列表染色

Halin-图是3-连通平面图,且存在一个面,删除关联于该面的边后是一棵树,图的列表染色是任给图G的每个顶点V配一颜色集合L(V),满足|L(V)|=k,k为某确定正数;G的每个点若均可着从L(V)中选出的一种颜色,使得任意两个相邻近的点着不同的色,则称G是k-可选择的,Min(k)称为G的选择数或列表色数,记x_L(G),本文证明了Halin图的列表色数为3或4,并得到了x_L(G)=3的充要条件。     

不含相邻三角形平面图的4-可选色问题

设k为正整数，G为图．我们给G每个顶点一个长为k的任意表，如果存在一个顶点着色，使得每个顶点都可从表中得到一种颜色，则称G为k-可选色的．本文中证明了不含相邻三角形并且四面和三面不相邻的平面图是4-可选色的。     

关于可平面图的3可选择性的一个注记

给图G=（V,E）的每个顶点v∈V分配一个可用色集L（v）,称L={L（v）｜v∈V}为G的一张色列表,若对每个顶点v∈V,都可以从L（v）中找到一种颜色φ（v）染给v,使得φ（x）≠φ（y）对任意边xy∈E成立,则称G是L可染的。若对G的任意一张满足｜L（v）｜≥k对所有v∈V成立的色列表L,G都是L可染的,则称G是k可选择的。本文运用Discharging方法证明了每一个不含4,6,8圈且任意两个三角形的距离至少为2的可平面图是3可选择的。     

强全控制边临界图

不含孤立点的图G称为全控制边临界的,如果对任意两个不相邻顶点u和v, 有γt(G uv)<γt(G).也称这样的图为γt-临界的. 如果该图G的全控制数为k,称G为k-γt-临界的.一个γt-临界图G称为强γt-临界的, 如果对任意顶点v∈V(G)存在G的一个基数为γt(G)-1的控制集D使得G[D]除v外不含孤立点.研究了强γt-临界图的性质,给出了一个由小的强γt-临界图构造大强γt-临界图的方法.     

没有某些圈的平面图的3可选择性

设G=(V,E)是一个图,对G的每一点v给一颜色集L(v).G称为L列表可染的,如果存在G的点染色f满足:f(u)≠f(v),(u,v)∈E(G),且f(u)∈L(u),u∈V(G).G称为k可选择的,对于任何列表L(v)(这里每一个L(v)恰有k个元素)G都是L列表可染的.本文研究了没有某些圈的平面图的可选择性,证明了没有4,5,7,10圈的平面图是3可选择的.     

关于正则二部图的Pebblinq数

图G的pebbling数f（G）是最小的正整数n,使得不管n个pebble如何放置在G的顶点上,总可以通过一系列的pebbling移动把一个pebble移到图G的任意一个顶点上,其中图G的一个pebbling移动是从一个顶点移走2个pebble,而把其中的一个移到与其相邻的一个顶点上。证明了具有2m个顶点的k-正则二部图的Pebbling数为2m,其中k≥[（m＋1）／2]。     

图的独立数与分数一致性

设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一致图。     

可平面图3可选择的一个充分条件

给G=(V,E)的每个顶点分配一个色列表L={L(v)|v∈V},若G有一个正常顶点染色φ,使得对每个顶点v∈V,都有φ(v)∈L(v),则称G是L可染的。若对G的每一个满足|L(v)|≥k,v∈V的L,G都是L可染的,则称G是k可选择的。本文通过权转移方法证明了每个不含4,6,8,10圈的可平面图是3可选择的。     

较少短圈的平面图的全色数

图G的k-全染色是用k种颜色对图G的V(G)∪E(G)中的元素进行着色, 使得相邻或者相关联的两个元素染不同的颜色, 图G的全色数是使G存在k-全染色的最小整数k. 对最大度为Δ的平面图, 如果(1),Δ(G)≥5且任何点至多关联一个长度至多为5的圈, 或者(2),Δ≥4, 不含3-圈并且任何点至多关联一个长度至多为6的圈, 则它的全色数为Δ(G)+1。