Doppel -Kreisüberdeckungen, Bipartisierende Matchings und Snarks

01.01.2008 - 29.02.2012
Research funding project
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.

People

Project leader

Project personnel

Institute

Förderungmittel

  • FWF - Österr. Wissenschaftsfonds (National) Fonds zur Förderung der wissenschaftlichen Forschung (FWF)

Research focus

  • Computational Intelligence: 100%

Keywords

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

Publications