最大度是4的可平面图的边染色

对于最大度是Δ的可平面图G,如果χ′（G）=Δ称G为第一类图,如果χ′（G）=Δ＋1称G为第二类图,χ′（G）表示G的边染色数.1965年,Vizing举例说明,最大度是4的平面图中不仅有第一类图,也有第二类图.论文运用Discharge方法及临界图的重要性质证明：最大度是4,不含5圈和6圈,且任意两个相交面的度不相同的可平面图是第一类图.     

最大度是5的可平面图的边染色

运用Discharge方法及临界图的一些重要性质证明了:最大度是5且任意一个3-圈与任意一个4-圈不相邻接,或任意一个3-圈与任意一个5-圈不相邻接的可平面图是第一类图.从而给出了最大度是5的可平面图是第一类图的2个充分条件.     

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

最大度是5的可平面图,既有第一类,也有第二类。该文运用Discharge方法以及临界图的一些重要性质证明,每个最大度为5且不含三圈或不含四圈或不含五圈的简单平面图的边色数等于5,即这样的平面图是第一类的。文中还给出了最大度为5的平面图分类的一个特征刻画。     

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

运用Discharge方法以及临界图的一些重要性质证明了:每个最大度为5且不含四圈五圈的简单平面图的边色数等于5,即这样的平面图是第一类的。给出了最大度为5的平面图分类的一个特征刻画。     

最大度是5的可平面图的边染色

对于最大度是Δ的可平面图G,如果χ′(G)=Δ,称G为第一类图;如果χ′(G)=Δ+1,称G为第二类图.χ′(G)表示G的边染色数.1965年,Vizing举例说明Δ=5的可平面图中既有第一类图,也有第二类图.作者运用Discharge方法证明最大度是5且不包含有弦的4-圈和有弦的5-圈,或不包含有弦的4-圈和有弦的6-圈的可平面图是第一类图.     

最大度是6不含相邻k-圈的可平面图的边染色

运用Discharge方法和临界图性质证明了,最大度是6且任意两个长度至多是6的k-圈不相邻的可平面图是第一类图.     

一些平面图的无圈边染色

主要研究了平面图的无圈边染色问题。证明了对平面图G,如果G不包含3,5圈,且G中任意两个4-圈都不共边,则无圈边染色猜想成立;并且,如果G不含3-圈,且任意两个4-圈不共点,则G的无圈边染色数不大于Δ(G)+3。     

最大度是6的平面图是第一类图的一个充分条件

用x'(G)表示G的边染色数.对于最大度是△的可平面图G,如果X'(G)=△,称G为第一类图;如果x'(G)=△+1,称G为第二类图.运用Dischrge方法证明:最大度是6且不含7圈的可平面图G是第一类图.     

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

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

平面图无圈边着色的一个结果

图G的无圈边着色是指图G的一个正常边着色且不含双色的圈.图G的无圈边色数是指图G的无圈边着色中所用色数的最小者,用x’a(G)表示;证明了如果G是一个D中的顶点不与3-面相关联,3-顶点不与D中的顶点相邻且Δ(G)≥6的平面图,则x’a(G)≤Δ(G)+1。     

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

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

一类平面图的强边染色

图G的强边染色是指对图G的边进行染色,使得距离不超过2的任意两条边染不同的颜色. 任何一个平面图都可用4Δ+4种颜色进行强边染色. 证明了当平面图没有k-圈(4≤k≤10)且3-圈不相交时(即每个顶点至多关联一个3-圈), 必定存在一个3Δ+1种颜色的强边染色.     

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

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

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

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

4-圈不共点的平面图的线性2-荫度

图G的线性2-荫度la₂(G)是指可以使G分解为k个边不相交森林的最小整数k, 其中森林的每个分支是长度至多为2的路。 证明了若G是4-圈不共点的平面图,则la₂(G)≤「Δ/2+5。     

无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的无7-,8-圈和15-圈平面图的3-选色

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

可平面图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可选择的。