圖的星染色與分?jǐn)?shù)染色.pdf

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

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