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

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

围长至少为5的平面图的线性着色

本文研究了围长至少为5的平面图的线性着色问题。利用反证法,通过分析最小反例图的结构,运用欧拉公式结合适当的权转移规则得出矛盾,从而证明了围长至少为5的平面图的线性色数满足lc(G)≤[△(G)/2]+4,改进了这方面的结果。     

最大度为6且不含4-圈和7-圈的平面图的边列表和全列表

令G是一个最大度为△(G)的平面图.运用Dischanging方法,进一步探究△(G)≥6的平面图的边列表色数,得到了最大度为6且不含4-圈和7-圈的平面图的边列表色数为△,全列表色数为△+1.     

关于无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-可选择的.     

最大度为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的围长.     

围长≥7最大度≥5的平面图的无圈列表边染色

对图G的一个正常边染色,如果图G的任何一个圈至少染3种颜色,则称这个染色为无圈边染色.若L为图G的一个边列表,对图G的一个无圈边染色φ,如果对任意e∈E(G),都有φ(e)∈L(e),则称φ为无圈L-边染色.用a′_(list)(G)表示图G的无圈列表边色数.论文证明:若图G是一个平面图,且它的最大度Δ≥5,围长g(G)≥7,则a′_(list)(G)=Δ.     

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

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

围长至少为5的平面图的线性染色

如果图G的一个正常染色满足任意两种颜色的顶点集合导出的子图是一些点不交的路的并,则称这个正常染色为图G的线性染色.图G的线性色数用lc(G)表示,是指G的所有线性染色中所用的最少颜色的个数.证明了对于每一个最大度为△围长至少为5的平面图G,lc(G)≤△+2.     

一类平面图的强边着色

图G的强边着色是正常边着色且任何长为3的路的边不着双色.图G的强边色数是G的所有强边着色中使用色数的最小者,记为χ′s(G).证明了如果图G是平面图且满足g(G)≥14,则χ′s(G)≤|(5Δ2-2Δ+1)/4|,其中g(G)表示图G的围长.     

围长至少是6的平面图的injective-边染色

为了进一步探究平面图的性质,运用极小反例和权转移的方法,研究了围长至少为6且6-圈与7~--圈不相交的平面图G的injective-边染色数,并证明该染色数的上界至多为3Δ(G)-3.研究成果改进了现有injective-边染色数的一个结论.     

围长为4的平面图是4-可选色的

1994年，ThomassenC证明了每一个平面图是5-可选色的，于1995年，ThomassenC又证明了每一围长至少为5的平面图是3-可选色的．现用递推归纳法证明每一围长为4的平面图是个可选色的．甚至当确定图中任一个4圈的着色时，该结论也是成立的．     

围长至少为5的平面图的injective-染色

为了进一步探究平面图的injective-染色,利用临界图的结构性质和权转移方法,研究了围长至少为5、最大度至少为40的平面图的injective-染色数,并证明了该染色数的上界至多为Δ+2.所得结果推广了平面图injective-染色的已知结果.     

平面图的强边染色的一个结果

如果图G的一个正常边染色的任意有公共邻边的两条边的染色不相同,则它是图G的一个强边染色。图G的强边染色所需要的最小颜色数称作图G的强边色数。本文利用差值转移方法证明了最大顶点度为偶数且不小于6的平面图,如果其不含有3圈,则其强边色数不超过5△2/4,特别地,本文证明了最大顶点度为4的平面图,如果其围长不小于5,则其强边色数不超过20。     

关于可平面图的3-列表染色的一个注记

对于一个给定的平面图G,确定G是否为3-列表可染的是NP-困难的.运用Discharging方法,证明了一个平面图是3-列表可染的充分条件,即不含相交i-圈与j-圈(4≤i≤j≤6),且三角形与5--圈的距离至少为3的平面图是3-列表可染的.所证结果改进了现有文献的相关结果.     

围长不小于11且最大度为3的平面图的无圈列表边染色

若图G为最大度为3且围长不小于11的平面图,证明了它的无圈边色数a′list （ G）＝3。     

含相邻三角形的平面图的列表边和列表全染色

给定一个平面图G,χ´_l(G)和χ"_l(G)分别表示图G的列表边色数和列表全色数.证明了:如果一个平面图G满足Δ(G)≥7,并且任何一个三角形至多和一个其他的三角形相邻,则有χ´_l(G)≤Δ(G)+1和χ"_l(G)≤Δ(G)+2成立。     

外平面图的围长和分数色数

讨论了外平面图的围长和分数色数的关系 ,给出了分数色数的一个上界 ;对于固定的整数g ,给出了围长是g的外平面图的分数色数的上确界f0 (g) ,并得出若n为正整数 ,有f0 (2n) =f0 (2n +1) =2 +1 n成立 .     

Δ≥9且不含相邻4-圈的平面图是(Δ+1)-全可选和Δ-边可选的

设χ'l(G),χ″l(G)和Δ(G)分别表示平面图G的列表色数,列表全色数和最大度,目前已经证明:若G是Δ≥12的平面图,则χ'l(G)=Δ,χ″l(G)=Δ+1。本文将证明:若G是Δ≥9且不含相邻4-圈的平面图,则χ″l(G)=Δ+1,χ'l(G)=Δ。     

无4-圈和5-圈的平面图的k-frugal列表染色

在图G的一个正常点染色c中,对于图中任意一点v,如果每种颜色在点v的邻点中至多出现k-1次,这个染色就称为图G的一个k-frugal染色。关于无4-圈和5-圈的平面图的k-frugal列表染色问题,有以下两个结论:(1)对于一切不含4-圈和5-圈的平面图,如果其最大度满足Δ≥3k+8,其k-frugal列表色数小于等于「Δ/(k-1)+2;(2)一切不含4-圈和5-圈的平面图,则其k-frugal列表色数小于等于「Δ/(k-1)+5。