图的无圈非正常列表染色

Acyclic improper list coloring of graphs

研究图的无圈非正常列表染色是当前图论领域的热点与难点问题.通过对极小反例G的结构分析,利用色延拓和色置换等方法证明了:最大度为4的非4-正则图是无圈(3,3)^*-可选的.所得结果推广了无圈非正常列表染色的若干结论.

It was investigated the acyclic improper list coloring problem which had been a difficult coloring problem so far.By analyzing the structure properties of the minimum counterexample G,together with coloring extension and coloring permutation,it was proved that every non-4-regular graph with maximum degree 4 was acyclically(3,3)^*-choosable.The obtained result generalized several relevant results of this topic.