李國偉臺灣大學：數學研究所陳俊佑Chen, Jun-YoJun-YoChen2007-11-282018-06-282007-11-282018-06-282004http://ntur.lib.ntu.edu.tw//handle/246246/59491本文所討論的圖形均為簡單圖，即頂點個數有限多個、邊的端點不一樣、邊沒有方向、以及兩個頂點之間最多只有一個邊。 Kneser圖KG(n, k)的點集為集合[N]＝{1,2,3,…,n}中大小為k的所有子集，兩個點有邊相連若且為若這兩個集合互斥。一個圖G的平方記為G2，圖G2是由圖G的點所生成：在圖G中相異兩點的距離不大於2的點都給個邊相連。在第二節中我們證明，當k>2時，圖KG2(2k+1, k)的著色數可以從 已知的4k+2降為3k+2。緊緻Kneser圖KG2(n, k)是Kneser圖KG(n, k)的子圖，是由所有2-stable的點所生成的圖。在第三節我們證明，當k>2時，圖KG+22 (2k+2, k)的著色數等於2k+2，KG2(6, 2)=9。在最後一節，我們先定義何謂一般化Coxter圖CG(p)，其中p奇質數。也證明了這個圖CG(p)的著色數非 (p+1)/2 即 (p+3)/2。The emph {Kneser graph} ${sf KG}(n,k)$ is the graph whose vertex set consists of all $k$-subsets of an $n$-set, and two vertices are adjacent if and only if they are disjoint. The emph{square} $G^2$ of a graph $G$ is the graph defined on the vertex set of $G$ such that distinct vertices within distance two in $G$ are joined by an edge. In Section 2, it is proved that the upper bound of chromatic number $chi(${sf KG}$^2(2k+1,k))$ of the square of the Kneser graph {sf KG}$(2k+1,k)$ is reduced from $4k+2$ to $3k+2$ when $kgeq 3$. The emph{reduced Kneser graph} ${sfKG}_2(n,k)$ is the subgraph of the Kneser graph ${sf KG}(n,k)$ induced by all vertices that are 2-stable subsets. In Section 3, it is proved that $chi({sf KG}^2_2(2k+2,k))= 2k+2$ when $k geq 3$ and $chi({sf KG}^2_2(6,2))=9$. In the last section, we define the generalized Coxeter graphs {sf CG}$(p)$ and prove that $frac{p+1}{2} leq chi({sf CG}^2(p)) leq frac{p+3}{2}$ where $p$ is an odd prime.中文摘要……...………………………………………………………………………¡¡ 中文目錄……...……………………………………………………………………...¡¡¡ 英文摘要………………………………………………………………………………1 英文目錄………………………………………………………………………………2 Section 1： Introduction………………………………………………………………3 Section 2： Kang’s Method……………………………………………………………7 Section 3： Coloring of KG2(2k+1, k)…………………………………….………….11 Section 4： Coloring of KG22(2k+2, k)…………………………………….….……...26 Section 5： Coloring of the generalized Coxeter graphs …………….…….………..33 Section 6： Conclusion ………………………………………………………………35 References …………………………………………………………………………36369659 bytesapplication/pdfen-USL(2,1)標號, Coxeter圖Kneser圖著色數平方圖reduced KnesergraphKneser graphCoxeter graph}$L(2,1)$-labelingsquare graphchromatic numberthesishttp://ntur.lib.ntu.edu.tw/bitstream/246246/59491/1/ntu-93-R90221014-1.pdf