請用此 Handle URI 來引用此文件:
http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/44992
標題: | 乘積圖的均勻著色 Equitable colorings of graph products |
作者: | Wu-Hsiung Lin 林武雄 |
指導教授: | 張鎮華(Gerard Jennhwa Chang) |
關鍵字: | Cartesian 乘積圖,Kronecker 乘積圖,強乘積圖,均勻著色,均勻著色數,均勻著色臨界值, Cartesian product,Kronecker product,strong product,equitable coloring,equitable chromatic number,equitable chromatic threshold, |
出版年 : | 2010 |
學位: | 博士 |
摘要: | 對正整數 $k$, 如果我們能將一個圖 $G$ 中所有的點著 $k$ 種顏色, 使得兩個相鄰的點所著的顏色相異, 而且任兩種顏色類在數量上差距最多一個, 則我們稱圖 $G$ 是均勻 $k$-可著的. 一個圖 $G$ 的均勻著色數, 記為 $chi_=(G)$, 是最小的 $k$ 使得 $G$ 是均勻 $k$-可著的. 一個圖 $G$ 的均勻著色臨界值, 記為 $chi_=^*(G)$, 是最小的 $t$ 使得對任何 $k$ 大於 $t$, $G$ 都是均勻 $k$-可著的.
乘積圖已在圖上的作用與結構的參數上有廣泛的研究, 包括圖著色. 而均勻著色是著色的變化型中在現實上有著較多應用之一 --- 所有顏色出現的頻率相互接近. 本文中我們研究 Cartesian 乘積圖, Kronecker 乘積圖, 與強乘積圖的均勻著色數與均勻著色臨界值. 特別地, 我們給出路徑, 圓圈, 完全圖, 與完全二部圖的這三類乘積圖均勻著色數與均勻著色臨界值的精確數值或上界. For a positive integer $k$, if we can color all vertices of $G$ in $k$ colors such that the colors of two adjacent vertices are different, and any two color classes are different in size at most one, then we call the graph $G$ equitably $k$-colorable. The equitable chromatic number of a graph $G$, denoted by $chi_=(G)$, is the minimum $k$ such that $G$ is equitably $k$-colorable. The equitable chromatic threshold of a graph $G$, denoted by $chi_=^*(G)$, is the minimum $t$ such that $G$ is equitably $k$-colorable for $k ge t$. Graph products have been widely studied in many actions and parameters of the structure of graphs, including graph colorings. And the equitable coloring is one of the variations of colorings with more applications in real --- the frequency of the appearance of all colors are near to each other. In this thesis we study equitable chromatic numbers and equitable chromatic thresholds of Cartesian products, Kronecker products and strong products of graphs. In particular, we give exact values and upper bounds on equitable chromatic numbers and equitable chromatic thresholds of these three kinds of product of some classes of graphs such as paths, cycles, complete graphs and complete bipartite graphs. |
URI: | http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/44992 |
全文授權: | 有償授權 |
顯示於系所單位: | 數學系 |
文件中的檔案:
檔案 | 大小 | 格式 | |
---|---|---|---|
ntu-99-1.pdf 目前未授權公開取用 | 734.96 kB | Adobe PDF |
系統中的文件,除了特別指名其著作權條款之外,均受到著作權保護,並且保留所有的權利。