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"”.

  1. 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 …

    uvic Repository record for The computational complexity of edge colouring restricted graphs (opens in a new tab)

  2. 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 …

    nus Repository record for EDGE-COLOURING OF GRAPHS AND EMBEDDINGS OF PARTIAL LATIN SQUARES (opens in a new tab) Download file for EDGE-COLOURING OF GRAPHS AND EMBEDDINGS OF PARTIAL LATIN SQUARES (opens in a new tab)

  3. 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 …

    ubc Repository record for Link scheduling directed graphs using undirected edge colours (opens in a new tab) Download PDF for Link scheduling directed graphs using undirected edge colours (opens in a new tab)

  4. 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 …

    lethbridge Repository record for Finding CCA groups and graphs algorithmically (opens in a new tab)

  5. 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 …

    waterloo Repository record for Multigraphs with High Chromatic Index (opens in a new tab)

  6. 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 …

    oxford Repository record for Graph colouring and other stories (opens in a new tab)

  7. 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 …

    the-open-u Download PDF for Edge-colourings of graphs (opens in a new tab)

  8. 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 …

    massey Repository record for 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 (opens in a new tab)

  9. 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 …

    waterloo Repository record for Finding Independent Transversals Efficiently (opens in a new tab)

  10. 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 …

    uvic Repository record for On the Depression of Graphs (opens in a new tab)

  11. 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 …

    birmingham Download PDF for Paths and cycles in graphs and hypergraphs (opens in a new tab)

  12. 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 …

    oxford Repository record for Graph colourings and games (opens in a new tab)

  13. 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 …

    oxford Repository record for Homogeneous sets in graphs and hypergraphs (opens in a new tab)

  14. 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 …

    unsw Repository record for On aspects of Ramsey theory (opens in a new tab)

  15. 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) …

    wvu Repository record for Colouring, covering, reconstruction, and 3-to-1 maps of graphs. (opens in a new tab)

  16. 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 …

    brock Repository record for Edge-choosability of Planar Graphs (opens in a new tab)

  17. 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 …

    oxford Repository record for Colourings of random graphs (opens in a new tab)

  18. 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 …

    qucosa-diss

  19. 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 …

    toronto-retro Repository record for Colouring Problems of Erdős and Rado on Infinite Graphs (opens in a new tab)

  20. 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ą …

    amu-pl Repository record for Liczby typu Fibonacciego, ich własności i zastosowania do problemów zliczania w grafach (opens in a new tab)