特殊圖類的標(biāo)號染色.pdf

1、山東大學(xué)碩士學(xué)位論文特殊圖類的標(biāo)號染色姓名：馬帥申請學(xué)位級別：碩士專業(yè)：運(yùn)籌學(xué)指導(dǎo)教師：吳建良20090430山東大學(xué)碩士學(xué)位論文頂點(diǎn)組成的一個(gè)圖，其中任意兩個(gè)點(diǎn)之間都有邊相連笛卡爾積圖：對圖G和Ⅳ，設(shè)v(c)=u1，U2，，讓m)和V(H)=ul，u2，，‰)它們的笛卡兒積圖GxH定義為tV(CXH)=叫訂=(H‘，tJJ)：1≤i≤r11，1≤J≤n)，E(CXH)ijWkl，i=k和(％，仇)∈E(H)，或J=2和(ui，uk)∈

2、E(G)平面圖定義：若圖G可在甲面圖上畫出，且其所有的邊只在頂點(diǎn)處相交。則G為平面圖。我們得到以下結(jié)論：對于任意的圖G的L(p，q)一標(biāo)號染色及其平方圖G2的點(diǎn)染色有以下結(jié)論成立：(x(v2)一1)max(p，q)≥增(G)≥(x(C2)一1)min(p，q)以及由此結(jié)論得出的推論：對于路Pm和R(m≥3，佗≥3)，其迪卡爾積圖FImXPn，有如下結(jié)論成立；5max(p，q)≥熘(PmXR)≥5min(p，q)對于圈Ck和路R(m≥3，

3、n≥3)，其笛卡爾積圖CrmR，有如下結(jié)論成立：I)(((％R)2)≤6(m三O(mod3)))(((％R)2)≤8(m三l(mod3))lx((％心)2)≤8(m三2(rood3)，m5)對于完全圖Kn和路R(m≥3，n≥3)，其笛卡爾積圖KnPn，有如下結(jié)論成立；(2m一1)fltaxp，q)≥增(‰R)≥(2m一1)rain(p，q)對于完全圖Kn和圈G(m≥3，n≥3)，其笛卡爾積圖joG。有如下結(jié)論成立tl(2m—1)m∞如，