Chromaticity of Certain 2-Connected Graphs

Lau, Gee Choon (2003) Chromaticity of Certain 2-Connected Graphs. Masters thesis, Universiti Putra Malaysia.

[img] PDF
2232Kb

Abstract

Since the introduction of the concepts of chromatically unique graphs and chromatically equivalent graphs, many families of such graphs have been obtained. In this thesis, we continue with the search of families of chromatically unique graphs and chromatically equivalent graphs. In Chapter 1, we define the concept of graph colouring, the associated chromatic polynomial and some properties of a chromatic polynomial. We also give some necessary conditions for graphs that are chromatically unique or chromatically equivalent. Chapter 2 deals with the chromatic classes of certain existing 2-connected (n, n + 1,)-graphs for z = 0, 1, 2 and 3. Many families of chromatically unique graphs and chromatically equivalent graphs of these classes have been obtained. At the end of the chapter, we re-determine the chromaticity of two families of 2-connected (n, n + 3)-graphs with at least two triangles. Our main results in this thesis are presented in Chapters 3, 4 and 5. In Chapter 3, we classify all the 2-connected (n, n + 4)-graphs wit h at least four triangles . In Chapter 4 , we classify all the 2-connected (n, n + 4)-graphs wit h t hree triangles and one induced 4-cycle. In Chapter 5, we classify all the 2-connected (n, n + 4)graphs with three triangles and at least two induced 4-cycles . In each chapter, we obtain new families of chromatically unique graphs and chromatically equivalent graphs. We end the thesis by classifying all the 2-connected (n, n + 4)-graphs with exactly three triangles. We also determine the chromatic polynomial of all these graphs. The determination of the chromaticity of most classes of these graphs is left as an open problem for future research.

Item Type:Thesis (Masters)
Subject:Algebras, Linear
Chairman Supervisor:Associate Professor Peng Yee Hock, PhD
Call Number:FSAS 2003 48
Faculty or Institute:Faculty of Environmental Studies
ID Code:9595
Deposited By: Laila Azwa Ramli
Deposited On:17 Feb 2011 06:02
Last Modified:22 May 2012 03:53

Repository Staff Only: item control page

Document Download Statistics

This item has been downloaded for since 17 Feb 2011 06:02.

View statistics for "Chromaticity of Certain 2-Connected Graphs"


Universiti Putra Malaysia Institutional Repository

Universiti Putra Malaysia Institutional Repository is an on-line digital archive that serves as a central collection and storage of scientific information and research at the Universiti Putra Malaysia.

Currently, the collections deposited in the IR consists of Master and PhD theses, Master and PhD Project Report, Journal Articles, Journal Bulletins, Conference Papers, UPM News, Newspaper Cuttings, Patents and Inaugural Lectures.

As the policy of the university does not permit users to view thesis in full text, access is only given to the first 24 pages only.