稀疏图的k-frugal列表染色
来源：同济大学学报·自然科学版杂志2022年第12期北京时间：
作者：房启明，张莉
单位：同济大学 数学科学学院，上海200092
摘要：图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。
关键词：图论,染色,最大平均度,平面图,围长
基金资助：国家自然科学基金（11871377）
