论文部分内容阅读
彩虹匹配的研究是近十年来图论研究的热点问题之一.著名的Ryser猜想(奇数阶的拉丁方中transveral的阶问题)即等价于正常边染色Kn.n含有彩虹的完美匹配.边染色图中彩虹匹配的存在性条件得到了广泛深入的研究.另一方面,匹配的彩虹数是从极值图论的角度来研究彩虹匹配的存在性问题.图的彩虹数实际等于图的anti-Ramsey数加1,其中图的anti-Ramsey数是Erd(o)s等人于上世纪70年代提出的,而这一参数与图的Turán数存在密切的联系. 本论文研究边染色图中彩虹匹配的存在性,主要考虑了某些特殊边染色图中最大彩虹匹配的阶,以及研究若干平面图中匹配的彩虹数.本论文的主要结构和研究内容分为以下四个部分. 第一章主要介绍了本论文所涉及的图论基本概念和术语,对边染色图中彩虹匹配问题的研究背景和研究现状进行详细阐述,并简要叙述了本学位论文的主要结果. 第二章研究边染色图中匹配的存在性条件,主要考虑了图的强边染色的一种弱化条件(也即图的semi-strong边染色)中的最大彩虹匹配的问题,刻画了该边染色图的最大彩虹匹配的阶与图的顶点数之间的联系. 第三章研究极大外可平面图中匹配的彩虹数问题.我们首先给出了大小为k的匹配的彩虹数的上下界,并用同样的方法改进了(围长很大)平面三角剖分图中大小为k的匹配的彩虹数的上界,同时给出了一些小的匹配的彩虹数的准确值. 第四章研究Halin图中匹配的彩虹数问题.我们给出了大小为k的匹配的彩虹数的上下界,同时给出了一些小的匹配的彩虹数的准确值.