边染色图的顶点划分问题

摘要

图的顶点划分问题一直都是图论研究的热点之一，在图论研究中具有重要的理论意义，并且在计算机科学和信息科学等多个领域具有广泛的应用.Erd(o)s的一个有名的注记表明:任何2-边染色完全图Kn都有一棵单色支撑树.Bollobás等人将如下划分问题归于Erd(o)s的结论的一个推广问题:将r-边染色完全图Kn划分成尽可能少的顶点不交的单色树.实际上，早在上个世纪的七八十年代，研究者就对这类划分问题开展了研究.Erd(o)s等提出了r-边染色图的单色子图划分数的问题.研究者们关于边染色图的单色树，单色圈，单色路的划分问题相继得出了不少结果.Chen等人对应地提出了r-边染色图的杂色树划分数的概念.
　　 本文主要研究边染色图的单色树和杂色树的划分问题，共分为五章.
　　 第一章给出了边染色图的顶点划分问题研究现状和一些基本概念.
　　 第二章研究了一种在限制条件下的r-边染色完全多部图的单色树划分数的一个问题，并得出单色树划分数的一个确切值.
　　 第三章定义了两种特殊边染色，利用这两种特殊边染色得到了r-边染色完全多部图的杂色树划分数的下界.
　　 第四章主要考虑r-边染色完全多部图Kn1，n2，…，nk（k≥4）的杂色树划分数的上界的问题，并且其上界和下界最多相差1.
　　 第五章给出了一个进一步考虑的问题，并考虑r-边染色完全多部图杂色树划分的算法问题.

目录

摘要

1 绪论

1．1 问题的研究现状

1．2 本文主要结论

2 完全多部图的单色树划分

2．1 定理

2．2 定理证明

3 完全多部图杂色树划分数的下界

3．1 第一种染色Φ*r,1

3．2 第二种染色Φ*r,2

3．3 主要结果

4 完全多部图的杂色树划分数的上界

4．1 引理

4．2 主要结果

5 研究展望

参考文献

在学期间的研究成果及发表的论文

致谢

声明

浙江师范大学学位论文诚信承诺书