非負(fù)特征圖的非正常染色.pdf

1、本文主要研究非負(fù)特征圖的幾類染色問題:非正常染色、線性染色及無圈邊染色.
　　 圖G的一個(gè)(點(diǎn))染色是從頂點(diǎn)集合V(G)到顏色集合S的一個(gè)映射c,其中S中的元素稱為顏色,染相同顏色的頂點(diǎn)構(gòu)成一個(gè)色類.如果｜S｜=k,則稱c是圖G的一個(gè)k-染色,通常S={1,2,…,k).如果圖G的一個(gè)k-染色使得圖G的相鄰頂點(diǎn)都染不同的顏色,則稱這樣的染色是正常染色.如果圖G存在一個(gè)正常k-染色,則圖G稱為k-可染的.圖G的點(diǎn)色數(shù)是使得圖G存在

2、正常染色的最小顏色數(shù),記為χ(G).顯然,圖G的點(diǎn)色數(shù)總是存在,因?yàn)榭偪梢越o圖G的每個(gè)頂點(diǎn)各自不同的顏色,從而得到圖G的一個(gè)正常｜V(G)｜-染色.
　　 列表染色是頂點(diǎn)染色的一個(gè)推廣,這種染色對于圖的每個(gè)點(diǎn)可選用的顏色有一定限制.列表染色最初由Vizing及Erd(o)s,Rubin和Taylor提出.圖G的一個(gè)點(diǎn)列表分派L是指給圖G的每個(gè)頂點(diǎn)ν一個(gè)顏色集合L(ν).給定圖G的一個(gè)列表分派L,如果圖G存在一個(gè)正常染色φ使得每個(gè)

3、頂點(diǎn)所染的顏色均選自各自的顏色集合L(ν),則稱圖G是L-可染的或稱φ是圖G的一個(gè)L-染色.如果對于任意給定的圖G的列表分派L且每個(gè)頂點(diǎn)的顏色集合｜L(ν)｜=k,圖G都存在正常染色,則稱圖G是k-可列表染色或k-可選色的.
　　 我們要討論的第一種染色問題稱為非正常染色(Impropercoloring).
　　 圖G被稱為是(k,d)*.可染的,如果能用k種顏色對圖G的頂點(diǎn)染色,并且使得每個(gè)頂點(diǎn)的鄰點(diǎn)中至多只有d個(gè)與

4、自己染相同的顏色.顯然,圖G的(k,0)*-染色即為正常染色.對于給定的列表分派L,圖G的(L,d)*-染色是指圖G的頂點(diǎn)可以L-染色,并且每個(gè)頂點(diǎn)的鄰點(diǎn)中至多只有d個(gè)與自己染相同的顏色.如果對于任意的列表分派L滿足每個(gè)點(diǎn)的列表集合｜L(ν)｜均為k,圖G都存在一個(gè)(L,d)*-染色,則稱圖G是(k,d)*-可選的.上述的非正常選色的概念由(S)krekovski,Eaton和Hull提出.
　　 在第二章,我們將對可嵌入曲面圖

5、的(k,d)*-選色做一些研究.具體的,我們得到如下的結(jié)論:
　　 (1)每個(gè)不含4-圈和8-圈的平面圖是(3,1)*-可選色的.
　　 (2)每個(gè)不含4-圈和9-圈的平面圖是(3,1)*-可選色的.
　　 (3)每個(gè)不含3-圈和4-圈的輪胎圖是(3,1)*-可選色的；每個(gè)不含3-圈和6-圈的輪胎圖是(3,1)*-可選色的；每個(gè)不含4-圈和6-圈的輪胎圖是(3,1)*-可選色的.
　　 (4)每個(gè)不含相鄰

6、3-圈和5-圈的輪胎圖是(3,2)*-可選色的.
　　 (5)每個(gè)不含3-圈的輪胎圖是(3,2)*-可選色的.
　　 另外一種我們所關(guān)注的染色問題是線性染色(Linearcoloring).
　　 圖G的線性染色是一個(gè)正常染色滿足任何兩種色類的導(dǎo)出子圖是一些不交路的并.圖G的線性染色數(shù)是圖G存在線性染色的最少顏色數(shù),記為lc(G).
　　 文獻(xiàn)[40]中已經(jīng)證明如下結(jié)論:每個(gè)平面圖G,若存在一個(gè)有序?qū)?△

7、,9)∈{(13,7),(7,9),(5,11),(3,13)),使得△(G)≥△且g(G)≥9,則lc(G)=「△(G)/2」+1.
　　 文獻(xiàn)[40]還證明了每個(gè)平面圖G,如果g(G)≥6,則lc(G)≤「△(G)/2」+4；如果g(G)≥5,則lc(G)≤「△(G)/2」+14.
　　 在第三章中,我們將得到平面圖的線性染色的一些改進(jìn)的界.我們證明了如下結(jié)論:
　　 (1)如果G是圍長至少為8的平面圖,則l

8、c(G)≤「△(G)/2」+2.
　　 (2)如果G是圍長至少為6的平面圖,則lc(G)≤「△(G)/2」+3.
　　 (3)如果G是圍長至少為5的平面圖,則lc(G)≤「△(G)/2」+10.
　　 第三類我們要討論的染色問題是圖的無圈邊染色問題(Acyclicedgecoloring).
　　 圖G的一個(gè)(邊)染色是從邊集合E(G)到顏色集合S的一個(gè)映射c,其中S中的元素稱為顏色,染相同顏色的邊構(gòu)成一

9、個(gè)色類.如果｜S｜=k,則稱c是圖G的一個(gè)k-邊染色.如果圖G的一個(gè)k-邊染色使得圖G的相鄰的邊都染不同的顏色,則稱這樣的邊染色是正常邊染色.如果圖G存在一個(gè)正常k-邊染色,則圖G稱為k-邊可染的.圖G的邊色數(shù)是使得圖G存在正常邊染色的最小顏色數(shù),記為χ’(G).顯然,圖G的邊色數(shù)總是存在,因?yàn)榭偪梢越o圖G的每條邊各自不同的顏色,從而得到圖G的一個(gè)正常｜E(G)｜-邊染色.
　　 圖G的無圈邊染色是圖G的一個(gè)正常邊染色滿足在這種

10、邊染色下不出現(xiàn)雙色圈.圖G的無圈邊色數(shù)是使得圖G存在無圈邊染色的最小顏色數(shù),記為α’(G).
　　 在第四章,我們證明了如下結(jié)論:
　　 (1)每個(gè)平面圖G,若存在一個(gè)有序?qū)?△,g)∈.{(8,7),(6,8),(5,9),(4,10),(3,14)},使得△(G)≥△且g(G)≥g,則α’(G)=△(G).
　　 (2)每個(gè)平面圖G,如果g(G)≥4,則α’(G)≤△(G)+5.
　　 文章的最后,我