UPSI Digital Repository (UDRep)



Abstract : Universiti Pendidikan Sultan Idris 
The chromaticity of graphs is the term used referring to the question of chromatic equivalence and chromatic uniqueness of graphs. Since the arousal of the interest on the chromatically equivalent and chromatically unique graphs, various concepts and results under the said areas of research have been discovered and many families of such graphs have been obtained. The purpose of this thesis is to contribute new results on the chromaticity of graphs, specifically, K4  homeomorphs with girth 9 and 6bridge graphs. A K4  homeomorph is a graph derived from a complete graph, K4. Such a homeomorph is denoted by K4(a, b, c, d, e, f) where the six edges of K4 are replaced by the six paths of length a, b, c, d, e and f. Let N and Ok be a set of natural numbers and a multigraph with two vertices and k edges, respectively. For any aI, a2, ... , ak E N, the graph O(al' a2, ... , ak) is a subdivision ofOk where the edged of Ok are replaced by paths of length a1,a2,...,ak,respectively. The subdivision of Ok is called a multibridge graph or a kbridge graph. The results in this thesis cover two main parts. The first part involves the chromaticity of K4  homeomorphs with girth 9 and the second part discusses the chromaticity of 6bridge graphs. We first study the chromaticity of a type of K4homeomorphs with girth 9, that is, the graph K4(2,3,4,d,e,f). We then investigate the chromaticity of another type of K4homeomorphs with girth 9, that is, the graph K4(,4,4,d,e,f). Then, we obtain the complete solution for the chromaticity of all types of K4 homeomorphs with girth 9. For the latter part, we first investigate the chromaticity of 6bridge graph O(3,3,3,b,b,c) where 3< b < c. We next study the chromaticity of 6 bridge graph O(a,a,a,b,b,c) where 2 < a < b < c. We continue to determine the chromaticity of 6bridge graph O(a,a,b,b,b,c) where 2 
This material may be protected under Copyright Act which governs the making of photocopies or reproductions of copyrighted materials. You may use the digitized material for private study, scholarship, or research. 