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

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

特殊图的条件染色

对于一个正整数r，图G的一个条件（k，r）-染色是使得图G的每个度至少为r的顶点至少与具有r种不同颜色的顶点相邻的正常的顶点染色．使图有一个条件（k，r）-染色的最小的整数k是图的第r个条件色数Z，（G），本文给出了对于不同的正整数，路、扇、轮的条件色数。     

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

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

平面图的(4,1)*-可选性

图G称为 (k ,d) 可选的 ,如果对满足条件L(v) =k(v∈V(G) )的任意指派L ,存在G的一个L着色使得G的每一个顶点至多有d个邻点与之着同色 .本文证明了每个无 4 圈的平面图是 (4 ,1) 可选的 .     

平面图的（4，1）＊—可选性

图G称为（k,d)＊－可选的,如果对满足条件│L(v)│＝k(v∈V（G））的任意指派L,存在G的一个L着色使得G的每一个顶点至多有d个邻点与之着同色,本文证明了每个无4－圈的平面图是（4,1）*-可选的。     

图的圈和路剖分

设G是一个顶点数为n的图,k为任意正整数且k≤n．Hikoe Enomoto和李浩证明了：如果一对不相邻顶点的度和至少为n-k 1,其中k≤n，则除了k=2，G=G5,G能被剖分成k个子图Hi，l≤i≤k，其中Hi是圈或K1或K2．本文中证明了任何一对不相邻顶点的度和至少为n-k，则G能被剖分成k个子图Ki,l≤i≤k，其中Hi是圈或是路．     

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

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

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

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

一些与圈图构成的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-连续的.     

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

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

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

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

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

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

点关联较少3-面的平面图的全染色

证明了对每点至多关联2个3-面的平面图,全染色猜想成立. 对每点至多关联2个3-面且Δ(G)≥8的平面图,有x_T(G)=Δ(G)+1.对每点至多关联[Δ(G)/2」个3-面且Δ(G)≥9的平面图,有x_T(G)=Δ(G)+1.     

最大度是4的可平面图是第一类图的充分条件

运用Discharge方法证明:最大度是4,且满足下列条件之一的可平面图G是第一类的.(1)G中不含长度为4至9的圈;(2)G中不含4-圈和5-圈,且任意两个3-面不关联于同一个顶点;(3)G中不含长度在5和8之间的圈,且任意两个3-圈,任意两个4-圈不关联于同一个顶点;(4)围长不小于4,G中不含有弦的8-圈,且任意两个4-面不关联于同一个顶点.     

K4-minor-free图的邻点可区别全染色

图G的一个正常全染色被称为邻点可区别全染色,如果G中任意两个相邻点的色集合不同.论文确定了k4-minor-free图的邻点可区别全色数.     

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

关于正则二部图的Pebblinq数

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