平面圖的非正常染色.pdf

1、學校代碼：10345研霓，類型基礎研究漸I；二殲煢六學ZHEJIANGN0RMALUNlVERSITY碩士學位論文題目鼉一，平面圈的饕篷常染色學科專業(yè)：年級：2014級運籌學青控黼論拳■號：201421104111研霓生：≮張傳瓣1、一指導教師：。薹摩前中禹分類號：，，≯01舀7i5j論文提交好褥：2017年≯月摘要本文所考慮的圖是有限的，簡單的和無向的令G=(VE)是一個平面圖，k為一個正整數(shù)如果存在一個映射妒：yj1，2，忌]I滿足

2、使得對任意xy∈E，都有妒(z)≠妒(可)則稱矽是G的一個七一染色若G有一個七一染色，則稱G是七一可染的設d1，d2，毗是k個非負整數(shù)，G=(VE)是分別以y及E為頂點集和邊集的圖圖G的一個(d1，d2，比)一染色是一個映射妒：y一1，2，尼)使得子圖G瞰]的最大度至多為di，其中K=u∈Vl矽(v。)=講若G存在一個(d，，dz，也)一染色，則稱G是(d1，d2，如)一可染的若d1=d2==d后=d，則稱G是正非正常忌一可染的，或(k

3、，d)一可染的顯然G是正常％一可染的等價于它是(0，0，o)一可染的；若G是(d1，d2，dk)一可染的，則它一定是(啦，必，畋)一可染的，其中也≤《，i=1，2，kSteinberg在1976年提出了一個著名的猜想：不含4和5一圈的可平面圖是3一可染的圍繞Steinberg猜想，人們提出著名的Bordeaux猜想：既不含5一圈又不含相交三角形的平面圖是(3，0)一可染的(弱的)及既不含5一圈又不含相鄰三角形的平面圖是(3，o)一可染的

4、(強的)和Nsk’S猜想：3一圈不與3一圈和5一圈相鄰的平面圖是(3，0)一可染的圍繞著以上幾個著名的猜想，后人展開了一系列相關的研究并取得了一些成果本論文分為三章，主要圍繞以上的猜想及相關問題展開研究，所得結論改進了現(xiàn)有的一些結果第一章介紹了本論文所涉及到的相關定義與符號，并做了一個關于正常和非正常染色的研究現(xiàn)狀的綜述第二章介紹了4圈不與3一，4一圈相鄰且不含7_圈的平面圖是(1，1，0)一可染的和5_圈不鄰的可平面圖是(1，1，0)