This thesie discusses uniquely circular colourable and uniquely fractional
colourable graphs.
Suppose G = (V;E) is a graph and r ¸ 2 is a real number. A circular
r-colouring of G is a mapping f : V (G) ! [0; r) such that for any edge xy
of G, 1 ¡P jf(x) ¡ f(y)j ¡P r ¡ 1. We say G is uniquely circular r-colourable
if there is a circular r-colouring f of G and any other circular r-colouring
of G can obtained from f by a rotation or a ¢Xip of the colours. Let I(G)
denote the family of independent sets of G. A fractional r-colouring of G
is a mapping f : I(G) ! [0; 1] such that for any vertex x, Px2I f(I) = 1
and PI2I(G) f(I) ¡P r. A graph G is called uniquely fractional r-colourable if
there is exactly one fractional r-colouring of G. Uniquely circular r-colourable
graphs have been studied extensively in the literature. In particular, it is
known that for any r ¸ 2, for any integer g, there is a uniquely circular r-
colourable graph of girth at least g. Uniquely fractional r-colouring of graphs
is a new concept. In this thesis, we prove that for any r ¸ 2 for any integer
g, there is a uniquely fractional r-colourable graph of girth at least g. It is
well-known that for any graph G, Âf (G) ¡P Âc(G). We prove that for any
rational numbers r ¸ r0 > 2 and any integer g, there is a graph G of girth at
least g, which is uniquely circular r-colourable and at the same time uniquely
fractional r0-colourable.
| Identifer | oai:union.ndltd.org:NSYSU/oai:NSYSU:etd-0125106-114359 |
| Date | 25 January 2006 |
| Creators | Lin, Shu-yuan |
| Contributors | Sen-Peng Eu, D. J. Guan, Gerard Jenn-hwa Chang, Yeong-Nan Yeh, Hong-Gwa Yeh, Li-Da Dong, Xu-ding Zhu |
| 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-0125106-114359 |
| Rights | unrestricted, Copyright information available at source archive |
Page generated in 0.0016 seconds