论文部分内容阅读
边染色图称为彩虹的,若其所有的边都染不同的颜色.图的anti-Ramsey数AR(G,H)定义为最大的整数k,使得在图G的一个k-边染色下,图G中不包含彩虹子图H.图的anti-Ramsey数最早是由Erd(o)s等于上世纪七十年代提出的,是经典Ramsey理论的彩虹推广问题之一.研究表明图的anti-Ramsey数与经典Ramsey数并无联系,而与图的TurOn数有着密切的关系.随后的数十年特别是最近十余年中,研究者对某些特殊图类的anti-Ramsey数进行了深入地研究,确定了包括圈,路,完全图,匹配等图在完全图或者完全二部图中的anti-Ramsey数.早期的研究中,研究者一般考虑母图为完全图或者完全二部图的情形,最近几年来,母图为一般图的情形逐渐吸引了研究者的兴趣. 本论文主要研究图(主要为二部图)中匹配的anti-Ramsey数,以及在某些特殊边染色中匹配的anti-Ramsey数问题.本论文的主要结构和研究内容分为以下四部分. 第一章我们介绍了本论文所涉及的基本概念和anti-Ramsey数的研究现状,并且给出了本文的主要结果. 第二章主要研究正则二部图中匹配的anti-Ramsey数,我们给出了若干条件下正则二部图中匹配的anti-Ramsey数的值,研究结果改进了Li& Xu的结果;给出了一般的k(k≥4)-正则二部图中匹配的anti-Ramsey数的上下界. 第三章研究非正则二部图中匹配的anti-Ramsey数问题,我们主要研究了(笛卡尔)积图Pr×Pn中匹配的anti-Ramsey数,得到了Pr×Pn中匹配的anti-Ramsey数的表达公式. 第四章研究完全图的一类特殊边染色(也即Gallai染色)中匹配的anti-Ramsey数问题.首先给出了任意k-Gallai染色下完全图中存在的最小彩虹匹配的边数,最后给出了Gallai染色下完全图中的anti-Ramsey数的值.