The classical (proper) graph colouring problem asks for a colouring of the vertices of a graph with the minimum number of colours such that no two vertices with the same colour are adjacent. Equivalently the colouring is required to be such that the graph induced by the vertices coloured the same colour has the maximum degree equal to zero. The graph parameter associated with the minimum possible number of colours of a graph is called chromatic number of that graph. One generalization of this classical problem is to relax the requirement that the maximum degree of the graph induced by the vertices coloured the same colour be zero, and instead allow it to be some integer d. For d = 0, we are back at the classical proper colouring. For other values of d we say that the colouring has defect d. Another generalization of the classical graph colouring, is list colouring and its associated parameters: choosability and choice number. The main result of this thesis is to show that every graph G of Euler genus μ is ⌈2 + √(3μ + 3)⌉–choosable with defect 1 (equivalently, with clustering 2). Thus allowing any defect, even 1, reduces the choice number of surface embeddable graphs below the chromatic number of the surface. For example, the chromatic number of the family of toroidal graphs is known to be 7. The bound above implies that toroidal graphs are 5-choosable with defect 1. This strengthens the result of Cowen, Goddard and Jesurum (1997) who showed that toroidal graphs are 5-colourable with defect 1. In a graph embedded in a surface, two faces that share an edge are called adjacent. We improve the above bound for graphs that have embeddings without adjacent triangles. In particular, we show that every non-planar graph G that can be embedded in a surface of Euler genus μ without adjacent triangles, is ⌈(5+ √(24μ + 1)) /3⌉–choosable with defect 1. This result generalizes the result of Xu and Zhang (2007) to all the surfaces. They proved that toroidal graphs that have embeddings on the torus without two adjacent triangles are 4-choosable with defect 1.

This thesis will study a variety of problems in graph theory. Initially, the focus will be on finding minimal degree conditions which guarantee the existence of various subgraphs. These subgraphs will all be formed of cycles, and this area of work will fall broadly into two main categories. First to be considered are cycles in edge-coloured graphs and, in particular, two questions of Li, Nikiforov and Schelp. It will be shown that a 2-edge-coloured graph with minimal degree at least 3n/4 either is isomorphic to the complete 4-partite graph with classes of order n/4, or contains monochromatic cycles of all lengths between 4 and n/2 (rounded up). This answers a conjecture of Li, Nikiforov and Schelp. Attention will then turn to the length of the longest monochromatic cycle in a 2-edge-coloured graph with minimal degree at least cn. In particular, a lower bound for this quantity will be proved which is asymptotically best possible. The next chapter of the thesis then shows that a hamiltonian graph with minimal degree at least (5-sqrt7)n/6 contains a 2-factor with two components. The thesis then concludes with a chapter about X_H, which is the number of copies of a graph H in the random graph G(n,p). In particular, it will be shown that, for a connected graph H, the value of X_H modulo k is approximately uniformly distributed, provided that k is not too large a function of n.

In this thesis we take a specialized approach to edge-colouring by focusing exclusively on multigraphs with high chromatic index. The bulk of our results can be classified into three categories. First, we prove results which aim to characterize those multigraphs achieving known upper bounds. For example, Goldberg's Theorem says that χ'≤ Δ+1+(Δ-2}/(g₀+1) (where χ' denotes chromatic index, Δ denotes maximum degree, and g₀ denotes odd girth). We characterize this bound by proving that for a connected multigraph G, χ'= Δ+1+(Δ-2}/(g₀+1) if and only if G=μC_g₀ and (g₀+1)|2(μ-1) (where μ denotes maximum edge-multiplicity). Our second category of results are new upper bounds for chromatic index in multigraphs, and accompanying polynomial-time edge-colouring algorithms. Our bounds are all approximations to the famous Seymour-Goldberg Conjecture, which asserts that χ'≤ max{⌈ρ⌉, Δ+1} (where ρ=max{(2|E[S]|)/(|S|-1): S⊆V, |S|≥3 and odd}). For example, we refine Goldberg's classical Theorem by proving that χ'≤ max{⌈ρ⌉, Δ+1+(Δ-3)/(g₀+3)}. Our third category of results are characterizations of high chromatic index in general, with particular focus on our approximation results. For example, we completely characterize those multigraphs with χ'> Δ+1+(Δ-3)/(g₀+3). The primary method we use to prove results in this thesis is the method of Tashkinov trees. We first solidify the theory behind this method, and then provide general edge-colouring results depending on Tashkinov trees. We also explore the limits of this method, including the possibility of vertex-colouring graphs which are not line graphs of multigraphs, and the importance of Tashkinov trees with regard to the Seymour-Goldberg Conjecture.

In this thesis we take a specialized approach to edge-colouring by focusing exclusively on multigraphs with high chromatic index. The bulk of our results can be classified into three categories. First, we prove results which aim to characterize those multigraphs achieving known upper bounds. For example, Goldberg's Theorem says that χ'≤ Δ+1+(Δ-2}/(g₀+1) (where χ' denotes chromatic index, Δ denotes maximum degree, and g₀ denotes odd girth). We characterize this bound by proving that for a connected multigraph G, χ'= Δ+1+(Δ-2}/(g₀+1) if and only if G=μC_g₀ and (g₀+1)|2(μ-1) (where μ denotes maximum edge-multiplicity). Our second category of results are new upper bounds for chromatic index in multigraphs, and accompanying polynomial-time edge-colouring algorithms. Our bounds are all approximations to the famous Seymour-Goldberg Conjecture, which asserts that χ'≤ max{⌈ρ⌉, Δ+1} (where ρ=max{(2|E[S]|)/(|S|-1): S⊆V, |S|≥3 and odd}). For example, we refine Goldberg's classical Theorem by proving that χ'≤ max{⌈ρ⌉, Δ+1+(Δ-3)/(g₀+3)}. Our third category of results are characterizations of high chromatic index in general, with particular focus on our approximation results. For example, we completely characterize those multigraphs with χ'> Δ+1+(Δ-3)/(g₀+3). The primary method we use to prove results in this thesis is the method of Tashkinov trees. We first solidify the theory behind this method, and then provide general edge-colouring results depending on Tashkinov trees. We also explore the limits of this method, including the possibility of vertex-colouring graphs which are not line graphs of multigraphs, and the importance of Tashkinov trees with regard to the Seymour-Goldberg Conjecture.

Oxalis reclinata Jacq., is a dicotyledonous plant. O. reclinata belongs to the family Oxalidaceae. This plant produced callus which accumulated red coloured anthocyanin pigments when cultured in vitro. The levels of anthocyanin accumulated by O. reclinata callus were higher than in the intact plant. The major pigment was isolated and identified as cyanjdin-3-glucoside (CROUCH, VAN STADEN, VAN STADEN, DREWES & MEYER, 1993). In nature, anthocyanins are responsible for orange, red, purple and blue colouration of certain tissues of higher plant s. Due to the toxicity of many synthetic red colouring agents, anthocyanins are regarded as potential substitutes for synthetic food colourants. This research was aimed at investigating mechanisms which induce pigment production as well as to optimize anthocyanin yield from callus cultures of O. reclinata, once anthocyanin production was stimulated. Pigmented and non-pigmented callus lines were generated from O. reclinata (CROUCH & VAN STADEN, 1994) and maintained on MURASHIGE & SKOOG (1962) agar medium (O.8% [w/v], pH 5.7) supplemented with 0.5 mgℓ ¯¹ BA, 5 mgℓ ¯¹ NAA, 30 gℓ ¯¹ sucrose and 0.1 gℓ ¯¹ myo-inositol. Plant tissue culture studies were conducted on red and white lines of O. reclinata to optimize callus yield and anthocyanin production in vitro. This involved manipulating contributory factors of the culture environment (carbohydrates, nitrates, phosphates, phytohormones, light and temperature). In vitro studies showed that, light played an inductive role in anthocyanin production in callus cultures of O. reclinata. The auxin, 2,4- dichlorophenoxyacetic acid (2,4-D) reduced pigment production but increased callus biomass. This hormone probably exerted its effect by reducing the pool of anthocyanin precursors, such as phenylalanine, resulting in increased primary metabolic activity. Suspension cultures were shown to be a viable means of propagating pigmented callus cells of O. reclinata. The growth curves for red and white callus cells were determined using the settled cell volume (SCV) method. Pigmented cell cultures grew for longer periods compared to nonpigmented cells of O. reclinata. White callus cells reached the stationary phase after 18 days. Red callus cells continued growing exponentially for an extra three days compared to white callus cells. The vacuole was identified as the organelle where anthocyanins accumulate using the light microscope. The molecular techniques of two-dimensional electrophoresis and in vitro translation were utilized to analyze differences in gene expression between white and red callus cultures of O. reclinata. Thus far, two-dimensional electrophoresis has shown that the red callus of O. reclinata had more polypeptides compared to the white callus. The level of gene expression was higher in the red callus compared to white callus, as revealed by nonradioactive in vitro translation. With optimization of radioactive in vitro translation, identification of specific structural anthocyanin genes which are under regulatory control should be possible. Future research should aim at acquiring a better understanding about the genetic control of anthocyanin biosynthesis in order to manipulate this pathway effectively. / Thesis (M.Sc.)-Univesity of Natal, Pietermaritzburg, 1996.

As cloud computing continues to gain popularity and its economies of scale continue to improve, stakeholders want to minimise the security risk, protect their data and other resources while maximising the gains of using any cloud resources and its application. It is predicted that by the end of 2017, bulk of spending on any IT infrastructure would be on cloud infrastructure and services as many critical applications – power, medical, finance among others continue to be migrated onto cloud platforms. For these sectors, the security challenges of cloud adoption continue to be of a great concern even with its benefits. The ability to trust and measure security levels of any cloud platform is paramount in the complete adoption and use of cloud computing in many mission critical sectors. In-depth study and analysis of the trustworthiness of various cloud based platforms/systems are often limited by the complex and dynamic nature of cloud and often do not correctly foresee or practically determine the varying trust relationship between and across the cloud layers, components (schedulers), algorithms and applications especially at a large scale. Tradition security and privacy controls continue to be implemented on cloud but due to its fluid and dynamic nature, research work in the area of end-user attestable trust evaluation of the cloud platform is limited. Most of the current simulation tools do not cater for modelling of Trust on scalable multi-layer cloud deployments (including workflow and infrastructure).Even as these tools continue to be implemented none has been used to cater for all the layers of the cloud platform. This research presents a deployment of trusted computing applied in cloud computing suited for mission critical applications. It attempts to simplify the integration of trusted platform module based integrity measurement into cloud infrastructure. Using Eucalyptus cloud software on server-grade hardware, a trusted community cloud platform was deployed on the Brunel Network as presented in Chapter 3. Security is enhanced by the integration of an end-user accessible TPM integrity measurement and verification process; this guarantees trusted ownership and integrity of the uploaded data and provides additional level of trust for the cloud platform. This research further presents a technique which allows data owners to first secure their data offline by inserting colour drops into the data using steganography. The colour drops are used to detect unauthorised modifications, verify data owner in the event the copyright of the data is in dispute and identify the path through which it was tampered with. This process ensures integrity and confidentiality of the resources. This thesis also presents a trust model using fuzzy logic which was simulated using Simulink in Matlab and subsequently evaluated on an experimental platform deployed on the Brunel network. Using this model, end-users can determine the trust values for a cloud platform or service, as well as, classify and compare various cloud platforms. The results obtained suggest that the outputs of this research work can improve end-user confidence when selecting or consuming cloud resources with enhanced data integrity and protection.

A (k,l)-colouring of a graph is a partition of its vertex set into k independent sets and l cliques. The bichromatic number chi^b of a graph is the minimum r$ such that the graph is (k,l)-colourable for all k+l=r. The bichromatic number is related to the cochromatic number, which can also be defined in terms of (k,l)-colourings. The bichromatic number is a fairly recent graph parameter that arises in the study of extremal graphs related to a classical result of Erd\H{o}s, Stone and Simonovits, and in the study of the edit distance of graphs from hereditary graph classes. While the cochromatic number has been well studied in the literature, there are only few known structural results for the bichromatic number. A main focus of this thesis is to establish a foundation of knowledge about the bichromatic number. The secondary focus is on $(k,l)$-colourings of certain interesting graph classes. Two known bounds for the bichromatic number are $\chi^b \leq \chi + \theta - 1$, where $\chi$ is the chromatic number and $\theta$ the clique covering number of the graph, and $\chi^b \geq \sqrt{n}$, where $n$ the number of vertices of the graph. We give a complete characterization of all graphs for which equality holds in the first bound, and show that the second bound is best possible by constructing graphs for square numbers $n$ such that equality holds in the bound. We investigate graphs for which the bichromatic number equals the cochromatic number and prove a Brooks-type theorem for the bichromatic number. Regarding $(k,l)$-colourings, we find a new algorithm for calculating the $(k,l)$-colourability of cographs and show that cographs have a particularly nice representation with regard to $(k,l)$-colourings. For proper circular arc graphs, we provide a method for $(k,l)$-colouring if $l \geq 1$, and establish an algebraic characterization for all maximally $(k,0)$-colourable proper circular arc graphs. Finally, we investigate the bichromatic number and cochromatic with respect to lexicographic products and show several nice bounds. / Graduate

Doctor en Ciencias de la Ingeniería, Mención Modelación Matemática / The first part of this thesis concerns monochromatic cycle partitions. We make the following three contributions. Our first result is that for any colouring of the edges of the complete bipartite graph $K_{n,n}$ with 3 colours there are 5 disjoint monochromatic cycles which together cover all but $o(n)$ vertices of the graph. In the same situation, 18 disjoint monochromatic cycles together cover all vertices. Next we show that given any $2$-local edge-colouring of the edges of the balanced complete bipartite graph $K_{n,n}$, its vertices can be covered with at most $3$ disjoint monochromatic paths. And, we can cover all vertices of any complete or balanced complete bipartite $r$-locally edge-coloured graph with $O(r^2)$ disjoint monochromatic cycles. We also determine the $2$-local bipartite Ramsey number of a path: Every $2$-local edge-colouring of the edges of $K_{n,n}$ contains a monochromatic path on $n$ vertices. Finally, we prove that any edge-colouring in red and blue of a graph on $n$ vertices and of minimum degree $2n/3 + o(n)$ admits a partition into three monochromatic cycles. This confirms a conjecture of Pokrovskiy approximately. The second part of this thesis contains two independent results about (proper) edge-colouring and parameter estimation respectively. With regards to edge-colouring, we conjecture that any graph $G$ with treewidth $k$ and maximum degree $\Delta(G)\geq k + \sqrt{k}$ satisfies $\chi'(G)=\Delta(G)$. In support of the conjecture we prove its fractional version. Concerning parameter estimation we study, for any fixed monotone graph property $\mathcal{P}=\text{Forb}(\mathcal{\mathcal{F}})$, the sample complexity of estimating a bounded graph parameter $z_{\mathcal{\mathcal{F}}}$ that, for an input graph $G$, counts the number of {spanning} subgraphs of $G$ that satisfy $\mathcal{P}$. Using a new notion of vertex partitions, we improve upon previous upper bounds on the sample complexity of estimating $z_{\mathcal{\mathcal{F}}}$.

We define a variation of injective oriented colouring as reflexive injective oriented colouring, or rio-colouring for short, which requires an oriented colouring to be injective on the neighbourhoods of the underlying graph, without requiring the colouring to be proper. An analysis of the complexity of the problem of deciding whether an oriented graph has a k-rio-colouring is considered, and we find a dichotomy for the values of k below 3 and above, being in P or NP-complete, respectively. Characterizations are given for the oriented graphs resulting from the polynomial-time solvable cases, and bounds are given for the rio-chromatic number in terms of maximum in-degree and out-degree, in general, and for oriented trees. Also, a polynomial-time algorithm is developed to aid in the rio-colouring of oriented trees.

A distinguishing colouring of a graph G is a labelling of the vertices of G with colours such that no non-trivial automorphism of G preserves all colours. The distinguishing number of G is the minimum number of colours in a distinguishing colouring. This thesis presents a survey of the history of distinguishing colouring problems and proves new bounds and computational results about distinguishability. An algorithm to generate all labellings of a graph up to isomorphism is presented and compared to a previously published algorithm. The new algorithm is shown to have performance competitive with the existing algorithm, as well as being able to process automorphism groups far larger than the previous limit. A specialization of the algorithm is used to generate all minimal distinguishing colourings of a set of graphs with large automorphism groups and compute their distinguishing numbers. / Graduate / 0984 / 0405 / bbird@uvic.ca