Chromaticity of Certain 2Connected GraphsLau, Gee Choon (2003) Chromaticity of Certain 2Connected Graphs. Masters thesis, Universiti Putra Malaysia.
AbstractSince 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 2connected (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 redetermine the chromaticity of two families of 2connected (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 2connected (n, n + 4)graphs wit h at least four triangles . In Chapter 4 , we classify all the 2connected (n, n + 4)graphs wit h t hree triangles and one induced 4cycle. In Chapter 5, we classify all the 2connected (n, n + 4)graphs with three triangles and at least two induced 4cycles . In each chapter, we obtain new families of chromatically unique graphs and chromatically equivalent graphs. We end the thesis by classifying all the 2connected (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.
Repository Staff Only: Edit item detail
