Navigation

Springe zum Hauptinhalt
Fakultät für Informatik
Informatik-Kolloquien

Informatik-Kolloquien

264. Informatik-Kolloquium

 

Öffentliche Verteidigung im Rahmen des Promotionsverfahrens

Herr Dipl.-Math. Knut Odermann

TU Chemnitz
Fakultät für Informatik
Professur Theoretische Informatik und Informationssicherheit

 

"Kantenfärbung von Graphen ohne bestimmte kleine regenbogengefärbte Teilgraphen"

 

Mittwoch, 04.01.2017
11:30 Uhr, Straße der Nationen 62, 1/B006

Alle interessierten Personen sind herzlich eingeladen!


Abstract:
Eine r-Kantenfärbung eines Graphen G = (V,E) auf n Knoten ist eine Abbildung von der Kantenmenge E in die Menge {1,...,r} von Farben. Die Frage ist, wieviele derartige Kantenfärbungen mit r Farben ein gegebener Graph G erlaubt, ohne einen zuvor festgelegten und nach einem gewissen Muster gefärbten Teilgraphen F zu enthalten. Insbesondere ist der extremale Fall von Interesse: welche Graphen auf n Knoten sind extremal, d.h., welche erlauben die meisten r-Kantenfärbungen, ohne einen zuvor festgelegten und nach einem gewissen Muster gefärbten Teilgraphen F zu enthalten?
Untersuchungsgegenstand der Dissertation sind hauptsächlich r-Kantenfärbungen ohne Teilgraphen F, die nicht nach dem Regenbogenmuster gefärbt sind. Das Regenbogenmuster, bei dem alle Kanten des verbotenen Graphen F paarweise unterschiedlich gefärbt sind, ist das natürliche Gegenstück zu den einfarbigen verbotenen Teilgraphen, die bereits von Alon et. al untersucht wurden. Der Schwerpunkt liegt auf der Untersuchung der Fälle, in denen F ein vollständiger Graph K_{k+1} oder ein Stern S_t ist. Asymptotische Resultate verwenden das Regularitätslemma von Szemerédi.
Die wesentlichen Ergebnisse sind die folgenden. Asymptotisch ist der Turángraph T_k(n) der einzige extremale Graph bzgl. der Anzahl der Färbungen ohne einen regenbogengemusterten Teilgraphen K_{k+1}. Speziell für ein Regenbogendreieck F = K_3, also k = 2, wird nachgewiesen, dass für alle n > 4 und alle r > 9 der Turángraph T_k(n) der einzige extremale Graph auf n Knoten ist. Ferner erlaubt asymptotisch der vollständige Graph K_n die meisten Färbungen ohne einen regenbogengemusterten Stern S_t. Es wird weiterhin ein Algorithmus vorgestellt, der in polynomieller Zeit zu jedem gegebenen r-kantengefärbten Graphen G mit vielen Kanten und gewissen weiteren Parametern entweder einen Regenbogenteilgraphen K_{k+1} von G findet oder einen geringen Anteil der Kanten aus G entfernt, so dass der restliche Graph nachweislich keinen Regenbogenteilgraphen K_{k+1} enthält.
 

zurück

Presseartikel