无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。     

不含相交三角形和4圈的平面图的无圈边染色

如果图G的正常边染色不包含2-色圈,则称它是图G的一个无圈边染色。图G的无圈边色数表示图G的无圈边染色所需的最小颜色数。利用差值转移方法并结合平面图的结构性质,证明了不含相交三角形和4圈的平面图的无圈边色数不超过△(G)+6。     

不含3圈的平面图的无圈边染色

图的无圈边染色是图的染色理论中的一个重要问题,2001年,Alon等猜想任意简单图G的无圈边色数都不超过△（G）＋2,其中△（G）为图G的最大顶点度。为了研究该猜想对平面图是否成立,利用差值转移方法,证明了不包含三角形的平面图G的无圈边色数不超过△（G）＋3．     

不含三角形的平面图的无圈边染色

图的无圈边染色是图的染色理论中的一个重要问题.2001年,Alon等猜想任意简单图G的无圈边色数都不超过Δ(G)+2,其中Δ(G)为图G的最大顶点度.为了深入研究该猜想对平面图是否成立,利用差值转移方法并结合最小反例图的一些结构性质,证明了:不包含三角形的平面图G,如果其最大顶点度不小于6,则其无圈边色数不超过Δ(G)+3.     

1-树与外平面图的无圈边着色

设f是图G的一个正常边着色，若在f下G中没有2-色圈，则称f是图G的一个无圈边着色，其所用最小色数为G的无圈边色数。N．Alon猜想对所有简单图，无圈边色数不超过其最大度加2。本文证明了该猜想对1-树与外平面图成立，且它们的色数均不超过最大度加1。     

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

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

围长≥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)=Δ.     

不含3-圈平面图的线性染色

运用Discharging方法,研究了平面图的线性染色问题,证明了一个没有3-圈的平面图G的线性色数lc(G)≤[3△(G)/2]+2,其中△(G)表示G的最大度.     

不含4圈的平面图的无圈边染色

如果图G的正常边染色不包含2-色圈,则称它是图G的一个无圈边染色。图G的无圈边色数表示图G的无圈边染色所需的最小颜色数。利用已有的关于平面图的结构性质,证明了不含4圈的2-连通平面图的无圈边色数不超过Δ(G)+11。     

△(G)=9且不含4-圈的平面图的全色数

用△(G)表示图G的顶点最大度.对平面图,当△(G)≥11时,已证明Vizing和Behzad的图的全色数猜想(TCC)是正确的.运用Dischrge方法证明了最大度为9且不含4-圈的平面图的全色数等于10.     

图中相互独立的4-圈和8-圈

设 G 是一个含有4k 个顶点的简单图,若δ（G）≥2k,则 G 包含 k －2个4-圈和1个8-圈,使得这 k －1个圈是相互独立的。在此基础上证明了：若 G 是一个含有4k（k≥4）个顶点的图,δ（G）≥2k,则下列两种情况中至少有一种成立：（1）G 包含 k －3个4-圈和1个12-圈;（2）G 包含 k －4个4-圈和2个8-圈。且不论哪一种情况成立,这k －2个圈点不交。     

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

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

最大度为6且不含5-圈和相邻4一圈的平面图是7-全可染的

运用Discharging方法,证明了最大度为6且不含5-圈和相邻4-圈的简单平面图是7-全可染的.所得结果改进了现有文献的相关结果.     

不含4,5,6-圈的平面图的均匀染色

设Φ是图G的一个正常的顶点染色, 若Φ的任何两种不同颜色所染的顶点数目至多相差1,称是G的一个均匀染色。对于不含4,5,6-圈的平面图, 且最大度Δ≥9,那么G存在均匀Δ-染色。     

具有度限制条件的IC平面图类中轻3-圈的存在性

利用权转移方法证明了每个最小度至少为5并且最小边度至少为11的IC-平面图G含有一个最大度max{d(u),d(v),d(w)}≤17的3-圈。     

完全三部图的5圈分解问题

给出了一些可以５圈分解的具体的完全三部图；利用一个引理构造了若干可以５圈分解的完全三部图系列；给出一个完全三部图可以５圈分解的必要条件，并猜测它也是充分条件．     

二部图中包含六圈的度条件

对于平衡二部图G=(V₁,V₂;E),|V₁|=|V₂|=3k,其中k≥1,如果最小度δ≥2k,则 G或者包含k个点不交的六圈,或者包含k-1个点不交的六圈和一个四圈。     

没有7-圈的平面图的BB-染色?

研究了没有7-圈的连通平面图的BB-染色问题。应用经典的Discharging方法,证明了没有7-圈且不含相邻4-圈的连通平面图G,存在G的一棵生成树T,使得( G,T)是BB-4-可染的。这一结果进一步拓展了平面图的BB-4-可染的充分条件。