This thesis discusses colouring, circular list colouring and adapted game colouring of graphs. For colouring, this thesis obtains a sufficient condition for a planar graph to be 3-colourable. Suppose G is a planar graph. Let H_G be the graph with vertex set V (H_G) = {C : C is a cycle of G with |C| ∈ {4, 6, 7}} and edge set E(H_G) = {CiCj : Ci and Cj have edges in common}. We prove that if any 3-cycles and 5-cycles are not adjacent to i-cycles for 3 ≤ i ≤ 7, and H_G is a forest, then G is 3-colourable.
For circular consecutive choosability, this thesis obtains a basic relation among chcc(G), X(G) and Xc(G) for any finite graph G. We show that for any
finite graph G, X(G) − 1 ≤ chcc(G) < 2 Xc(G). We also determine the value of chcc(G) for complete graphs, trees, cycles, balanced complete bipartite graphs and some complete multi-partite graphs. Upper and lower bounds for chcc(G) are given for some other classes of graphs.
For adapted game chromatic number, this thesis studies the adapted game chromatic number of various classes of graphs. We prove that the maximum
adapted game chromatic number of trees is 3; the maximum adapted game chromatic number of outerplanar graphs is 5; the maximum adapted game
chromatic number of partial k-trees is between k + 2 and 2k + 1; and the
maximum adapted game chromatic number of planar graphs is between 6 and 11. We also give upper bounds for the Cartesian product of special classes of graphs, such as the Cartesian product of partial k-trees and outerplanar graphs, or planar graphs.
| Identifer | oai:union.ndltd.org:NSYSU/oai:NSYSU:etd-0727110-000414 |
| Date | 27 July 2010 |
| Creators | Yang, Chung-Ying |
| Contributors | Gerard Jennhwa Chang, Xuding Zhu, Tsai-Lien Wong, Hong-Gwa Yeh, D. J. Guan, Zhishi Pan, Sen-Peng Eu, Tung-Shan Fu |
| Publisher | NSYSU |
| Source Sets | NSYSU Electronic Thesis and Dissertation Archive |
| Language | English |
| Detected Language | English |
| Type | text |
| Format | application/pdf |
| Source | http://etd.lib.nsysu.edu.tw/ETD-db/ETD-search/view_etd?URN=etd-0727110-000414 |
| Rights | unrestricted, Copyright information available at source archive |
Page generated in 0.0025 seconds