Bitte warten...
Bitte warten...
English
Hilfe
Login
Forschungsportal
Suche
Forschungsprofile
Forschungsprojekte
Projektvollmacht
Lehre
Forschung
Organisation
Konstruktion, Studium und Anwendung von Snarks
01.08.2005 - 31.01.2008
Forschungsförderungsprojekt
Die Bedeutung der Graphentheorie in den Sozial- und Naturwissenschaften (z.B. Operation Research, Computer- und Biowissenschaften) ist unumstritten. Auch innerhalb diverser mathematischer 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 neuer 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 Compatibility 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.
Personen
Projektleiter_in
Ao.Univ.Prof. Dr. Herbert Fleischner
(E184)
Projektmitarbeiter_innen
Projektass.(FWF) Mag.rer.nat. Dr.rer.nat. Arthur Hoffmann-Ostenhof
(E184)
Institut
E184 - Institut für Informationssysteme
Förderungsmittel
FWF - Österr. Wissenschaftsfonds (National)
Fonds zur Förderung der wissenschaftlichen Forschung (FWF)
Forschungsschwerpunkte
Computational Science and Engineering