本文中考慮到的圖均為有限,簡單圖。令圖G=（V（G）,E（G））且滿足映射σ:E（G）→ {1,-1}的有序?qū)Γ℅,σ）,那么稱有序?qū)?G,σ為符號圖,其中σ稱為圖G的特征。設(shè)e為圖G中的一條邊,那么當(dāng)σ（e）= 1（或σ（e）=-1）時邊e為正邊（或負邊）。（G,σ）是k-著色是指當(dāng)k為偶數(shù)時,V（G）→ {±1,±2,...,±k/2};當(dāng)k為奇數(shù)時,V（G）→ {0,±1,...,±k-1/2},并且對任意一條邊e =uv∈E（G）都有c（u）≠σ（uv）c（v）。稱圖（G,σ）是k-可染的如果它存在一個k-著色。圖的染色問題的研究始于著名的“四色猜想”,但該定理至今無人用純數(shù)學(xué)方法證出,因此有許多專家為了尋找一種數(shù)學(xué)證明方法開始對平面圖的3染色問題進行研究。平面圖的3染色問題最早的研究是在1959年,Grotzsch證明了每一個不含三角形的平面圖是3-可染的。隨后在1976年Steinberg提出了一個猜想:每個不含4,5-圈的平面圖都是3-可染的。但在2017年Cohen-Addad,Hebdige,Kral,Li和Salgado證明了Steinberg猜想是不成立的。因此對... 

【文章來源】：華中師范大學(xué)湖北省 211工程院校 教育部直屬院校

【文章頁數(shù)】：30 頁

【學(xué)位級別】：碩士

【文章目錄】：
摘要
Abstract
第一章 緒論
第二章 預(yù)備知識
第三章 可約結(jié)構(gòu)
第四章 權(quán)轉(zhuǎn)移過程
參考文獻
致謝


【參考文獻】：
期刊論文
[1]不包含{4,5,7}-圈平面圖是3-可染的[J]. 方冬云.  吉林師范大學(xué)學(xué)報(自然科學(xué)版). 2015(03)
[2]不包含{4,5,7}-圈平面圖的結(jié)構(gòu)性質(zhì)[J]. 方冬云.  長春工業(yè)大學(xué)學(xué)報. 2015(03)
[3]不包含{4,8,9}-圈的平面圖是3-可染的[J]. 方冬云.  系統(tǒng)科學(xué)與數(shù)學(xué). 2012(09)



本文編號：3420676