Chromaticity Of K4-Homeomorphs With Girth 9 And 6-Bridge Graphs

Abd Karim, Nor Suriya (2007) Chromaticity Of K4-Homeomorphs With Girth 9 And 6-Bridge Graphs. Doctoral thesis, Universiti Pendidikan Sultan Idris.

[img]
Preview
Text
CHROMATICITY OF K4_HOMEOMORPHS WITH GIRTH 9 AND 6_BRIDGE GRAPHS.pdf

Download (1MB) | Preview

Abstract

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 6-bridge 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 multi-bridge graph or a k-bridge 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 6-bridge graphs. We first study the chromaticity of a type of K4-homeomorphs with girth 9, that is, the graph K4(2,3,4,d,e,f). We then investigate the chromaticity of another type of K4-homeomorphs 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 6-bridge 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 6-bridge graph O(a,a,b,b,b,c) where 2<a<b<c. Next, we investigate two more types of 6-bridge graphs of the form O(3,3,b,b,c,c) where 3<b<c and O(3,3,3,b,c,d) where 3<b<c<d. Many new results on the chromaticity of K4-homeomorphs with girth 9 and 6-bridge graphs are obtained. We end this thesis by including some open problems for further investigation.

Item Type: Thesis (Doctoral)
Subjects: Q Science > QA Mathematics
Faculties: Faculty of Science and Mathematics
Depositing User: Muhamad Awais Mahadzir
Date Deposited: 24 May 2018 08:19
Last Modified: 24 May 2018 08:19
URI: http://ir.upsi.edu.my/id/eprint/828

Actions (login required)

View Item View Item