圖的可跡性和直積圖著色性質(zhì)的討論.pdf

1、本文第一部分根據(jù)三點(diǎn)獨(dú)立集的度和(記作σ3(G))討論了，n-可擴(kuò)圖的可跡性．關(guān)于n-可擴(kuò)圖，1957年Berge在文獻(xiàn)中首次提出，n-可擴(kuò)路的問題，而自從Plumer于1980年在文獻(xiàn)中首次引入n-可擴(kuò)圖的概念以來，一些學(xué)者對(duì)可擴(kuò)圖的度和，可跡性，Hamiltonian性等方面進(jìn)行研究，得到了一系列成果．2001年Ken-ichi Kawarabayashi，Katsuhiro Ota and Akira Saito在文獻(xiàn)中給出連通的

2、n-可擴(kuò)圖的度和與哈密爾頓性及該圖與完全圖之間的一些關(guān)系．1996年阿勇嘎教授在文獻(xiàn)中根據(jù)頂點(diǎn)數(shù)不小于3的連通圖的度和得到圖G的子圖在G中可跡的一個(gè)充分條件． 在以上的研究基礎(chǔ)上，本文根據(jù)圖中三點(diǎn)獨(dú)立集的度和得到了連通的n-可擴(kuò)圖可跡的一個(gè)充分條件． 第二部分主要證明了對(duì)幾類特殊圖Hedetniemi猜想的等價(jià)命題成立．圖論中，圖的著色問題是人們關(guān)注的一個(gè)焦點(diǎn)，著色問題起源于最著名的猜想---四色猜想．自從英國人Guth

3、re.F[佛朗西斯.古特里]于1852年提出四色問題之后，人們用不同的方法去攻克這一猜想，但至今還未有嚴(yán)格的解析證明．Hedetniemi在文獻(xiàn)中揭示了一個(gè)圖的色數(shù)與直積圖色數(shù)之間關(guān)系的猜想，用代數(shù)思想研究圖的著色問題．對(duì)色數(shù)大于5的圖還未證明Hedetniemi猜想成立．Benoit Larose，Claude Tardif在文獻(xiàn)中用收縮的觀點(diǎn)研究Hedetniemi猜想，并證明了對(duì)兩個(gè)連通圖和頂點(diǎn)傳遞的射影的核，Hedetniemi