圖的數列泛寬著色

S-Packing Coloring on Graphs

陳聖華(Sheng-Hua Chen)

指導教授 ： 張鎮華

國立臺灣大學/理學院/數學研究所/碩士(2009年)

https://doi.org/10.6342/NTU.2009.02910

摘要

泛寬著色問題主要來自無線網路的頻道分配、資源配置及生物多樣性模型。舉例來說，為了避免互相干擾，美國聯邦通訊委員會規定廣播電台必須相隔足夠距離才能使用相同的頻率，因為物理的限制，不同頻率需要不同的距離，政府部門必須適當配置才能使整個廣播網絡順利運作。

將此問題化約成圖論型式：對於給定的有限遞增正整數數列$(s_1,s_2,dots,s_k)$及圖$G$，若我們能夠給予圖上的每個頂點一個顏色，使得著第$i$色的兩個相異頂點距離超過$s_i$，則稱此圖可被$(s_1,s_2,dots,s_k)$著色；而對於給定的無限遞增正整數數列$S={s_n}_{n=1}^{infty}$，我們希望知道給定的圖最少要幾個顏色能夠作$(s_1,s_2,dots,s_k)$著色，此最少的數目稱為圖$G$的$S$-泛寬著色數。

在這篇論文當中，我們找出某些類別圖的最佳上、下界或著色演算法，並刻劃某些達到泛寬著色上界的圖，在演算複雜度方面我們區別某些泛寬著色問題是複雜的非確定型演算法問題(NP-complete)或是多項式時間可解的問題。

關鍵字

圖著色 ； 圖形演算法 ； 演算複雜度

並列摘要

The concept of the $S$-emph{packing coloring} motivates from the areas of frequency or channel assignment in wireless networks, resource placements and biological diversity. For instance, Federal Communications Commission of the United States Government has established numerous rules and regulations concerning the assignment of broadcast frequencies to radio stations.

Two radio stations assigned the same broadcast frequency must be located sufficiently far apart so that the broadcast does not interfere with the reception of the other,and because of physical limitation, different frequency require different distance.

The $S$-emph{packing coloring} problem is defined as follows: given a finite nondecreasing sequence $(s_1,s_2,dots,s_k)$ of positive integers, a graph $G=(V,E)$ is called $(s_1,s_2,dots,s_k)$-emph{packing colorable}
if there is a function $f:V
ightarrow {1,2,dots,k}$ such that $d(x,y)>s_i$ or $x=y$ when $f(x)=f(y)=i$.
For an infinite non-decreasing sequence $S={s_n}_{n=1}^{infty}$ of positive integers,the $S$-emph{chromatic number} $chi_S(G)$ of $G$ is the minimum number $k$ such that $G$ is $(s_1,s_2,dots,s_k)$-packing colorable.

In this thesis, we find some sharp bounds of $S$-chromatic numbers of some classes of graphs. We also characterize graphs which attain the bounds. From a complexity point of view, we distinguish NP-completeness or P-solvablility for some $S$-packing coloring problems.

並列關鍵字

Graph coloring ； graph algorithm ； complexity

參考文獻

[1] N. Alon, J. H. Spencer, The Probability Method, Wiley- Interscience Publication, 2000.

chromatic number of Cartesian products, hexagonal

lattice, and trees, Discrete Appl. Math., 155 (2007),

[4] R. L. Brooks, On colouring the nodes of a network,

Proc. Cambridge Phil. Soc, 37 (1941), 63-70.