Cycle Double Cover Problems, Generalized Bipartizing Matchings and Snarks

01.01.2008 - 29.02.2012
Research funding project
The Cycle Double Cover Conjecture (CDCC) and the Nowhere Zero 5-flow Conjecture (NZ5FC) belong to the most important conjectures in graph theory. CDCC: Every bridgeless graph G has a collection S of cycles such that each edge of G is covered by exactly two cycles of S. NZ5FC: Every bridgeless graph has a nowhere zero 5-flow. For both conjectures it suffices to consider 3-regular graphs which are not 3-edge colorable. This project investigates problems which are closely related to these conjectures. The following three parts form the main scientific goals of this project: 1. Verification of the CDCC and the Generalized Compatibility Conjecture which is a new related conjecture to the CDCC for new classes of bridgeless graphs; for instance generalizations of circle graphs, graphs which admit drawings in the plane with ¿limited crossing distance¿, etc. 2. Achieving new structural results with respect to bridgeless cubic graphs by the investigation of bipartite spanning minors. 3. Development of new construction methods which give rise to snarks with large girth and small order.

People

Project leader

Project personnel

Institute

Grant funds

  • FWF - Österr. Wissenschaftsfonds (National) Austrian Science Fund (FWF)

Research focus

  • Computational Intelligence: 100%

Keywords

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

Publications