邊染色圖的頂點(diǎn)劃分問題.pdf

1、圖的頂點(diǎn)劃分問題一直都是圖論研究的熱點(diǎn)之一，在圖論研究中具有重要的理論意義，并且在計(jì)算機(jī)科學(xué)和信息科學(xué)等多個(gè)領(lǐng)域具有廣泛的應(yīng)用.Erd(o)s的一個(gè)有名的注記表明:任何2-邊染色完全圖Kn都有一棵單色支撐樹.Bollobás等人將如下劃分問題歸于Erd(o)s的結(jié)論的一個(gè)推廣問題:將r-邊染色完全圖Kn劃分成盡可能少的頂點(diǎn)不交的單色樹.實(shí)際上，早在上個(gè)世紀(jì)的七八十年代，研究者就對這類劃分問題開展了研究.Erd(o)s等提出了r-邊染色圖

2、的單色子圖劃分?jǐn)?shù)的問題.研究者們關(guān)于邊染色圖的單色樹，單色圈，單色路的劃分問題相繼得出了不少結(jié)果.Chen等人對應(yīng)地提出了r-邊染色圖的雜色樹劃分?jǐn)?shù)的概念.
　　 本文主要研究邊染色圖的單色樹和雜色樹的劃分問題，共分為五章.
　　 第一章給出了邊染色圖的頂點(diǎn)劃分問題研究現(xiàn)狀和一些基本概念.
　　 第二章研究了一種在限制條件下的r-邊染色完全多部圖的單色樹劃分?jǐn)?shù)的一個(gè)問題，并得出單色樹劃分?jǐn)?shù)的一個(gè)確切值.