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

图谱半径的可达上界与可达下界

利用图的度序列得出了图的邻接矩阵的谱半径的一个可达上界和一个可达下界,并刻划了图谱半径达到上、下界时图的特征。     

稀疏图的k-frugal列表染色

图G的k-frugal列表色数一般记作chkG,关于稀疏的k-frugal列表色数上界,有以下3个结论：? k≥3,如果图G满足madG<3-a（其中0<a≤13）且ΔG≥k+3a-3,则chkG=?k-1+1;? k≥4,如果图G满足madG<3,则chkG≤?k-1+2;? k≥4,如果图G满足madG<103,则chkG≤?k-1+3。