關(guān)于邊染色臨界圖有關(guān)性質(zhì)的研究.pdf

1、圖論相對于其他數(shù)學(xué)分支學(xué)科來說，迄今為止只有200多年的歷史。本文研究的邊染色臨界圖的問題是圖的染色問題的一個分支，也是圖論的主要研究對象之一。最大度為△的圖G，其邊色數(shù)χ'(G)要么是△，要么是△+1。如果χ'(G)=△，則稱圖G是第一類的；如果χ'(G)=△+1，則稱圖G是第二類的。如果圖G是連通的、第二類的，且對每條邊χ'（G-e）＜χ'(G)，則稱G是臨界圖。用χα'(G)表示。Vizing(1964)和Gupta(1966)各

2、自獨立的得出一個關(guān)于圖的邊色數(shù)重要定理（Vizing Theorem）：對任意最大度為△的簡單圖，χ'(G)=△或χ'(G)=△+1。1960年，Vizing提出了臨界圖獨立數(shù)猜想(Vizing’s Independence Number Conjecture)：若G是n階△臨界圖，則有α(G)≤∣V∣-2,目前為止仍沒有被完全證明出來。
　　本研究分為四個部分：第1章主要對本課題的研究背景、研究現(xiàn)狀和基礎(chǔ)概念等做了簡單介紹。第2

3、章討論了對于不含2度點邊染色臨界圖的獨立數(shù)的范圍。利用差值轉(zhuǎn)移方法證明了證明當(dāng)最大度△∈{9,10}時，此處公式省略！和當(dāng)△∈{11,…,46}，獨立數(shù)：此處公式省略。第3章討論了邊染色臨界圖的邊數(shù)的新下界，通過運用差值轉(zhuǎn)移的方法證明不含3-圈的5-臨界圖和6-臨界圖邊數(shù)的新下界分別為m≥121/56n和m≥133/52n，比目前最好的結(jié)果m≥15/7n和m≥33/13n分別提高了1/28n和1/26n。第4章提出了一些值得進一步研究的