圓色數(shù)和圓不完美圖.pdf

1、索馭弓：015ij，ijii奎級：=：退南京師冠大掌碩士學(xué)位論文園Circularchromaticnumberandcircularimperfectgraphs圓色數(shù)和圓不完美圖作者：院系：指導(dǎo)教師：張麗麗數(shù)學(xué)與計(jì)算幾科學(xué)學(xué)院許寶網(wǎng)B教授學(xué)科專業(yè)：運(yùn)籌學(xué)與控制論摘要摘要一個(gè)圖G的圓色數(shù)弘(G)是圖G的色數(shù)x(G)的自然推廣，最初是由Vince于1988年以“星色數(shù)”的定義提出來的朱緒鼎在文獻(xiàn)[3]中用類似Haj6s定理的一些操作，利

2、用G《的復(fù)制，構(gòu)造了所有圓色數(shù)至少是k／d的圖，k／d≥3本文利用此文獻(xiàn)中的三種操作構(gòu)造了圓色數(shù)相等的一類圖，計(jì)算出結(jié)果圖s，＆，島[3]的圓團(tuán)數(shù)，在此基礎(chǔ)上給出s。，&，S313]為圓不完美的充分條件，同時(shí)給出如下定理[3】的簡化證明：如果r≥3，G。，G：，G，是圓色數(shù)至少為r的圖，則x。(島)≥r。文章的最后給出了圓色數(shù)的另一等價(jià)定義：任意圖G，瓢(G)=mink／d]2d≤kIV(D)l且矗d(G)sk／d(其中D是G的定向圖)