4 documents found

Dissertation
All rights reserved
2020-09-16

Rooted structures in graphs : a project on Hadwiger's conjecture, rooted minor ...

Hadwigers Vermutung ist eine der anspruchsvollsten Vermutungen für Graphentheoretiker und bietet eine weitreichende Verallgemeinerung des Vierfarbensatzes. Ausgehend von dieser offenen Frage der strukturellen Graphentheorie werden gewurzelte Strukturen in Graphen diskutiert. Eine Transversale einer Partition...
Master thesis
All rights reserved
2020-08

Analyse eines den 4-Zusammenhang zertifizierenden Algorithmus

Zertifikate sind in der Graphentheorie hilfreich um Eigenschaften von Graphen schnell nachweisen zu können. Elmasry, Mehlhorn und Schmidt setzten sich mit 3-Zusammenhang in Hamiltongraphen auseinander und entwickelten ein Zertifikat, welches mittels eines Algorithmus in Laufzeit O(m + n) verifiziert,...
Dissertation
All rights reserved
2019-09-30

Subtrees search, cycle spectra and edge-connectivity structures

In the first part of this thesis, we study subtrees of specified weight in a tree $T$ with vertex weights $c: V(T) \rightarrow \mathbb{N}$. We introduce an overload-discharge method, and discover that there always exists some subtree $S$ whose weight $c(S) := \sum_{v \in V(S)} c(v)$ is close to $\frac{c(T)}{2}$;...
Article / Chapter
2015-11-11

On graphs double-critical with respect to the colouring number

The colouring number col(G) of a graph G is the smallest integer k for which there is an ordering of the vertices of G such that when removing the vertices of G in the specified order no vertex of degree more than k-1 in the remaining graph is removed at any step. An edge e of a graph G is said to be...