Coloured Graph Decompositions

Waterhouse, M A (2005). Coloured Graph Decompositions PhD Thesis, School of Physical Sciences, The University of Queensland.

Attached Files (Some files may be inaccessible until you login with your UQ eSpace credentials)
Name Description MIMEType Size Downloads
THE18769.pdf Full Text application/pdf 4.43MB 0
Author Waterhouse, M A
Thesis Title Coloured Graph Decompositions
School, Centre or Institute School of Physical Sciences
Institution The University of Queensland
Publication date 2005
Thesis type PhD Thesis
Supervisor Professor Peter Adams
Dr Darryn Bryant
Total pages 237
Collection year 2005
Language eng
Subjects L
230101 Mathematical Logic, Set Theory, Lattices And Combinatorics
780101 Mathematical sciences
Formatted abstract

Let G be a graph in which each vertex has been coloured using one of k colours, say C1, c2, …, ck. If a graph H in G has ni vertices coloured ci i = 1, 2, ... , k, and |ni –nj| < 1 for any i , j Є {1, 2, . . . , k}, then H is said to be equitably k-coloured. An H-decomposition ɧ of G is equitably k-colourable if the vertices of G can be coloured so that every copy of H in ɧ is equitably k-coloured.

In Chapters 2 to 5, we consider equitably colourable decompositions. In Chapter 2, we completely settle the existence question for equitably k-colourable v-cycle decompositions of Kv, for 1 < k < v, and for any prime p we completely settle the existence question for equitably k-colourable i-perfect p-cycle decompositions of Kp, where 1 < k < p and 1 < i < (p - 1) /2. We also completely settle the existence question for equitably 2-colourable m-cycle decompositions of Kv for m even and m = 5. Furthermore, we show that for all admissible v > 5, there exists at least one 5-cycle decomposition of Kv which cannot be equitably 2-coloured. In addition, we completely settle the existence question for equitably 2-colourable m-cycle decompositions of Kv - F and for equitably 3-colourable m-cycle decompositions of Kv and Kv - F, where m Є { 4, 5, 6}. We also provide upper bounds on admissible values of v for existence of equitably (m - 1)-colourable m-cycle decompositions of Kv and Kv - F. In Chapter 3, we partially generalise our results on equitably 2-colourable even-length cycle decompositions of Kv - F. Except for the case where v(v - 2)/2 is an odd multiple of m and v = m = 4 (mod8), we show that if the obvious necessary conditions are satisfied then there exists an equitably 2-coloured m-cycle decomposition of Kv - F for even m. In Chapter 4, we completely settle the existence question for equitably 2-colourable 3- and 5-cycle decompositions of Kp(n), and for equitably 2-colourable 4- and 6-cycle decompositions of Kn1,n2, ... ,np,· In addition, we completely settle the existence question for equitably 3-colourable m-cycle decompositions of Kp(n), for m Є {3, 4, 5}. In Chapter 5, we completely settle the existence question for equitably 2- and 3-colourable 3-cube decompositions of Kv, Kv - F and Kx,y· 

We also consider other types of coloured graph decompositions. Suppose that the vertices of Kv, have been coloured with at most two colours. Let C1 C2, . . .Cm denote the colouring of the m-cycle (x1,x2, . . . ,xm) which assigns the colour Ci to the vertex xi for i = 1, 2, . . . , m, where Ci Є {black, white}. We let T be the set of all possible such colourings and we let S C T. If ɧ is an m-cycle system such that the colouring type of every m-cycle in ɧ is in S, and every colouring type in S is represented in ɧ, then we say that ɧ has proper colouring Type S. 

In Chapter 6, we completely settle the existence question for 4-cycle decompositions with proper colouring Type S for all possible S. In Chapter 7, we completely settle the existence question for 5-cycle decompositions with proper colouring Type S for all S when |S| = 1, and for many |S| when |S| = 2. For the remaining S, where |S| = 2, we determine some necessary conditions for existence of such decompositions.

Keyword Graph theory

Document type: Thesis
Collection: UQ Theses (RHD) - UQ staff and students only
Citation counts: Google Scholar Search Google Scholar
Created: Fri, 24 Aug 2007, 18:44:47 EST