Global ETD Search
Search theses and dissertations gathered from participating repositories worldwide. Every result links back to the library that holds it. No account is needed.
Results
Showing 1 to 20 of 42 for “"graph colouring"”.
-
Aspects of graph colouring
The four-colour conjecture of 1852, and the total colouring conjecture of 1965, have sparked off many new concepts and conjectures. In this thesis we investigate many of the outstanding conjectures, establishing various related results, and present many conjectures of our own. <br></br><br></br>We …
-
Graph Colouring and Decomposition
In this thesis we consider two variants on graph colouring. The first variant, ℓ-vertex-ranking requires that the vertices in the graph are assigned integer colours such that any path of length at most ℓ has a unique maximum colour. For this problem we give asymptotically tight bounds on the number …
-
Overlap and fractional graph colouring
… body of material exists concerning the colouring of graphs, there is much less on overlap colourings. In this thesis, we investigate the colouring of certain families of graphs.
-
Graph colouring and other stories
… of different problems within the field of Graph Theory. Half of these problems relate to edge-colourings of graphs; the other half are concerned with H-colourings, reconstruction, and pursuit and evasion games. <br></br> For graphs G and H, an H-colouring of G is a map ψ : V (G) → V (H) …
-
Probabilistic graph colouring algorithms using Zykov trees
Let G=(V ,E) be a simple, undirected graph. A colouring of G is a mapping c : V ➔ {1,2, ... ,k}. c is a proper colouring if c(u) * c(v) for all {u,v} in E. The chromatic number of G, denoted x (G), is the smallest positive integer k for which a proper k-colouring exists. The graph colouring …
-
A study on generalized solution concepts in constraint satisfaction and graph colouring
… bound on the threshold of phase transitions. Graph colouring is one of the most well-studied problems in graph theory. A solution to a graph colouring problem is a colouring of the vertices such that each colour class is a stable set. A relatively new generalization of graph colouring is …
-
The Chromatic Category: A Connection Between Planar Graph Colouring and Representation Theory
… that encodes information about the proper colourings of the duals of planar graphs. In this work, we show that the chromatic category is pivotal, provide a basis for its morphisms spaces, and show that it is related to several other categories in the literature. In particular, under some …
-
An evaluation on the gracefulness and colouring of graphs
… we shall introduce two interesting topics from graph theory and begin to explore what happens when we combine these together. We will be focusing on an area known as graph colouring and assessing it alongside a very unique set of graphs called graceful graphs. The two topic areas, although not …
-
Analysing the Effectiveness of Different Parameter Optimization Techniques for Complex Genetic Algorithmsd
… by Ashlock et al. (2014) could be used to create graphs that are hard to colour for graph colouring algorithms, specifically the random sort (RS) method. In order to determine whether or not this is possible, an optimal parameter setting for the genetic algorithm must be obtained. The appropriate …
-
Topics in computational complexity
… is notation and definitions. In Chapter 2 the subgraph homeomorphism problem, for fixed pattern graphs H, is considered. For the cases H and#x2245; C<sub>6</sub>,C<sub>7</sub>,W<sub>4</sub> or W<sub>5</sub>, we obtain exact characterizations of graphs with no subgraph homeomorphic from H, and …
-
Scratch-pad memory management for static data aggregates
… we propose two novel methodologies, the memory colouring methodology and the perfect colouring methodology, to place the static data aggregates such as arrays and structs of a program in SPM. Our methodologies are dynamic in the sense that some data aggregates can be swapped into and out of SPM …
-
Graphs and Ultrapowers
<p> Graphs are defined as a special kind of relational system and an analogue of Birkhoff's Representation Theorem for Universal Algebras is proved. The notion of ultrapower, a specialization of the ultraproducts introduced into Mathematical Logic by Tarski, Scott and others, is demonstrated to …
-
Highly Concurrent Solutions to Graph and Image Processing Problems
… including the travelling salesman problem, the graph colouring problem, and image median filtering. Novel cP systems solutions to the travelling salesman problem and graph colouring problem, with time complexity linear to the number of nodes in the graph, along with a constant-time solution to …
-
Defect-1 Choosability of Graphs on Surfaces
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 …
-
A Study of Ordered Gene Problems Featuring DNA Error Correction and DNA Fragment Assembly with a Variety of Heuristics, Genetic Algorithm Variations, and Dynamic Representations
… salesman problem, bin packing problem, and graph colouring problem. In addition, two bioinformatics problems not traditionally seen as ordered gene problems are studied: DNA error correction and DNA fragment assembly. These problems are studied with multiple variations and combinations of …
-
Belief Propagation on Dense Graphs with Few Strong Links
… when the problem can be represented by a sparse graph. They have been used to solve a range of computational problems such as decoding, graph colouring, satisfiability problems etc. In this approach, messages containing probabilistic information about nodes in the graph are being passed from node …
-
Analysis of the fitness landscape for the class of combinatorial optimisation problems
… analysis of the fitness landscape for MAX-SAT, Graph-Colouring, Travelling Salesman and Quadratic Assignment problems. Belonging to the class of NP-Hard problems, all these problems become exponentially harder as the problem size grows. We study a group of properties of the fitness landscape for …
-
Improper colourings of graphs
We consider a generalisation of proper vertex colouring of graphs, referred to as improper colouring, in which each vertex can only be adjacent to a bounded number t of vertices with the same colour, and we study this type of graph colouring problem in several different settings. The thesis is …
-
Uniqueness and Complexity in Generalised Colouring
The study and recognition of graph families (or graph properties) is an essential part of combinatorics. Graph colouring is another fundamental concept of graph theory that can be looked at, in large part, as the recognition of a family of graphs that are colourable according to certain rules. In …
Page 1 of 3