论文部分内容阅读
图G的r-边染色是指一个满射φ:E(G)→{1,2,…,r}.边染色图G称为杂色的,若图G的任意两条边都染有不同的颜色.
图的anti-Ramsey数由Erd(o)s等人于1973年提出.Erd(o)s等人的研究表明图的anti-Ramsey数与图的Turán数有非常密切的关系.给定正整数n和图族F.图族F的anti—Ramsey数R*(n,F)表示对完全图Kn一个边染色中所用的最大颜色数,使得不含有任何杂色子图属于图族F.Erd(o)s等人对图的anti-Ramsey数的研究结果大都为近似值,近几年来,研究者准确刻画了一些特殊图类的anti-Ramsey数,包括树,路,圈,星,团,简单二部图等,以及研究了在完全二部图的情形下这些图类的anti-Ramsey数,得到很多研究结果.
本文主要研究边染色图中不含杂色树和杂色路的问题,主要研究结果如下:
第一部分我们主要研究在完全二部图Kn,n中图族Jk的anti-Ramsey数问题,准确刻画了其表达公式,其中Jk为k条边的树族.研究表明该参数与Jk在二部图中的Turán数是一致的.
第二部分中.我们把图的anti-Ramsey数定义推广到一般图中,运用与第一部分相似的研究方法,主要研究了格子图Gn,n中Jk的anti-Ramsey数问题,对于某些特殊情形,我们准确刻画了其表达公式.
第三部分我们主要研究了完全二部图Kn,n的边染色,完全刻画了不含杂色路P4,P5和P6的特征,而对于Pk,k≥7的情形则相当复杂而难以刻画.