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

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

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

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