一些完全多部图唯一列表可染性的特征化

论文摘要

图的染色问题是图论的主要研究课题之一,它包括列表染色、T染色、集合染色、n元数组染色等,其中列表染色是通常染色的推广,近年来颇受人们的关注,并且在唯一k列表可染、m数、选择数等方面已经取得了许多成果。列表染色的概念最早由V.G.Vizing和P.Erdos,A.L.Rubin,H.Taylor分别独立地提出,它与普通染色概念的区别在于,事先给图G的每一个顶点u关联一个颜色列表L（v）,在给图G染色的时候,每个顶点的颜色必须在它所关联的颜色列表中选择,如果在此条件下,图G存在一个正常染色,则称图G是列表可染色的;如果存在唯一列表染色,则称G是唯一列表可染的,唯一列表染色这个概念由E.S.Mahmoodian和M.Mahdian首次提出。令G是一个阶为n的图,如果对G的每个顶点u,存在一个有k个颜色的颜色列表L（v）（k称为颜色列表的长度）,使得G有一个唯一列表染色,则称图G是一个唯一k列表可染色图,简记为UkLC图,UkLC这个概念最早由E.S.Mahmoodian和M.Mahdian提出。2001年M.Ghebleh和E.S.Mahmoodian针对完全多部图这一重要图类,除了其中9个图,特征化了U3LC图;同时他们对这9个图提出了开放问题:查证图K2,2,r,r=4,5,…,8,K2,3,4,K1*4,4,K1+4,5和K1*5,4 具有M（3） 性质。本人主要证明了图K2,2,r,r=4,5,6,7,具有M（3） 性质。

论文目录

• 摘要
• ABSTRACT
• 目录
• 第一章 绪论
• 1-1 图论的产生和发展
• 1-2 图的染色问题及列表染色问题的产生和发展
• 第二章 图的基本知识
• 2-1 图的一些基本概念
• 2-2 图的有关的基本结论
• 第三章 图的列表染色理论
• 3-1 列表染色的基本概念
• 3-2 图的唯一列表可染的主要结果
• 3-3 m数和可选择性的有关结果
• 第四章 一些完全多部图的唯一三列表可染性
• 4-1 一些U3LC完全多部图的特征化
• 4-2 完全三部图K2,2,r,r=4，5，6，7，具有M（3） 性质
• 4-3本领域的一些开放问题和猜想
• 第五章 总结
• 致谢
• 参考文献