臨界圖邊數(shù)的下界與某些圖類的分?jǐn)?shù)邊染色.pdf

1、圖G正常邊染色π是映射π:E(G)→{1,2,…},使得任何兩條相鄰的邊無同一象.G的邊色數(shù)是其邊染色全體象的基數(shù)中最小值,用x'(G)表示.Vizing定理:G是最大度為△的簡單圖,則x'(G)=△或△+1.設(shè)G是簡單圖,若x'(G)=△,則稱G是第一類的,否則稱G是第二類的.圖G是連通的第二類圖,且對G的任何邊e,有x'(G-e)

2、提出如下猜想:n階△-臨界圖的邊數(shù)滿足m≥(n△-n+3)/2.此猜想至今尚未解決,但是這一猜想的證明卻是一個非?；钴S的課題.D.P.Sander與Y.Zhao在2003得到一個比較新的結(jié)果:n階△-臨界圖的邊數(shù)滿足m≥n(△+√2△-1)/4.本文利用臨界圖的有關(guān)性質(zhì),對于7≤△≤18的臨界圖的邊數(shù)m的下界做了進(jìn)一步改進(jìn),數(shù)值計算優(yōu)于D.P.Sander與Y.Zhao的結(jié)果.圖G的一個分?jǐn)?shù)邊染色是指分配給G的匹配M一個非負(fù)權(quán)ω<,M>

3、,使對任意e∈E(G),有∑<,MЗ e>ω<,M>≥1(或∑M<,З e>ω<,M>≤1).圖G的分?jǐn)?shù)邊色數(shù)為x'f(G)=min∑<,M>ω<,M>(或 x'f(G)=max∑<,M>ω<,M>).本文利用分?jǐn)?shù)邊染色的有關(guān)理論,討論了以下內(nèi)容:1利用圖的分?jǐn)?shù)邊染色與邊染色之間的關(guān)系,給出了一些第二類圖的充分條件的更簡單證明.2 Vizing在1965年提出了平面圖猜想:最大度為6、7的平面圖是第一類的.此猜想亦未完全證明.本文給出了