邊染色圖中雜色子圖的若干研究.pdf

1、圖G的r-邊染色是指一個(gè)滿射φ:E(G)→{1,2,…,r}.邊染色圖G稱為雜色的,若圖G的任意兩條邊都染有不同的顏色.
　　 圖的anti-Ramsey數(shù)由Erd(o)s等人于1973年提出.Erd(o)s等人的研究表明圖的anti-Ramsey數(shù)與圖的Turán數(shù)有非常密切的關(guān)系.給定正整數(shù)n和圖族F.圖族F的anti—Ramsey數(shù)R*(n,F)表示對(duì)完全圖Kn一個(gè)邊染色中所用的最大顏色數(shù),使得不含有任何雜色子圖屬于圖族F

2、.Erd(o)s等人對(duì)圖的anti-Ramsey數(shù)的研究結(jié)果大都為近似值,近幾年來(lái),研究者準(zhǔn)確刻畫(huà)了一些特殊圖類的anti-Ramsey數(shù),包括樹(shù),路,圈,星,團(tuán),簡(jiǎn)單二部圖等,以及研究了在完全二部圖的情形下這些圖類的anti-Ramsey數(shù),得到很多研究結(jié)果.
　　 本文主要研究邊染色圖中不含雜色樹(shù)和雜色路的問(wèn)題,主要研究結(jié)果如下:
　　 第一部分我們主要研究在完全二部圖Kn,n中圖族Jk的anti-Ramsey數(shù)問(wèn)題

3、,準(zhǔn)確刻畫(huà)了其表達(dá)公式,其中Jk為k條邊的樹(shù)族.研究表明該參數(shù)與Jk在二部圖中的Turán數(shù)是一致的.
　　 第二部分中.我們把圖的anti-Ramsey數(shù)定義推廣到一般圖中,運(yùn)用與第一部分相似的研究方法,主要研究了格子圖Gn,n中Jk的anti-Ramsey數(shù)問(wèn)題,對(duì)于某些特殊情形,我們準(zhǔn)確刻畫(huà)了其表達(dá)公式.
　　 第三部分我們主要研究了完全二部圖Kn,n的邊染色,完全刻畫(huà)了不含雜色路P4,P5和P6的特征,而對(duì)于Pk