圖的星染色與分數(shù)染色.pdf

1、山東大學博士學位論文圖的星染色與分數(shù)染色姓名：孫磊申請學位級別：博士專業(yè)：運籌學與控制論指導(dǎo)教師：劉家壯2000.3.1中文期r耍X定理318對疋：6中任意不相鄰的兩頂點蜘、vo，均有辦(ji‰u(％，％))乃(疋。)，即‰是分數(shù)染色上邊臨界的。定理319對‰中任一點V，均有z，(如一V)5詈設(shè)圖G1和G2不相交，在GluG中，把Gl的每個頂點和傷的每個頂點連接起來所得到的圖稱為Gl和G的聯(lián)圖，記作GlVG2。定理321令G、日是兩個圖

2、，則乃(GVH)2z，(G)z，(日)。令臉l為正整數(shù)，ckI為奇圈，其頂點為c1，c2，，c秈I，邊為(cf，鉗I)，盧l，，2Hl(這里c2m表示c1)。作圖％如下：對c2M增加一個頂點Ⅳ，連結(jié)@，∞，l=l，，2“l(fā)。我們稱跖kl為奇輪。推論322新(阡么I)3妻。我們知道，對任一平面圖G，2s乃(G)搿。對任意正整數(shù)娩2及任意正整數(shù)橙，若我們能證明存在平面圖G、H，使得z，(G)吃譬及z，(日)3要，則對任意【2，4】之間的有理