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 20 for “"edge-colouring"”.
-
The computational complexity of edge colouring restricted graphs
Edge colouring a graph is a classic algorithmi,; graph problem which has many applications. The problem of determining the chnmatic index is, in general, NP-complete. This thesis investigates the computational complexity of edge colouring restricted graphs. Previous work has established that the …
-
EDGE-COLOURING OF GRAPHS AND EMBEDDINGS OF PARTIAL LATIN SQUARES
Let G be a graph with edge sete E(G) and maximum degree ?(G). An edge colouring ? of G is a mapping from E(G) to a set C such that no two adjacent edges have the same image. A great breakthrough in this field occurred in 1964 when V.G. Vizing proved that x’(G), the minimum number of colours needed …
-
Link scheduling directed graphs using undirected edge colours
… is the problem of assigning time slots to each edge so that communication on every edge at its assigned time may occur without interference. Interference is also modeled as a graph, typically the same as the communication graph. However, interference may occur even without the desire or …
-
Finding CCA groups and graphs algorithmically
… Cay(G,C). The set C also induces a natural edge-colouring of this graph. All affine automorphisms of the Cayley graph preserve this edge-colouring. A Cayley graph Cay(G,C) has the Cayley Colour Automorphism Property (is CCA), if all its colour-preserving automorphisms are affine. A group G …
-
Multigraphs with High Chromatic Index
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 …
-
Graph colouring and other stories
… 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) such that ij ∈ E(G) ⇒ ψ(i)ψ(j) ∈ E(H). The number …
-
Edge-colourings of graphs
… most ten. We give conditions for extending the edge-colouring of a nearly complete subgraph to the whole graph and use this result to prove a special case of Vizing's conjecture. We also use other methods to solve further cases of this conjecture. A major part of the thesis classifies those …
-
Combinatorial maps and the foundations of topological graph theory : a thesis presented in partial fulfilment of the requirements for the degree of Doctor of Philosophy in Mathematics at Massey University
… map is an n-regular graph endowed with proper edge colouring in n colours.) We establish some new results and some generalisations of important theorems in topological graph theory. The classification of surfaces, the imbedding distribution of a graph, the maximum genus of a graph, and …
-
Finding Independent Transversals Efficiently
… to solve problems in graph theory (e.g. list colouring, strong colouring, delay edge colouring, circular colouring, various graph partitioning and special independent set problems), hypergraphs (e.g. hypergraph matching), group theory (e.g. generators in linear groups), and theoretical …
-
On the Depression of Graphs
An edge ordering of a graph G = (V,E) is an injection f : E → R, where R denotes the set of real numbers. A path in G for which the edge ordering f increases along its edge sequence is called an f-ascent; an f-ascent is maximal if it is not contained in a longer f-ascent. The depression of G is the …
-
Paths and cycles in graphs and hypergraphs
… a cyclic ordering of its vertices such that the edges are all \(k\)-sets of consecutive vertices in the ordering. We consider a generalisation of Lehel's Conjecture, which states that every 2-edge-coloured complete graph can be partitioned into two cycles of distinct colour, to \(k\)-uniform …
-
Graph colourings and games
<p>Graph colourings and combinatorial games are two very widely studied topics in discrete mathematics. This thesis addresses the computational complexity of a range of problems falling within one or both of these subjects.</p><p>Much of the thesis is concerned with the computational complexity of …
-
Homogeneous sets in graphs and hypergraphs
… is independent, that is it does not contain any edge, or if it is complete, that is it contains all possible pairs or subsets of it as edges. We investigate the properties of graphs and hypergraphs in two cases of imposed restrictions on the structure of their homogeneous sets. </p> <p>First we …
-
On aspects of Ramsey theory
… throughout the thesis, including some basic knowledge of Graph Theory which is particularly useful in Chapters 2 and 3. We present Ramsey-type results about graphs in Chapters 2 and 3. In Chapter 2, we introduce the classical Ramsey's Theorem which is the Ramsey-type theorem on the edge-colouring …
-
Colouring, covering, reconstruction, and 3-to-1 maps of graphs.
… the main results in this thesis. In Chapter II, edge-colouring and total colouring of graphs are discussed. The core {dollar}G\\sb{lcub}\\Delta{rcub}{dollar} is the subgraph of G induced by the vertices of maximum degree. If {dollar}G\\sb{lcub}\\Delta{rcub}{dollar} is a forest then Fournier (24) …
-
Edge-choosability of Planar Graphs
According to the List Colouring Conjecture, if G is a multigraph then χ' (G)=χl' (G) . In this thesis, we discuss a relaxed version of this conjecture that every simple graph G is edge-(∆ + 1)-choosable as by Vizing’s Theorem ∆(G) ≤χ' (G)≤∆(G) + 1. We prove that if G is a planar graph without …
-
Colourings of random graphs
… graph parameters arising from different types of colourings of random graphs, defined broadly as an assignment of colours to either the vertices or the edges of a graph.</p> <p>The <em>chromatic number</em> X(G) of a graph is the minimum number of colours required for a vertex colouring where no …
-
Introduction to the Minimum Rainbow Subgraph problem
… problem (MRS problem): Given a graph $G$, whose edges are coloured with $p$ colours. Find a subgraph $F\\\\subseteq G$ of $G$ of minimum order and with $p$ edges such that each colour occurs exactly once. We proved that this problem is NP-hard, and even APX-hard. Furthermore, we stated upper and …
-
Colouring Problems of Erdős and Rado on Infinite Graphs
… First, we investigate vertex partitions of edge coloured complete graphs into monochromatic paths. Our main result here is an answer to a question of R. Rado from 1978: we prove that every finite edge coloured infinite complete graph can be partitioned into disjoint monochromatic paths of …
-
Liczby typu Fibonacciego, ich własności i zastosowania do problemów zliczania w grafach
W rozprawie zostały przedstawione rezultaty dotyczące ciągów typu Fibonacciego, czyli ciągów zdefiniowanych jednorodnym liniowym równaniem rekurencyjnym, ze szczególnym uwzględnieniem ich zastosowań w grafach. Wyniki zawarte w rozprawie dotyczą wyznaczania -indeksu w grafach jednocyklowych i są …