乘積圖的均勻著色

Abstract

對正整數 $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.