稀疏图的k-frugal列表染色  

k-frugal List Coloring of Sparse Graphs

作　　者：房启明 张莉[1] FANG Qiming;ZHANG Li(School of Mathematical Sciences,Tongji University,Shanghai 200092,China)

机构地区：[1]同济大学数学科学学院,上海200092

出　　处：《同济大学学报（自然科学版）》2022年第12期1825-1832,共8页Journal of Tongji University:Natural Science

基　　金：国家自然科学基金(11871377)。

摘　　要：图G的k-frugal列表色数一般记作ch_(k)(G),关于稀疏的k-frugal列表色数上界,有以下3个结论:∀k≥3,如果图G满足mad(G)<3-a(其中0<a≤1/3)且Δ(G)≥k+3/a-3,则ch_(k)(G)=[Δ/k-1]+1;∀k≥4,如果图G满足mad(G)<3,则ch_(k)(G)≤[Δ/k-1]+2;∀k≥4,如果图G满足mad(G)<10/3,则ch_(k)(G)≤[Δ/k-1]+3。The k-frugal choice number of graph G is denoted by ch_(k)(G).In this paper,we prove the following theorem.Let G be a graph with maximum average degree mad(G)<3-a(0<a≤13)and maximum degree Δ(G)≥k+3/a-3,then ch_(k)(G)=[Δ/k-1]+1 for any integer k≥3;Let G be a graph with maximum average degree mad(G)<3,then ch_(k)(G)≤[Δ/k-1+2] for any integer k≥4;Let G be a graph with maximum average degree mad(G)<103,then ch_(k)(G)≤[Δ/k-1]+3 for any integer k≥4.

关 键 词：图论 染色 最大平均度 平面图 围长 

分 类 号：O157.5[理学—数学]