• Refine Query
  • Source
  • Publication year
  • to
  • Language
  • 1
  • Tagged with
  • 1
  • 1
  • 1
  • 1
  • 1
  • 1
  • 1
  • About
  • The Global ETD Search service is a free service for researchers to find electronic theses and dissertations. This service is provided by the Networked Digital Library of Theses and Dissertations.
    Our metadata is collected from universities around the world. If you manage a university/consortium/country archive and want to be added, details can be found on the NDLTD website.
1

Simultaneously Uniquely Circular Colourable and Uniquely Fractional Colourable Graphs

Lin, Shu-yuan 25 January 2006 (has links)
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.

Page generated in 0.0813 seconds