图的平方着色、L（2，1）-标号以及列表L（2，1）-标号

论文摘要

以频率分配问题作为应用背景,该文研究了图的平方着色、L（2,1）-标号以及列表L（2,1）-标号问题.设χ（G2）,λ（G）,λl（G）分别表示图G的平方色数,L（2,1）-标号数,列表L（2,1）-标号数.关于χ（G2）和λ（G）,有以下两个著名的猜想: 猜想1[8] 若图G是平面图,则有 猜想2[7] 若图G的最大度Δ（G）≥2,则有λ（G）≤Δ2（G）。 但是,目前国内外对图的列表L（2,1）-标号问题的研究不多。 在第二章中我们考虑了Halin图的平方着色问题。证明了对所有Halin图有Δ（G）+1≤χ（G2）≤Δ（G）+3;对于最大度至少为5的Halin图G有χ（G2）=Δ（G）+1。 在第三章中我们研究了图的L（2,1）-标号问题。首先研究了Halin图、Mycielski图和Kneser图的L（2,1）-标号问题,得到了 （1） 对所有Halin图有χ（G）≤Δ（G）+7;对于最大度至少为9的Halin图G有λ（G）≤Δ（G）+2。 （2） 对所有图有λ（μ（G））≤3Δ（μ（G））-1;|G|+1≤λ（μ（G））≤|G|+λ（G）+1,且上、下界是紧的;进一步,若|G|≥Δ2（G）+5Δ（G）-2,那么λ（μ（G））=|G|+1;并给出了λ（μ（Cn））的精确刻画。其中μ（G）表示G的Mycielski图。 （3） 证明了Kneser图满足猜想2;对所有的Kneser图G=K（n,k）,有λ（G）≤|G|;进一步若n≥3k-1,则有λ（G）=|G|-1。 （4） 结合图的路划分数与L（2,1）-标号数之间的关系,给出了一个估计一般图的L（2,1）-标号数上界的多项式时间算法。并得到:若n点图G的围长g（G）≥5,则有n-1≤λ′（G）≤n+2。

论文目录

• 摘要
• Abstract
• 一、绪论
• （一）、基本概念
• （二）、L（p，q）-标号问题的概念、应用背景与研究概况
• （三）、本文的主要创新点
• 二、Halin图的平方着色
• 三、图的L（2，1）-标号
• （一）、Halin图的L（2，1）-标号
• （二）、Mycielski图的L（2，1）-标号
• （三）、Kneser图的L（2，1）-标号
• （四）、一般图的L（2，1）-标号数的算法
• 四、图的列表L（2，1）-标号
• （一）、一般图的列表L（2，1）-标号
• （二）、Halin图的列表L（2，1）-标号
• （三）、笛卡儿乘积图G×H的列表L（2，1）-标号
• （四）、复合图G[H]的列表L（2，1）-标号
• （五）、全图T（G）的列表L（2，1）-标号
• （六）、块图S（G）的列表L（2，1）-标号
• （七）、无爪图的列表L（2，1）-标号
• 参考文献
• 致谢
• 攻读学位期间发表的学术论文