Formatted abstract

Let G be a graph in which each vertex has been coloured using one of k colours, say C_{1}, c_{2}, …, c_{k}. If a graph H in G has n_{i} vertices coloured c_{i} i = 1, 2, ... , k, and n_{i} –n_{j} < 1 for any i , j Є {1, 2, . . . , k}, then H is said to be equitably kcoloured. An Hdecomposition ɧ of G is equitably kcolourable if the vertices of G can be coloured so that every copy of H in ɧ is equitably kcoloured. In Chapters 2 to 5, we consider equitably colourable decompositions. In Chapter 2, we completely settle the existence question for equitably kcolourable vcycle decompositions of K_{v}, for 1 < k < v, and for any prime p we completely settle the existence question for equitably kcolourable iperfect pcycle decompositions of K_{p}, where 1 < k < p and 1 < i < (p  1) /2. We also completely settle the existence question for equitably 2colourable mcycle decompositions of K_{v} for m even and m = 5. Furthermore, we show that for all admissible v > 5, there exists at least one 5cycle decomposition of K_{v} which cannot be equitably 2coloured. In addition, we completely settle the existence question for equitably 2colourable mcycle decompositions of K_{v}  F and for equitably 3colourable mcycle decompositions of K_{v} and K_{v}  F, where m Є { 4, 5, 6}. We also provide upper bounds on admissible values of v for existence of equitably (m  1)colourable mcycle decompositions of K_{v} and K_{v}  F. In Chapter 3, we partially generalise our results on equitably 2colourable evenlength cycle decompositions of K_{v}  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 2coloured mcycle decomposition of K_{v}  F for even m. In Chapter 4, we completely settle the existence question for equitably 2colourable 3 and 5cycle decompositions of K_{p}(n), and for equitably 2colourable 4 and 6cycle decompositions of K_{n1},_{n2}, ... ,_{np},· In addition, we completely settle the existence question for equitably 3colourable mcycle decompositions of K_{p}(_{n}), for m Є {3, 4, 5}. In Chapter 5, we completely settle the existence question for equitably 2 and 3colourable 3cube decompositions of K_{v}, K_{v}  F and K_{x},_{y}· We also consider other types of coloured graph decompositions. Suppose that the vertices of K_{v}, have been coloured with at most two colours. Let C_{1} C_{2}, . . .C_{m} denote the colouring of the mcycle (x_{1},x_{2}, . . . ,x_{m}) which assigns the colour C_{i} to the vertex x_{i} for i = 1, 2, . . . , m, where C_{i} Є {black, white}. We let T be the set of all possible such colourings and we let S C T. If ɧ is an mcycle system such that the colouring type of every mcycle 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 4cycle decompositions with proper colouring Type S for all possible S. In Chapter 7, we completely settle the existence question for 5cycle 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.
