S-Packing Coloring on Graphs
Date Issued
2009
Date
2009
Author(s)
Chen, Sheng-Hua
Abstract
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.wo 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.he $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}f there is a function $f:Vghtarrow {1,2,dots,k}$ such that $d(x,y)>s_i$ or $x=y$ when $f(x)=f(y)=i$.or 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.n 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.
Subjects
Graph coloring
graph algorithm
complexity
Type
thesis
File(s)![Thumbnail Image]()
Loading...
Name
ntu-98-R95221034-1.pdf
Size
23.53 KB
Format
Adobe PDF
Checksum
(MD5):143d163265b3cc4015772407be6e9c68