Loading…
Cycle structure and colorings of directed graphs
Cycle structure and colorings of directed graphs
Steiner, Raphael Mario
FG Diskrete Mathematik
This thesis deals with problems from the theory of finite directed graphs. A directed graph (digraph for short) is a binary relation whose domain has finite size. With that digraphs can be seen as a very general way of representing (possibly asymmetric) relations between pairs from a finite set of objects. Undoubtedly, such a generality allows to encode many structures by digraphs. This works particularly well if important properties of the structure at hand can be expressed as relations or connections between objects. To give some selected examples, let us mention road networks, electricity networks, radio networks, the world wide web, circuits in electronic devices, or neural networks.
A main focus of the thesis at hand is the investigation of properties of one of the most fundamental objects all over graph theory, the so-called cycle (sometimes also called circuit). A cycle in a graph is determined by a closed alternating sequence of cyclically connected vertices and edges. In a graph of finite size one will typically see loads of distinct cycles of various types. Therefore cycles constitute an important and recurring motive in almost all branches of graph theory, for instance, they play important roles in structural graph theory, in the theory of flows on directed networks, in theoretical characterizations of graph classes, as well as in the theory of graph colorings. Additionally, cycles play a decisive role in numerous algorithmic problems and their solutions, such as in the Traveling Salesman Problem, algorithms for finding a largest matching in a given graph, in the max-flow problem, and also in subprocedures such as Kruskal's algorithm for finding a minimum weight spanning tree. For those reasons, a substantial amount of research in graph theory has specialised on the structure of cycles in graphs.
In the first major part of this thesis we deal with cycles which occur in directed graphs, and prove several necessary and sufficient theoretical conditions for the existence of cycles of certain types. Additionally, we deal with algorithmic problems related to cycles in directed graphs.
In the second part we deal with the problem of acyclic colorings of directed graphs, which also relates to the (non-)existence of certain cycles. The dichromatic number represents an optimization problem in which we seek to color the vertices of a given digraph with the fewest number of colors while avoiding monochromatic directed cycles. This topic was introduced 40 years ago by Paul Erdős and Victor Neumann-Lara and since then, particularly in the last two decades, has been considered by many researchers. In this thesis we contribute new results that on the one hand establish new theoretical bounds on the dichromatic number and on the other hand shed more light on the computational complexity of this problem.
The third and last major part of this thesis carries on with the topic of digraph colorings and presents new results for various further notions of digraph coloring and ways of decomposing a given digraph into the fewest number of simpler subdigraphs.
Diese Dissertation beschäftigt sich mit Problemstellungen aus der Theorie der endlichen gerichteten Graphen. Ein (endlicher) gerichteter Graph ist eine binäre Relation, deren Quellmenge endliche Größe besitzt. Gerichtete Graphen stellen damit eine sehr allgemeine Art und Weise dar, möglicherweise asymmetrische Beziehungen zwischen einer endlichen Menge von Objekten zu codieren. Selbstverständlich erlaubt es eine solche Allgemeinheit, viele Probleme durch gerichtete Graphen zu abstrahieren, besonders dann, wenn sich wichtige Eigenschaften durch Beziehungen oder Verbindungen zwischen Objekten ausdrücken lassen. Als ausgewählte Beispiele seien hier Straßennetzwerke, Funknetze, Gasnetzwerke, das Internet, Schaltkreise in elektronischen Geräten, sowie neuronale Netzwerke genannt.
Ein Schwerpunkt der vorliegenden Arbeit liegt auf der Untersuchung von Grapheneigenschaften im Zusammenhang mit einem der wohl fundamentalsten Objekte der Graphentheorie, dem sogenannten Kreis. Ein Kreis in einem Graphen wird beschrieben durch eine geschlossene Folge von zyklisch benachbarten Knoten und Kanten ohne auftretende Wiederholungen. In einem Graphen endlicher Größe kann man typischerweise erwarten, eine ganze Reihe verschiedenster Kreise zu finden. Aufgrunddessen sind Kreise ein wichtiges und wiederkehrendes Motiv in fast allen Zweigen der Graphentheorie und treten beispielsweise in der strukturellen Graphentheorie auf, in der Theorie von Flüssen auf gerichteten Graphen, in theoretischen Charakterisierungen von Graphenklassen und in der Theorie der Färbung von Graphen. Zudem spielen Kreise in etlichen Verfahren zur Lösung von algorithmischen Problemen auf Graphen eine entscheidende Rolle, wie beispielsweise dem Problem des Handlungsreisenden, Algorithmen zur Berechnung eines größten Matchings oder dem Maximum-Flow-Problem und auch in Subprozeduren wie beispielweise Kruskals Algorithmus zum Finden eines leichtesten Spannbaums. Aus diesen Gründen hat sich eine beachtliche Menge an Resultaten der Graphentheorie darauf spezialisiert, die Kreisstruktur in Graphen selbst als Untersuchungsobjekt zu betrachten.
Im ersten Teil dieser Arbeit befassen wir uns mit Kreisen, die in gerichteten Graphen auftreten, beweisen verschiedene hinreichende und notwendige Bedingungen für die Existenz solcher Kreise und betrachen algorithmische Fragestellungen in diesem Zusammenhang.
Im zweiten Teil der Arbeit beschäftigen wir uns mit dem Problem der gerichteten Graphenfärbung, das auch mit der Existenz gewisser Kreise zu tun hat. Hierbei handelt es sich um ein Optimierungsproblem, bei dem man die Knoten des Graphen mit möglichst wenigen Farben so zu färben versucht, dass keine gerichteten Kreise innerhalb einer Farbklasse auftreten. Dieses Problem wurde vor vier Jahrzehnten von Paul Erdős und Victor Neumann-Lara aufgeworfen und seitdem in der Literatur studiert. In dieser Arbeit tragen wir neue Resultate bei, die einerseits neue Schranken an die Zahl der benötigten Farben liefern und andererseits die algorithmische Komplexität des Problems beleuchten.
Der dritte Teil der Arbeit knüpft an den zweiten Teil an und liefert neue Resultate für diverse weitere Arten, einen gerichteten Graphen zu färben oder in möglichst wenige strukuriertere Subgraphen zu zerlegen.
