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

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

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

3、) 表示G 的獨立數(shù)，x ( G ) 表示G 的色數(shù)．文中所用術(shù)語與符號基本與文獻?1 中一致．定義1 ．21 設(shè)C 是長度為r 的圓周，圖G 的一個r 一圓染色是一個映射c ：X ∈以G ) r _ c 上的一段單位長度的開弧c ( z ) ，使得當(dāng)( X ，Y ) ∈E ( C ) 時，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ù)”，上面的定義不是V i n c e 的原始定義，是Z h uX u d i n g 在文獻[ 2 】中給出的一個等價定義． V i n c e 給出的定義是這樣的：定義1 ．2 ．2 對兩個正整數(shù)k ，d ，1Sd 曼k ，圖G 的一個( k ，d ) 一染色

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