圖的圓染色及（g,f）-染色理論的若干結(jié)果.pdf

1、山東大學(xué)博士學(xué)位論文圖的圓染色及（g,f）-染色理論的若干結(jié)果姓名：閆曉霞申請(qǐng)學(xué)位級(jí)別：博士專業(yè)：運(yùn)籌學(xué)與控制論指導(dǎo)教師：劉桂真20030328山東大學(xué)博士學(xué)位論文圖的圓染色及( F ，，) 一染色理論的若干結(jié)果閏 曉 霞山東大學(xué)數(shù)學(xué)與系統(tǒng)科學(xué)學(xué)院摘要若S 是一個(gè)有限集，我們用㈦表示S 中元素的個(gè)數(shù)．對(duì)于實(shí)數(shù)o ，用l z l 表示不大于實(shí)數(shù)z 的最大整數(shù)，用『。] 表示不小于實(shí)數(shù)X 的最小整數(shù)．給定正整數(shù)i ，J ，我們用g c d

2、( i ，J ) 表示i 與J 的最大公約數(shù)．除非特別指出，本文所考慮的圖均是有限無(wú)向簡(jiǎn)單圖．我們用V ( G ) 和E ( C ) 分別表示圖G 的頂點(diǎn)集合和邊集合．用d G ( u ) 表示頂點(diǎn)Z t 在圖G 中的度，用A ( G ) 表示G 的最大度，用5 ( G ) 表示G 的最小度．C [ V 。] 表示G 的由頂點(diǎn)子集I ／導(dǎo)出的子圖，G 【E ’] 表示G 的由邊子集E ’導(dǎo)出的子圖．％表示n 個(gè)頂點(diǎn)的完全圖．Q ( G

3、) 表示G 的獨(dú)立數(shù)，x ( G ) 表示G 的色數(shù)．文中所用術(shù)語(yǔ)與符號(hào)基本與文獻(xiàn)?1 中一致．定義1 ．21 設(shè)C 是長(zhǎng)度為r 的圓周，圖G 的一個(gè)r 一圓染色是一個(gè)映射c ：X ∈以G ) r _ c 上的一段單位長(zhǎng)度的開(kāi)弧c ( z ) ，使得當(dāng)( X ，Y ) ∈E ( C ) 時(shí)，c ( x ) N c ( y ) = 0 ．如果G 有r 一圓染色，我們就稱G 是r 一圓可染色的．圖G 的圓色數(shù)記作x 。( G ) ，定義為：

4、x 。( G ) = i n f { r ：G 是r 一圓可染色的} ．圖G 的圓包數(shù)x 。( G ) 最初是在1 9 8 8 年由V i n c e 提出的，當(dāng)時(shí)稱之為“星色數(shù)”，上面的定義不是V i n c e 的原始定義，是Z h uX u d i n g 在文獻(xiàn)[ 2 】中給出的一個(gè)等價(jià)定義． V i n c e 給出的定義是這樣的：定義1 ．2 ．2 對(duì)兩個(gè)正整數(shù)k ，d ，1Sd 曼k ，圖G 的一個(gè)( k ，d ) 一染色

5、是一個(gè)染色C ．所用顏色集合為{ o ，1 ，?，k 一1 ) ，使得( z ．Y ) ∈E ( G ) = } dSJ c 扣) 一c ( ∥) } ≤k —d圓色數(shù)定義為：x 。( G ) = i n f { ；：存在G 的( ％，d ) 一染色} ． U圖的圓染色的另一等價(jià)定義是由G o d d y n ，T a r s i 和Z h a n g 在文獻(xiàn)【3 】中提出的，這個(gè)定義將圖的染色與網(wǎng)絡(luò)的流聯(lián)系起來(lái)．給定圖G 的一個(gè)( k