圖的κ-重染色問(wèn)題.pdf

1、圖染色是圖論研究中的重要問(wèn)題和熱點(diǎn)之一，有重大的理論價(jià)值和應(yīng)用背景.1976年，Stahl在頂點(diǎn)染色的基礎(chǔ)上提出了k-重頂點(diǎn)染色概念.用G=(V, E)表示一個(gè)頂點(diǎn)集為V，邊集為E的有限簡(jiǎn)單無(wú)向圖.若存在映射φ：V(G)→Zk(n)(Zk(n)是由{1，2，…，n)的所有k-元子集構(gòu)成的集合)，滿足：()uv∈E(G)，有φ(u)∩φ(v)=()，則稱φ是圖G的一個(gè)k-重n-頂點(diǎn)染色.若圖G有一個(gè)k-重n-頂點(diǎn)染色，就稱G是k-重n-頂

2、點(diǎn)可染的.稱χk(G)=min{n：G是k-重n-頂點(diǎn)可染的}為G的k-重色數(shù).當(dāng)k=1，φ就是一般的項(xiàng)點(diǎn)染色，即χ1(G)=χ(G).有關(guān)這方面的研究成果不是很多，有許多問(wèn)題還有待解決.本論文主要討論了一類特殊圖及平面圖的k-重染色問(wèn)題. 本學(xué)位論文由五章組成.第一章是對(duì)本學(xué)位論文涉及到的問(wèn)題背景，定義及進(jìn)展等各方面給出一個(gè)綜述. 在之后的兩章中，我們主要研究了平面圖的k-重染色，通過(guò)探討平面圖的一系列特殊結(jié)構(gòu)，利用權(quán)

3、轉(zhuǎn)移的方法證明了如下結(jié)果： (1)若G是外可平面圖，則圖G是k-重2k-可染的或者k-重χk(C*)-可染的，這里C*是G的最小奇圈； (2)若G是一個(gè)奇圍長(zhǎng)至少為10k-9(k≥3)的平面圖，則圖G是k-重(2k+1)-可染的； (3)若k是奇數(shù)(k≥3)，G是一個(gè)奇圍長(zhǎng)至少為5k-2的平面圖，則圖G是k-重(2k+2)-可染的. 此外第四章計(jì)算了一些特殊圖類的Mycielkian圖的k-重色數(shù).最后一