平面图的在线4列表染色

On-Line 4-Choosable Planar Graphs

图的在线列表染色(也叫Painting博弈)是图的列表染色的在线版本,近年来得到广泛的研究。平面图G上的f列表染色游戏有两位玩家:Lister和Painter。如果Painter在图G上的f列表染色游戏中有一个赢的策略,我们说图G是在线f-可选的。如果图G是在线f可选的且f = 4,则称图G是在线4-可选的。图G的在线选择数用χp(G)表示,是最小的正整数k使得图G是在线k-可选的。本文结合Alon-Tarsi定理证明了当k = 3, 4,5或6时,不含k圈的平面图是在线4-可选的(或叫4-可涂的)。