定向图的直径和平面图的不完全选色性

论文摘要

对于图H（m,n）=Km∨（?）,给图定向使得它的直径最小。这里m≥2和n≥1时,我们有这样的结论:（1）（m是奇数时）对于m=2p+1,p≥1这种情况,当n≤（（?））-m时图的直径是2,当n≥（（?））时候是3。（2）（m是偶数时）对于m=4p+2,p≥0这种情况,如果n≤（（?））-m/2,那么直径是2,其他的时候是3;对于m=4p,p≥1这种情况,如果n≤（（?））-m/2-1,那么直径是2,其他的时候是3。 我们还讨论了关于平面图不完全选色的问题。若对任一定点给定k种颜色的列表,染色时每个顶点的颜色只能从自身的颜色列表中选择且每个顶点至多有d个邻点和它染相同的颜色,总存在图G的一个顶点的正常着色,则图G称为（k,d）*-可选色的。在第二章中证明了一个周长不小4且不含5-,6-圈的平面图,如果它至多有4个4-圈,那么这个图是（2,2）*-可选色的。还证明了一个周长不小4且不含5-,6-圈的平面图,如果它含有4-圈的个数至多为5,那么这个图是（2,3）*-可选色的。

论文目录

• Contents
• Abstract in English．
• 摘要
• Preface
• m ∨ K_n'>1 Minimum diameter in orientations of K_m ∨ K_n
• 1.1 Introduction
• 1.2 main results and known lemmas
• 1.3 The Proof of the main results
• 1.4 Summary and further considerations
• 2 On Defective Choosability
• 2.1 Introdution
• 2.2 Main results and known lemmas
• 2.3 Proof of the main results
• Bibliography
• Acknowledgements