Endbericht

Projektnummer		Einzelprojekte  P18383
Titel		Konstruktion, Studium und Anwendungen von Snarks
ProjektleiterIn		FLEISCHNER Herbert
Bewilligungsdatum		20.06.2005
Universität / Forschungsstätte		Institut für Informationssysteme Abt. für Datenbanken und Artificial Intelligence, Technische Universität Wien
Gebiet(e)
Keywords		dominating cycle, nowhere-zero flows, snarks, independence number, cycle double cover
Homepage		http://www.dbai.tuwien.ac.at

Die Bedeutung der Graphentheorie in den Sozial und Naturwissenschaften (z.B. Operation Research, Computer- und Biowissenschaften) ist unumstritten. Auch innerhalb diverser mathematischen Disziplinen konnte sie fruchtbringend angewandt werden. Das vorliegende Projekt konzentriert sich auf bedeutende Fragestellungen innerhalb der Graphentheorie.
Zu den wahrscheinlich wichtigsten Vermutungen innerhalb der Graphentheorie zählen die Nowhere-Zero5-Flow Conjecture (NZ5FC) und die Cycle Double Cover Conjecture (CDCC). Erstaunlicherweise hat die Untersuchung eines Färbungsproblems (Cycle Plus Triangles (CPT) Problem), das auf P.Erdös zurückgeht und bei unmittelbarer Betrachtung in keinerlei Beziehung zur NZ5FC und CDCC steht, eine neue Herangehensweise für die Lösung dieser Vermutungen eröffnet. Der Beweis des CPT Theorems hat nämlich zu einer neuen Vermutung geführt, genannt Bipartizing Matching Conjecture (BMC) . Die Richtigkeit der BMC zusammen mit der seit langem ungelösten Dominating Cycle Conjecture würde sowohl die CDCC als auch die NZ5FC lösen.
Das Projekt untersucht die genauen Zusammenhänge dieser beiden Vermutungen als auch von Sabidussi's Compatibilty Conjecture zur BMC. Weiteres zentrales Thema des Projekts wird die Untersuchung von (speziellen) Snarks sein. Diese Klasse von Graphen spielt seit jeher eine wichtige Rolle in der Graphentheorie, da sich die NZ5FC, CDCC aber auch andere Probleme auf die Betrachtung von Snarks zurückführen lassen. Schlussendlich sind Varianten, Verallgemeinerung und eine neue Vermutung bezüglich des CPT Theorems auch Thema dieses Projekts.