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

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

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