Spelling suggestions: "subject:"decolouring"" "subject:"discolourings""
1 |
On the Depression of GraphsSchurch, Mark 17 April 2013 (has links)
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 smallest integer k such that any
edge ordering f has a maximal f-ascent of length at most k. In this dissertation we
discuss various results relating to the depression of a graph. We determine a formula
for the depression of the class of trees known as double spiders. A k-kernel of a
graph G is a set of vertices U ⊆ V (G) such that for any edge ordering f of G there
exists a maximal f-ascent of length at most k which neither starts nor ends in U.
We study the concept of k-kernels and discuss related depression results, including
an improved upper bound for the depression of trees. We include a characterization
of the class of graphs with depression three and without adjacent vertices of degree
three or higher, and also construct a large class of graphs with depression three which
contains graphs with adjacent vertices of high degree. Lastly, we apply the concept
of ascents to edge colourings using possibly fewer than |E(G)| colours (integers). We
consider the problem of determining the minimum number of colours for which there
exists an edge colouring such that the length of a shortest maximal path of edges
with increasing colors has a given length. / Graduate / 0405
|
2 |
Embedding r-Factorizations of Complete Uniform Hypergraphs into s-FactorizationsDeschênes-Larose, Maxime 26 September 2023 (has links)
The problem we study in this thesis asks under which conditions an r-factorization of Kₘʰ can be embedded into an s-factorization of Kₙʰ. This problem is a generalization of a problem posed by Peter Cameron which asks under which conditions a 1-factorization of Kₘʰ can be embedded into a 1-factorization of Kₙʰ. This was solved by Häggkvist and Hellgren. We study sufficient conditions in the case where s = h and m divides n. To that end, we take inspiration from a paper by Amin Bahmanian and Mike Newman and simplify the problem to the construction of an "acceptable" partition. We introduce the notion of irreducible sums and link them to the main obstacles in constructing acceptable partitions before providing different methods for circumventing these obstacles. Finally, we discuss a series of open problems related to this case.
|
Page generated in 0.0516 seconds