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

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

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

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