关于Tuza和Voigt的(Dm,m)-可选择性刻画定理  

On the Characterization Theorem for(Dm,m)-Choosability of Tuza and Voigt

作　　者：申玉发[1] 郑国萍[1] 张灵敏[1] 何文杰[2] 

机构地区：[1]河北科技师范学院数理系,秦皇岛066004 [2]河北工业大学应用数学研究所,天津300130

出　　处：《大学数学》2008年第3期71-73,共3页College Mathematics

基　　金：河北省教育厅自然科学研究项目(2005108);河北科技师范学院博士基金研究项目(2006D015)

摘　　要：给出一个不属于Non-D的图,但该图却不是(Dm,m)-可选择的.这表明在Tuza Zs和Voigt M的Non-D定义和(Dm,m)-可选择图的特征化定理中存在一定的冲突.针对如上冲突,对Tuza Zs和Voigh M所给出的Non-D的定义,以及(Dm,m)-可选择图的特征化定理的证明进行了修正.This paper gives a graph that does not belong to Non-D, while it is not （Dm,m）-choosable according to the definition given by Tuza Zs and Voigt M. This shows that there are some conflictions in the definition of Non-D and the characterization theorem for （Dm,m）-choosable graphs. Some modifications are given for the definition of Non-D and the proof of the characterization theorem for （Dm,m）-choosable graphs.

关 键 词：列表染色 (Dm m)-可选择性 Non-D 

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