Lehre

Die Arbeit untersucht Überdeckungen der Kantenmenge eines Digraphen mit k Schnitten (im Folgenden als k-Cut Cover bezeichnet). Eine äquivalente Eigenschaft ist die k-Färbbarkeit der Kanten so, dass keine zwei aufeinanderfolgenden Kanten uv, vw dieselbe Farbe erhalten. Eine Eckenfärbung mit höchstens M(k) Farben ist hinreichend für die Existenz eines k-Cut Covers, wobei M(k) der zentrale Binomialkoeffizient „k über [k/2]“ ist. Für symmetrische Digraphen erweisen sich diese beiden Eigenschaften als äquivalent. Hieraus folgt, dass das Problem zu entscheiden, ob ein (symmetrischer) Digraph ein k-Cut Cover besitzt, für k ≥ 3 NP-vollständig ist. Insbesondere untersucht diese Arbeit minimale Cut Covers in azyklischen Digraphen. Jeder azyklische Digraph mit maximalem Eingrad M(k)-1 hat ein k-Cut Cover, da er eine Eckenfärbung mit M(k) Farben besitzt. Es wird gezeigt, dass diese Schranke bestmögliche ist, und dies löst ein von Alon, Bollobás, Gyárfás, Lehel und Scott gestelltes Problem. Für die abgeänderte Bedingung, dass für jeden Knoten entweder sein Eingrad oder Ausgrad nach oben beschränkt ist, wird das minimale k, welches ein k-Cut Cover im Allgemeinen garantiert, bis auf höchstens zwei mögliche Werte bestimmt. Außerdem werden Cut Covers in Potenzen von gerichteten Pfaden betrachtet. Es wird gezeigt, dass ein k-Cut Cover in der d-ten Potenz beliebig langer gerichteter Pfade genau dann existiert, wenn d ≤ (c-o(1)) 2^k, für eine Konstante c ∈ [1/e, 1/2]. Ein Cut Cover in einem Digraphen kann auf alle Digraphen übertragen werden, die homomorph zu ihm sind. Die Existenz eines Homomorphismus zu einer Potenz eines gerichteten Pfades ist in polynomialer Zeit überprüfbar und äquivalent zu einer Gleichgewichtsbedingung für die Anzahl der Vorwärts- und Rückwärtskanten von ungerichteten Kantenzügen. Das Problem, zu entscheiden, ob ein azyklischer Digraph ein 3-Cut Cover besitzt, ist NP-vollständig, sogar für planare Digraphen mit maximalem Ein- und Ausgrad 3, die einen Homomorphismus zur dritten Potenz des gerichteten Pfades auf 12 Ecken besitzen.

In der vorliegenden Masterarbeit wird eine Abschwächung einer Vermutung von Thomassen gezeigt. Thomassen hatte vermutet, dass 4-zusammenhängende Kantengraphen hamiltonsch sind - das ist, sie besitzen einen aufspannenden Kreis. Hier zeigen wir, dass, mit einer wesentlich einschränkenden Bedingung an Ecken des Grades 3 im Urbild des Kantengraphen, 5-reguläre, 4-zusammenhängende Kantengraphen hamiltonsch sind. Weiterhin gibt es eine Vermutung, die von L. Lovász im Jahr 1969 aufgestellt wurde. Diese besagt, dass - bis auf wenige Ausnahmen - alle vertex-transitiven Graphen hamiltonsch sind, wobei man einen Graphen vertex-transitiv nennt, wenn seine Automorphismengruppe transitiv auf den Ecken des Graphen wirkt. Durch Ausnutzen des obigen Resultates und nach Klassifikation der 5-regulären vertex-transitiven Kantengraphen können wir dann zeigen, dass vertex-transitive, 5-reguläre Kantengraphen, in deren Urbild Kreise der Länge 4 enthalten sind, hamiltonsch sind.Abschließend fokussieren wir uns auf ein Resultat von Jaeger, der 1979 eine sehr nützliche Äquivalenz zeigte, in der er die Kantenmengen, die innerhalbe eines gegebenen Graphen zu einem eulerschen Teilgraphen erweitert werden können, klassifizierte. Dies nutzen wir, um Resultate, die bereits nützlich dafür waren, Abschwächungen von Thomassens Vermutung zu zeigen, zu verschärfen.

In dieser Arbeit wird eine Verschärfung eines Spezialfalls der Hadwiger-Vermutung gelöst. Es werden Graphen mit einer Kempe-Färbung, das ist eine Färbung, in der der von je zwei Farbklassen induzierte Teilgraph zusammenhängend ist, betrachtet und unter diesen solche, in denen alle Farbklassen die Größe zwei haben. Unter dieser Voraussetzung konnte gezeigt werden, dass, wenn der Graph nicht allzu viele nicht verbundene Kanten besitzt, er ein perfektes Matching, in dem die Kanten paarweise verbunden sind, haben muss. Dieses verbundene perfekte Matching stellt dann einen vollständigen Minor dar, der so viele Taschen hat, wie die Färbung Farbklassen.

Die Arbeit untersucht unter anderem folgende Darstellungs- und Konstruktionsprobleme: Gegeben sind Mengensysteme X und A über einer gemeinsamen Grundmenge. Ist es möglich, die Mengen aus X mit beliebigen Durchschnitten und Vereinigungen aus den Mengen aus A als Ausdruck darzustellen bzw. in Form einer Konstruktionsvorschrift zu konstruieren? Dieses Problem ist in polynomieller Zeit entscheidbar. Für eine Modifikation des Problems sei weiter eine Familie von n [Element von] N Mengenoperationen gegeben, welche in der Darstellung bzw. Konstruktion zusätzlich zu Durchschnitten und Vereinigungen (einmalig) verwendet werden dürfen. Auch dieses Problem ist für eine Klasse von Mengenoperationen, zu der insbesondere alle zweistelligen sowie die Komplementbildung gehören, in polynomieller Zeit entscheidbar. Für n = 3 viele hinreichend komplexe, aber feste Mengenoperationen ist das Problem dagegen NP-vollständig. Dies bleibt bestehen, wenn wir statt der Verwendung von drei Mengenoperationen drei frei wählbare Mengen zulassen. Die zugehörige Entscheidungsfrage ist allgemein: Gibt es ein Mengensystem S aus n Mengen so, dass die Mengen aus X mit beliebigen Durchschnitten und Vereinigungen aus den Mengen aus A [Vereinigungsmenge] S konstruierbar bzw. als Ausdruck darstellbar sind? Eine Verallgemeinerung dieses Problems ist äquivalent zum folgenden Entscheidungsproblem für einen gegebenen Digraphen D = (V, E) und n [Element von] N: Gibt es n Teilmengen von V (Schnitte in D) so, dass für jede Kante xy [Element von] E eine der Mengen die Ecke x, jedoch nicht die Ecke y enthält? Dies wiederum ist äquivalent zu einer Zerlegung der Kantenmenge E in n Mengen, welche nicht zugleich Kanten xy und yz für irgendwelche Ecken x, y, z enthalten. Auch diese Probleme sind NP-vollständig, insbesondere für azyklische Digraphen und n = 3.

Ein wichtiger Teil der Graphentheorie sind bis heute Färbungsprobleme. Das klassische Färbungsproblem ist ein kombinatorisches Optimierungsproblem. Im Mittelpunkt steht dabei die Untersuchung der chromatische Zahl. Erweitern wir dieses Konzept und fordern, dass jede Farbklasse streng-t-degeneriert ist, so nennen wir die minimale Anzahl benötigter Farben die Eckenpartitionszahl. Wir zeigen grundlegende Eigenschaften kritischer Graphen bezüglich der Eckenpartitionszahl und untersuchen, wann ein Graph in zwei disjunkte Teilgraphen zerlegt werden kann, wobei jede Ecke des ersten Teilgraphen mit jeder Ecke des zweiten Teilgraphen durch genau t Kanten verbunden wird. Des Weiteren untersuchen wir die minimale Anzahl Kanten eines kritischen Graphen bezüglich der Eckenpartitionszahl. Außerdem erweitern wir das Strong Perfect Graph Theorem auf die Eckenpartitionszahl mit t=2.