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

Projektmitarbeiter_innen

Institut

Förderungsmittel

  • Fonds zur Förderung der wissenschaftlichen Forschung (FWF)

Forschungsschwerpunkte

  • Computational Science and Engineering