稀疏图的k-frugal列表染色

作者：房启明; 张莉^*

来源：同济大学学报(自然科学版), 2022, 50(12): 1825-1832.

• 图论
• 染色
• 最大平均度
• 平面图
• 围长

图G的k-frugal列表色数一般记作chk(G),关于稀疏的k-frugal列表色数上界,有以下3个结论:?k≥3,如果图G满足mad(G)<3-a (其中0<a≤1/3,且Δ(G)≥k+3/a-3,则chk(G)=[Δ/(k-1)]+1;?k≥4,如果图G满足mad(G)<3,则chk(G)≤[Δ/(k-1)]+2;?A≥4,如果图G满足mad(G)<10/3,则chk(G)=[Δ/(k-1)]+3。

• 单位
  同济大学