Construction, Study and Applications of Snarks

01.08.2005 - 31.01.2008
Research funding project
The Cycle Double Cover Conjecture (CDCC) and the Nowhere-Zero5-Flow Conjecture (NZ5FC) are two of the most outstanding conjectures in graph theory. Surprisingly, the investigation of a colouring theorem, namely, the Cycle Plus Triangles Theorem (CPT-Theorem), originally conjectured by P. Erdös, leads to a conjecture which opens up a new approach to tackling both the CDCC and NZ5FC. This new conjecture is called Bipartizing Matching Conjecture (BMC) and its truth in combination with the Dominating Cycle Conjecture would solve both the CDCC and NZ5FC. This project investigates first , under which additional assumtions the validity of the NZ5FC and of the CDCC implies that cubic graphs with dominating cycle admit disjoint BMs. In all the conjectures above,however, snarks are the graphs to deal with. Therefore the main content of the project will be the study of snarks and the verification of the above conjecture for well known but also new classes of snarks. Moreover this project aims at solving at least partially a new conjecture by H. Enomoto which estimates the independece number of 4-regular graphs which are somewhat more than CPT-graphs.

People

Project leader

Project personnel

Institute

Grant funds

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

Research focus

  • Computer Science Foundations: 100%

Publications