Doppel -Kreisüberdeckungen, Bipartisierende Matchings und Snarks

01.01.2008 - 29.02.2012
Forschungsförderungsprojekt
Die Cycle Double Cover Conjecture (CDCC) und die Nowhere-Zero 5-Flow Conjecture (NZ5FC) gehören zu den wichtigsten ungelösten Problemen der Graphentheorie. CDCC: Jeder brückenlose Graph G enthält eine Menge S von Kreisen, sodass jede Kante von G genau zwei Kreisen in S angehört. NZ5FC: Jeder brückenlose Graph besitzt einen nowhere-zero 5-flow. Für beide Vermutungen genügt es, 3-reguläre Graphen zu betrachten, die nicht 3-Kanten-färbbar sind. Dieses Projekt soll sich mit Problemen beschäftigen, die in engem Zusammenhang mit diesen Vermutungen stehen. Die folgenden drei Forschungsrichtungen umreissen die wichtigsten Ziele dieses Projekts: 1. Beweis der CDCC sowie der Verallgemeinerten Kompatibilitäts-Vermutung (eine neue Vermutung, die in engem Zusammenhang mit der CDCC steht) für neue Klassen brückenloser Graphen; z.b. Verallgemeinerungen von Circle Graphs, Graphen mit einer Darstellung in der Ebene, die eine "beschränkte Kreuzungs-Distanz" besitzt, etc. 2. Beweis neuer struktureller Resultate in brückenlosen kubischen Graphen durch die Erforschung bipariter spannender Minoren. 3. Entwicklung neuer Konstruktionsmethoden von Snarks mit grosser Taillenweite und kleiner Knotenzahl.

Personen

Projektleiter_in

Projektmitarbeiter_innen

Institut

Förderungsmittel

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

Forschungsschwerpunkte

  • Information and Communication Technology

Schlagwörter

DeutschEnglisch
Graphentheoriegraph theory
cycle double coverDoppel -Kreisüberdeckungen
matchingmatching
cycle decompositionKreiszerlegung
snarksnark
geringfügigminor