Equitable colorings of graph products
Date Issued
2010
Date
2010
Author(s)
Lin, Wu-Hsiung
Abstract
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.
Subjects
Cartesian product
Kronecker product
strong product
equitable coloring
equitable chromatic number
equitable chromatic threshold
Type
thesis
File(s)![Thumbnail Image]()
Loading...
Name
ntu-98-D92221001-1.pdf
Size
23.53 KB
Format
Adobe PDF
Checksum
(MD5):94a09cf90add169a7d042cbe00e8709f